Chordal graphs form one of the most studied graph classes. Several graph problems that are NP-hard in general become solvable in polynomial time on chordal graphs, whereas many others remain NP-hard. For a large group of problems among the latter, approximation algorithms, parameterized algorithms, and algorithms with moderately exponential or sub-exponential running time have been designed. Chordal graphs have also gained increasing interest during the recent years in the area of enumeration algorithms. Being able to test these algorithms on instances of chordal graphs is crucial for understanding the concepts of tractability of hard problems on graph classes. Unfortunately, only few published papers give algorithms for generating chordal graphs. Even in these papers, only very few methods aim for generating a large variety of chordal graphs. Surprisingly, none of these methods is directly based on the “intersection of subtrees of a tree” characterization of chordal graphs. In this paper, we give an algorithm for generating chordal graphs, based on the characterization that a graph is chordal if and only if it is the intersection graph of subtrees of a tree. Upon generating a random host tree, we give and test various methods that generate subtrees of the host tree. We compare our methods to one another and to existing ones for generating chordal graphs. Our experiments show that one of our methods is able to generate the largest variety of chordal graphs in terms of maximal clique sizes. Moreover, two of our subtree generation methods result in an overall complexity of our generation algorithm that is the best possible time complexity for a method generating the entire node set of subtrees in an “intersection of subtrees of a tree” representation. The instances corresponding to the results presented in this paper, and also a set of relatively small-sized instances are made available online.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2022027
Keywords: Random chordal graph generation, intersection of subtrees of a tree
@article{RO_2022__56_2_565_0,
author = {\c{S}eker, Oylum and Heggernes, Pinar and Ekim, Tinaz and Ta\c{s}k{\i}n, Z. Caner},
title = {Generation of random chordal graphs using subtrees of a tree},
journal = {RAIRO. Operations Research},
pages = {565--582},
year = {2022},
publisher = {EDP-Sciences},
volume = {56},
number = {2},
doi = {10.1051/ro/2022027},
mrnumber = {4398961},
zbl = {1489.05128},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2022027/}
}
TY - JOUR AU - Şeker, Oylum AU - Heggernes, Pinar AU - Ekim, Tinaz AU - Taşkın, Z. Caner TI - Generation of random chordal graphs using subtrees of a tree JO - RAIRO. Operations Research PY - 2022 SP - 565 EP - 582 VL - 56 IS - 2 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2022027/ DO - 10.1051/ro/2022027 LA - en ID - RO_2022__56_2_565_0 ER -
%0 Journal Article %A Şeker, Oylum %A Heggernes, Pinar %A Ekim, Tinaz %A Taşkın, Z. Caner %T Generation of random chordal graphs using subtrees of a tree %J RAIRO. Operations Research %D 2022 %P 565-582 %V 56 %N 2 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2022027/ %R 10.1051/ro/2022027 %G en %F RO_2022__56_2_565_0
Şeker, Oylum; Heggernes, Pinar; Ekim, Tinaz; Taşkın, Z. Caner. Generation of random chordal graphs using subtrees of a tree. RAIRO. Operations Research, Tome 56 (2022) no. 2, pp. 565-582. doi: 10.1051/ro/2022027
[1] and , Enumerating minimal dominating sets in chordal graphs. Inf. Process. Lett. 116 (2016) 739–743. | MR | Zbl | DOI
[2] , , , and , Generating and radiocoloring families of perfect graphs. In: Experimental and Efficient Algorithms. Springer (2005) 302–314. | Zbl | DOI
[3] and , An introduction to chordal graphs and clique trees. In: Graph Theory and Sparse Matrix Computations. IMA in Math. Appl., Vol. 56. Springer (1993) 1–27. | MR | Zbl | DOI
[4] , , and , Parameterized complexity of the sparsest k-subgraph problem in chordal graphs. SOFSEM. Springer (2014) 150–161. | MR | Zbl
[5] , and , Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications (1999). | MR | Zbl | DOI
[6] , A characterisation of rigid circuit graphs. Disc. Math. 9 (1974) 205–212. | MR | Zbl | DOI
[7] , On rigid circuit graphs. Ann. Math. Sem. Univ. Hamburg 25 (1961) 71–76. | MR | Zbl | DOI
[8] , and , The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation. J. Comb. Optim. 41 (2021) 710–735. | MR | Zbl | DOI
[9] and , Incidence matrices and interval graphs. Pac. J. Math. 15 (1965) 835–855. | MR | Zbl | DOI
[10] , Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comp. 1 (1972) 180–187. | MR | Zbl | DOI
[11] , The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Th. B 16 (1974) 47–56. | MR | Zbl | DOI
[12] , , and , An exact algorithm for Subset Feedback Vertex Set on chordal graphs. J. Disc. Alg. 26 (2014) 7–15. | MR | Zbl
[13] , and , Enumerating minimal connected dominating sets in graphs of bounded chordality. Theor. Comput. Sci. 630 (2016) 63–75. | MR | Zbl | DOI
[14] , Algorithmic Graph Theory and Perfect Graphs. Ann. Disc. Math. Vol. 57. Elsevier (2004). | MR | Zbl
[15] and , Über die Auflösung von Graphen in vollständige Teilgraphen. Ann. Univ. Sci. Budapest (1958) 113–121. | MR | Zbl
[16] and , Some problems of diophantine approximation: Part II. The trigonometrical series associated with the elliptic ν-functions. Acta Math. 37 (1914) 193–239. | JFM | MR | DOI
[17] , Minimal triangulations of graphs: a survey. Disc. Math. 306 (2006) 297–317. | MR | Zbl | DOI
[18] , The Art of Computer Programming: Seminumerical Algorithms. Vol. 2, Chapter 4. Addison-Wesley (1969). | MR | Zbl
[19] , Dagstuhl Seminar 14071 “Graph Modification Problems (2014).
[20] and , A linear time algorithm for deciding interval graph isomorphism. JACM 26 (1979) 183–195. | MR | Zbl | DOI
[21] , and , Two methods for the generation of chordal graphs. Ann. Oper. Res. 157 (2008) 47–60. | MR | Zbl | DOI
[22] , Parameterized coloring problems on chordal graphs. Theor. Comput. Sci. 351 (2006) 407–424. | MR | Zbl | DOI
[23] , , , and , Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs, LNCS, vol. 8165 Springer (2013) 370–381. | MR | Zbl
[24] , Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann (2014). | Zbl
[25] , and , Approximating interval coloring and max-coloring in chordal graphs. J. Exp. Alg. 10 (2005) 2–8. | MR | Zbl
[26] and , On generating random network structures: trees. International Conference on Computational Science. LNCS, Vol. 2658. Springer (2003) 879–887. | MR | Zbl
[27] , A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. Graph Theory Comput. 183 (1972) 217. | MR | Zbl
[28] , and , Algorithmic aspects of vertex elimination on graphs. SIAM J. Comp. 5 (1976) 266–283. | MR | Zbl | DOI
[29] , , and , Linear-time generation of random chordal graphs. In: Algorithms and Complexity: 10th International Conference, CIAC 2017, LNCS, Vol. 10236. Springer (2017) 442–453. | MR | Zbl | DOI
[30] , Efficient Graph Representations. Fields Institute Monograph Series. Vol. 19. AMS (2003). | MR | Zbl
[31] , Data Structures and Network Algorithms. SIAM, Philadelphia, (1983). | MR | Zbl | DOI
Cité par Sources :
A preliminary version of this paper has appeared in the Proceedings of the 10th International Conference on Algorithms and Complexity, CIAC 2017 [29].
