Abstract
Exact exponential-time algorithms for NP-hard problems is an emerging field, and an increasing number of new results are being added continuously. Two important NP-hard problems that have been studied for decades are the treewidth and the minimum fill problems. Recently, an exact algorithm was presented by Fomin, Kratsch, and Todinca to solve both of these problems in time \({\mathcal O}^{*}\)(1.9601n). Their algorithm uses the notion of potential maximal cliques, and is able to list these in time \({\mathcal O}^{*}\)(1.9601n), which gives the running time for the above mentioned problems. We show that the number of potential maximal cliques for an arbitrary graph G on n vertices is \({\mathcal O}^{*}\)(1.8135n), and that all potential maximal cliques can be listed in \({\mathcal O}^{*}\)(1.8899n) time. As a consequence of this results, treewidth and minimum fill-in can be computed in \({\mathcal O}^{*}\)(1.8899n) time.
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: UAI 2001: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, pp. 7–15. Morgan Kaufmann Publishers Inc., San Francisco (2001)
Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Alg. Disc. Meth. 8, 277–284 (1987)
Berry, A., Bordat, J.P., Cogis, O.: Generating all the minimal separators of a graph. Int. J. Foundations Comp. Sci. 11(3), 397–403 (2000)
Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing 25, 1305–1317 (1996)
Bouchitté, V., Kratsch, D., Müller, H., Todinca, I.: On treewidth approximations. Discrete Appl. Math. 136(2-3), 183–196 (2004)
Bouchitté, V., Todinca, I.: Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput. 31, 212–232 (2001)
Bouchitté, V., Todinca, I.: Listing all potential maximal cliques of a graph. Theor. Comput. Sci. 276(1-2), 17–32 (2002)
Cook, W., Seymour, P.: Tour merging via branch-decomposition. INFORMS J. Comput. 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. Theor. Comput. Sci. 289(1), 69–83 (2002)
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)
Fomin, F.V., Kratsch, D., Todinca, I.: Exact (exponential) algorithms for treewidth and minimum fill-in. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 568–580. Springer, Heidelberg (2004)
Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. J. Soc. Indust. Appl. Math. 10, 196–210 (1962)
Lauritzen, S.L., Spiegelhalter, D.J.: Local computations with probabilities on graphical structures and their applications to expert systems. J. Royal Statist. Soc., ser B 50, 157–224 (1988)
Robertson, N., Seymour, P.: Graph minors II. Algorithmic aspects of tree-width. J. Algorithms 7, 309–322 (1986)
Rose, D.J.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In: Read, R.C. (ed.) Graph Theory and Computing, pp. 183–217. Academic Press, New York (1972)
Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13, 566–579 (1984)
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. Alg. Disc. Meth. 2, 77–79 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Villanger, Y. (2006). Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In. In: Correa, J.R., Hevia, A., Kiwi, M. (eds) LATIN 2006: Theoretical Informatics. LATIN 2006. Lecture Notes in Computer Science, vol 3887. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11682462_73
Download citation
DOI: https://doi.org/10.1007/11682462_73
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32755-4
Online ISBN: 978-3-540-32756-1
eBook Packages: Computer ScienceComputer Science (R0)