Abstract
We show that for a graph G on n vertices its treewidth and minimum fill-in can be computed roughly in 1.9601n time. Our result is based on a combinatorial proof that the number of minimal separators in a graph is \(\mathcal O(n \cdot 1.7087^n)\) and that the number of potential maximal cliques s is \(\mathcal O(n^4 \cdot 1.9601^n)\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Amir, E.: Efficient approximation for triangulation of minimum treewidth. In: Uncertainty in Artificial Intelligence: Proceedings of the Seventeenth Conference (UAI 2001), San Francisco, CA, pp. 7–15. Morgan Kaufmann Publishers, San Francisco (2001)
Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discrete Methods 8, 277–284 (1987)
Berry, A., Bordat, J.P., Cogis, O.: Generating all the minimal separators of a graph. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol. 1665, p. 167. Springer, Heidelberg (1999)
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305–1317 (1996)
Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209, 1–45 (1998)
Bodlaender, H.L., Fomin, F.V.: Tree decompositions with small cost. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol. 2368, pp. 378–387. Springer, Heidelberg (2002)
Bouchitté, V., Todinca, I.: Treewidth and minimum fill-in: grouping the minimal separators. SIAM J. on Computing 31(1), 212–232 (2001)
Bouchitté, V., Todinca, I.: Listing all potential maximal cliques of a graph. Theoretical Computer Science 276(1-2), 17–32 (2002)
Bouchitté, V., Kratsch, D., Müller, H., Todinca, I.: On treewidth approximation. Discr. Appl. Math. (to appear)
Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inform. Process. Lett. 58, 171–176 (1996)
Cook, W., Seymour, P.: Tour merging via branch-decomposition. INFORMS J. on Computing 15(3), 233–248 (2003)
Dantsin, E., Goerdt, A., Hirsch, E.A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., Schöning, U.: A deterministic (2−2/(k+1))n algorithm for k-SAT based on local search. Theoret. Comput. Sci. 289, 69–83 (2002)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)
Eppstein, D.: Small maximal independent sets and faster exact graph coloring. In: Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 2001. LNCS, vol. 2125, pp. 462–470. Springer, Heidelberg (2001)
Feige, U.: Coping with the NP-hardness of the graph bandwidth problem. In: Halldórsson, M.M. (ed.) SWAT 2000. LNCS, vol. 1851, pp. 10–19. Springer, Heidelberg (2000)
Fomin, F., Kratsch, D., Todinca, I.: Exact (exponential) algorithms for treewidth and minimum fill-in, Research Report RR-2004-09, LIFO–University of Orléans (2004)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)
Held, M., Karp, R.: A dynamic programming approach to sequencing problems. J. Soc. Indust. Appl. Math. 10, 196–210 (1962)
Kaplan, H., Shamir, R., Tarjan, R.E.: Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J. Comput. 28, 1906–1922 (1999)
Kloks, T., Kratsch, D., Spinrad, J.: On treewidth and minimum fill-in of asteroidal triple-free graphs. Theoretical Computer Science 175, 309–335 (1997)
Parra, A., Scheffler, P.: Characterizations and algorithmic applications of chordal graph embeddings. Discrete Appl. Math. 79(1-3), 171–188 (1997)
Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7, 309–322 (1986)
Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition. J. Combin. Theory Ser. B 52, 153–190 (1991)
Woeginger, G.J.: Exact algorithms for NP-hard problems: a survey. In: Jünger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol. 2570, pp. 185–207. Springer, Heidelberg (2003)
Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebraic Discrete Methods 2, 77–79 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fomin, F.V., Kratsch, D., Todinca, I. (2004). Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds) Automata, Languages and Programming. ICALP 2004. Lecture Notes in Computer Science, vol 3142. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27836-8_49
Download citation
DOI: https://doi.org/10.1007/978-3-540-27836-8_49
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22849-3
Online ISBN: 978-3-540-27836-8
eBook Packages: Springer Book Archive