The Complexity of Subtree Intersection Representation of Chordal Graphs and Linear Time Chordal Graph Generation
Special Event on Analysis of Experimental Algorithms, SEA² 2019, Kalamata, Yunanistan, 24 - 29 Haziran 2019, cilt.11544 LNCS, ss.21-34, (Tam Metin Bildiri)
- Yayın Türü: Bildiri / Tam Metin Bildiri
- Cilt numarası: 11544 LNCS
- Doi Numarası: 10.1007/978-3-030-34029-2_2
- Basıldığı Şehir: Kalamata
- Basıldığı Ülke: Yunanistan
- Sayfa Sayıları: ss.21-34
- Anahtar Kelimeler: Chordal graph, Graph generation, Representation complexity
- 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 [5]. 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 (formula presented). 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 (formula presented). 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. We use this result to derive the first linear time random chordal graph generator. 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 (formula presented) edges in less than one second on a laptop computer.