The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation

DOI10.1007/S10878-021-00712-6MaRDI QIDQ2025063zbMATH OpenOpenAlexFDO

Authors Tınaz Ekim, Mordechai Shalom, Oylum Şeker

Publication date 11 May 2021

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.04916

zbMATH Keywords

chordal graphgraph generationrepresentation complexitysubtree intersection

Mathematics Subject Classification ID

Trees (05C05) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: It is known that any chordal graph on $n$ vertices can be represented as the intersection of $n$ subtrees in a tree on $n$ nodes. This fact is recently used in [2] to generate random chordal graphs on $n$ vertices by generating $n$ subtrees of a tree on $n$ nodes. It follows that the space (and thus time) complexity of such an algorithm is at least the sum of the sizes of the generated subtrees assuming that a tree is given by a set of nodes. In [2], this complexity was mistakenly claimed to be linear in the number $m$ of edges of the generated chordal graph. This error is corrected in [3] where the space complexity is shown to be $Omega(m{n}^{1/4})$. The exact complexity of the algorithm is left as an open question. In this paper, we show that the sum of the sizes of $n$ subtrees in a tree on $n$ nodes is $Theta(msqrtn)$. We also show that we can confine ourselves to contraction-minimal subtree intersection representations since they are sufficient to generate every chordal graph. Furthermore, the sum of the sizes of the subtrees in such a representation is at most $2m+n$. We use this result to derive the first linear time random chordal graph generator. Based on contraction-minimal representations, we also derive structural properties of chordal graphs related to their connectivity. In addition to these theoretical results, we conduct experiments to study the quality of the chordal graphs generated by our algorithm and compare them to those in the literature. Our experimental study indicates that the generated graphs do not have a restricted structure and the sizes of maximal cliques are distributed fairly over the range. Furthermore, our algorithm is simple to implement and produces graphs with 10000 vertices and $4.10^7$ edges in less than one second on a laptop computer.

Recommendations

• Generation of random chordal graphs using subtrees of a tree
• Linear-time generation of random chordal graphs
• Extending partial representations of subclasses of chordal graphs
• Intersection representation of a chordal graph by subtrees of a spanning tree
• Two methods for the generation of chordal graphs

Cites work

• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithmic graph theory and perfect graphs
• An exact algorithm for subset feedback vertex set on chordal graphs
• An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs
• Approximating interval coloring and max-coloring in chordal graphs
• Combinatorial problems on \(H\)-graphs
• Counting clique trees and computing perfect elimination schemes in parallel
• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• Experimental and Efficient Algorithms
• Generating labeled planar graphs uniformly at random
• Graph classes and Ramsey numbers
• scientific article; zbMATH DE number 15335 (Why is no real title available?)
• scientific article; zbMATH DE number 48812 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 3420184 (Why is no real title available?)
• Inverse chromatic number problems in interval and permutation graphs
• Linear-time generation of random chordal graphs
• On extracting maximum stable sets in perfect graphs using Lovász's theta function
• On some applications of the selective graph coloring problem
• Parameterized coloring problems on chordal graphs
• Random generation and enumeration of bipartite permutation graphs
• Small 1-defective Ramsey numbers in perfect graphs
• The firefighter problem with more than one firefighter on trees
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Topics in Intersection Graph Theory
• Two methods for the generation of chordal graphs

Cited in

(3)

• Intersection graphs of \(k\)-acyclic families of subtrees and relational database query processing.
• Linear-time generation of random chordal graphs
• Cayley trees and increasing 1, 2-trees: let's twist!

Describes a project that uses

Uses Software

• LEMON

This page was built for publication: The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2025063)