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

Tınaz Ekim (), Mordechai Shalom () and Oylum Şeker ()
Additional contact information
Tınaz Ekim: Bogazici University
Mordechai Shalom: TelHai Academic College
Oylum Şeker: University of Toronto

Journal of Combinatorial Optimization, 2021, vol. 41, issue 3, No 7, 710-735

Abstract: 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 (Gavril in J Comb Theory 16:47–56, 1974). This characterization has been recently used to generate random chordal graphs on n vertices by generating n subtrees of a tree on n nodes. The space (and thus time) complexity of an algorithm generating n subtrees of a tree on n nodes is at least the sum of the sizes of the generated subtrees. The determination of this sum was left as an open question in Şeker et al. (Generation of random chordal graphs using subtrees of a tree. arXiv preprint arXiv:1810.13326 , 2018). In this paper, we show that the sum of the sizes of n subtrees in a tree on n nodes is $$\varTheta (m\sqrt{n})$$ Θ ( m n ) . We also show that we can confine ourselves to contraction-minimal subtree intersection representations because they are sufficient to generate every chordal graph with strictly positive probability. Moreover, the sum of the sizes of the subtrees in a contraction-minimal representation is at most $$2m+n$$ 2 m + n . We use this result to derive the first linear-time random chordal graph generator. Based on contraction-minimal representations, we also derive connectivity-related structural properties of chordal graphs. Besides these theoretical results, we also conduct experiments to study the quality of the chordal graphs generated by our algorithm and compare them to those generated by existing methods from the literature. Our algorithm does not generate chordal graphs uniformly at random, which is a quite challenging open question, irrespective of the time complexity of the generator. However, our experimental study suggests that the generated graphs have a fairly varied structure as indicated by the sizes of maximal cliques. Furthermore, our algorithm is simple to implement and produces graphs with 10,000 vertices and $$4 \times 10^7$$ 4 × 10 7 edges in less than one second on a laptop computer.

Keywords: Chordal graph; Representation complexity; Graph generation; Subtree intersection (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00712-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:41:y:2021:i:3:d:10.1007_s10878-021-00712-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00712-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().