The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation
Journal of Combinatorial Optimization, cilt.41, sa.3, ss.710-735, 2021 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 41 Sayı: 3
- Basım Tarihi: 2021
- Doi Numarası: 10.1007/s10878-021-00712-6
- Dergi Adı: Journal of Combinatorial Optimization
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Applied Science & Technology Source, Chimica, Compendex, Computer & Applied Sciences, INSPEC, zbMATH
- Sayfa Sayıları: ss.710-735
- Anahtar Kelimeler: Chordal graph, Graph generation, Representation complexity, Subtree intersection
- Boğaziçi Üniversitesi Adresli: Evet
Özet
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 Θ(mn). 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 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 × 10 7 edges in less than one second on a laptop computer.