research-article

On exact algorithms for treewidth

Authors:

Hans L. Bodlaender,

Fedor V. Fomin,

Arie M. C. A. Koster,

Dieter Kratsch,

Dimitrios M. ThilikosAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 9, Issue 1

Article No.: 12, Pages 1 - 23

https://doi.org/10.1145/2390176.2390188

Published: 26 December 2012 Publication History

Abstract

We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential-time algorithms using exponential space or using only polynomial space. We first report on an implementation of a dynamic programming algorithm for computing the treewidth of a graph with running time O*(2ⁿ). This algorithm is based on the old dynamic programming method introduced by Held and Karp for the Traveling Salesman problem. We use some optimizations that do not affect the worst case running time but improve on the running time on actual instances and can be seen to be practical for small instances. We also consider the problem of computing Treewidth under the restriction that the space used is only polynomial and give a simple O*(4ⁿ) algorithm that requires polynomial space. We also show that with a more complicated algorithm using balanced separators, Treewidth can be computed in O*(2.9512ⁿ) time and polynomial space.

References

[1]

Arnborg, S., Corneil, D. G., and Proskurowski, A. 1987. Complexity of finding embeddings in a k-tree. SIAM J. Algeb. Disc. Meth. 8, 277--284.

Digital Library

[2]

Bachoore, E. H. and Bodlaender, H. L. 2005. New upper bound heuristics for treewidth. In Proceedings of the 4th International Workshop on Experimental and Efficient Algorithms (WEA 2005). S. E. Nikoletseas, Ed., Lecture Notes in Computer Science, vol. 3503, Springer Verlag, 217--227.

Digital Library

[3]

Bachoore, E. H. and Bodlaender, H. L. 2006. A branch and bound algorithm for exact, upper, and lower bounds on treewidth. In Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management (AAIM 2006), S.-W. Cheng and C. K. Poon, Eds., Lecture Notes in Computer Science, vol. 4041, Springer Verlag, 255--266.

Digital Library

[4]

Björklund, A. 2010. Determinant sums for undirected Hamiltonicity. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010). IEEE, 173--182.

Digital Library

[5]

Bodlaender, H. L. 1998. A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209, 1--45.

Digital Library

[6]

Bodlaender, H. L. 2005. Discovering treewidth. In Proceedings of the 31st Conference on Current Trends in Theory and Practive of Computer Science (SOFSEM 2005). P. Vojtás, M. Bieliková, and B. Charron-Bost, Eds., Lecture Notes in Computer Science, vol. 3381, Springer Verlag, 1--16.

Digital Library

[7]

Bodlaender, H. L. 2006. Treewidth: Characterizations, applications, and computations. In Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2006). F. V. Fomin, Ed., Lecture Notes in Computer Science, vol. 4271, Springer Verlag, 1--14.

Digital Library

[8]

Bodlaender, H. L., Fomin, F. V., Koster, A. M. C. A., Kratsch, D., and Thilikos, D. M. 2012. A note on exact algorithms for vertex ordering problems on graphs. Theory Comput. Syst. 50, 3, 420--432.

Digital Library

[9]

Bodlaender, H. L., and Koster, A. M. C. A. 2010. Treewidth computations I. Upper bounds. Inf. Computat. 208, 259--275.

Digital Library

[10]

Bodlaender, H. L., and Koster, A. M. C. A. 2011. Treewidth computations II. Lower bounds. Inf. Computat. 209, 1103--1119.

Digital Library

[11]

Bodlaender, H. L., Koster, A. M. C. A., and van den Eijkhof, F. 2005. Pre-processing rules for triangulation of probabilistic networks. Computat. Intell. 21, 3, 286--305.

[12]

Bodlaender, H. L., Koster, A. M. C. A., and Wolle, T. 2006. Contraction and treewidth lower bounds. J. Graph Algor. Appl. 10, 5--49.

[13]

Boost 1999--2009. Boost C++ libraries. http://www.boost.org/.

[14]

Bouchitté, V., and Todinca, I. 2001. Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput. 31, 212--232.

Digital Library

[15]

Bouchitté, V., and Todinca, I. 2002. Listing all potential maximal cliques of a graph. Theoret. Comput. Sci. 276, 17--32.

Digital Library

[16]

Clautiaux, F., Carlier, J., Moukrim, A., and Négre, S. 2003. New lower and upper bounds for graph treewidth. In Proceedings of the 2nd International Workshop on Experimental and Efficient Algorithms (WEA 2003), J. D. P. Rolim, Ed., Lecture Notes in Computer Science, vol. 2647, Springer Verlag, 70--80.

Digital Library

[17]

Clautiaux, F., Moukrim, A., Négre, S., and Carlier, J. 2004. Heuristic and meta-heuristic methods for computing graph treewidth. RAIRO Oper. Res. 38, 13--26.

[18]

Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. 2011. On cutwidth parameterized by vertex cover. In Proceedings of the 6th International on Parameterized and Exact Computation (IPEC 2011). Lecture Notes in Computer Science Series, vol. 7112, Springer, 246--258.

Digital Library

[19]

Dendris, N. D., Kirousis, L. M., and Thilikos, D. M. 1997. Fugitive-search games on graphs and related parameters. Theoret. Comput. Science 172, 233--254.

[20]

Fomin, F. V., Grandoni, F., and Kratsch, D. 2005. Some new techniques in design and analysis of exact (exponential) algorithms. Bull. EATCS 87, 47--77.

[21]

Fomin, F. V., Kratsch, D., and Todinca, I. 2004. Exact (exponential) algorithms for treewidth and minimum fill-in. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming, (ICALP 2004), J. Díaz, J. Karhumäki, A. Lepistö, and D. Sanella, Eds., Lecture Notes in Computer Science, vol. 3142, Springer Verlag, 568--580.

[22]

Fomin, F. V., Kratsch, D., Todinca, I., and Villanger, Y. 2008. Exact algorithms for treewidth and minimum fill-in. SIAM J. Comput. 38, 1058--1079.

Digital Library

[23]

Fomin, F. V. and Villanger, Y. 2010. Finding induced subgraphs via minimal triangulations. In Proceedings 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), J.-Y. Marion and T. Schwentick, Eds., Dagstuhl Seminar Proceedings Series, vol. 5, Leibniz-Zentrum für Informatik, Schloss Dagstuhl, Germany, 383--394.

[24]

Fomin, F. V. and Villanger, Y. 2012. Treewidth computation and extremal combinatorics. Combinatorica 32, 3, 289--308.

[25]

Fulkerson, D. R. and Gross, O. A. 1965. Incidence matrices and interval graphs. Pac. J. Math. 15, 835--855.

[26]

Gogate, V. and Dechter, R. 2004. A complete anytime algorithm for treewidth. In Proceedings of the 20th Annual Conference on Uncertainty in Artificial Intelligence (UAI 2004), D. M. Chickering and J. Y. Halpern, Eds., AUAI Press, 201--208.

Digital Library

[27]

Golumbic, M. C. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York.

[28]

Gurevich, Y. and Shelah, S. 1987. Expected computation time for Hamiltonian path problem. SIAM J. Comput. 16, 486--502.

Digital Library

[29]

Held, M. and Karp, R. 1962. A dynamic programming approach to sequencing problems. J. SIAM 10, 196--210.

[30]

Kitsunai, K., Kobayashi, Y., Komuro, K., Tamaki, H., and Tano, T. 2012. Computing directed pathwidth in O(1.89ⁿ) time. In Proceedings of the 7th International on Parameterized and Exact Computation (IPEC 2012). Lecture Notes in Computer Science Series, vol. 7535, Springer, 182--193.

Digital Library

[31]

Koivisto, M. and Parviainen, P. 2010. A space-time tradeoff for permutation problems. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). ACM, 484--492.

Digital Library

[32]

Koster, A. M. C. A. 2009. ComputeTW -- An interactive platform for computing treewidth of graphs. http://www.math2.rwth-aachen.de/~koster/ComputeTW.

[33]

Koster, A. M. C. A., Wolle, T., and Bodlaender, H. L. 2005. Degree-based treewidth lower bounds. In Proceedings of the 4th International Workshop on Experimental and Efficient Algorithms (WEA 2005), S. E. Nikoletseas, Ed., Lecture Notes in Computer Science, vol. 3503, Springer Verlag, 101--112.

Digital Library

[34]

Rose, D. J., Tarjan, R. E., and Lueker, G. S. 1976. Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5, 266--283.

Digital Library

[35]

Shoikhet, K. and Geiger, D. 1997. A practical algorithm for finding optimal triangulations. In Proceedings of the 15th National Conference on Artificial Intelligence (AAAI'97). Morgan Kaufmann, 185--190.

Digital Library

[36]

Suchan, K. and Villanger, Y. 2009. Computing pathwidth faster than 2ⁿ. In Proceedigs of the International Workshop on Parameterized and Exact Computaion (IWPEC 2009). Lecture Notes in Computer Science, vol. 5917, Springer, 324--335.

Digital Library

[37]

Tarjan, R. E. and Yannakakis, M. 1984. Simple linear time algorithms to test chordiality of graphs, test acyclicity of graphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13, 566--579.

Digital Library

[38]

TreewidthLib. 2004. Treewidthlib. http://www.cs.uu.nl/people/hansb/treewidthlib.

[39]

Villanger, Y. 2006. Improved exponential-time algorithms for treewidth and minimum fill-in. In Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), J. R. Correa, A. Hevia, and M. A. Kiwi, Eds., Lecture Notes in Computer Science, vol. 3887, Springer Verlag, 800--811.

Digital Library

[40]

Woeginger, G. J. 2003. Exact algorithms for NP-hard problems: A survey. In Combinatorial Optimization: “Eureka, you shrink”. Lecture Notes in Computer Science, vol. 2570, Springer, Berlin, 185--207.

Digital Library

Cited By

Tamaki H(2020)Experimental Analysis of TreewidthTreewidth, Kernels, and Algorithms10.1007/978-3-030-42071-0_15(214-221)Online publication date: 20-Apr-2020
https://doi.org/10.1007/978-3-030-42071-0_15
Čibej UFürst LMihelič J(2019)A Symmetry-Breaking Node Equivalence for Pruning the Search Space in Backtracking AlgorithmsSymmetry10.3390/sym1110130011:10(1300)Online publication date: 15-Oct-2019
https://doi.org/10.3390/sym11101300
Slavchev BMasliankova EKelk S(2019)A Machine Learning Approach to Algorithm Selection for Exact Computation of TreewidthAlgorithms10.3390/a1210020012:10(200)Online publication date: 20-Sep-2019
https://doi.org/10.3390/a12100200
Show More Cited By

Index Terms

On exact algorithms for treewidth
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal

We obtain a number of lower bounds on the running time of algorithms solving problems on graphs of bounded treewidth. We prove the results under the Strong Exponential Time Hypothesis of Impagliazzo and Paturi. In particular, assuming that n-variable m-...
The role of planarity in connectivity problems parameterized by treewidth

For some years it was believed that for "connectivity" problems such as Hamiltonian Cycle, algorithms running in time 2 O ( tw ) n O ( 1 ) - called single-exponential - existed only on planar and other topologically constrained graph classes, where tw ...
Treewidth and Pathwidth of Permutation Graphs

In this paper, we show that the treewidth and pathwidth of a permutation graph can be computed in polynomial time. In fact we show that, for permutation graphs, the treewidth and pathwidth are equal. These results make permutation graphs one of the few ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 9, Issue 1

December 2012

252 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/2390176

Issue’s Table of Contents

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 December 2012

Accepted: 01 May 2012

Revised: 01 November 2009

Received: 01 October 2006

Published in TALG Volume 9, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
675
Total Downloads

Downloads (Last 12 months)30
Downloads (Last 6 weeks)2

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tamaki H(2020)Experimental Analysis of TreewidthTreewidth, Kernels, and Algorithms10.1007/978-3-030-42071-0_15(214-221)Online publication date: 20-Apr-2020
https://doi.org/10.1007/978-3-030-42071-0_15
Čibej UFürst LMihelič J(2019)A Symmetry-Breaking Node Equivalence for Pruning the Search Space in Backtracking AlgorithmsSymmetry10.3390/sym1110130011:10(1300)Online publication date: 15-Oct-2019
https://doi.org/10.3390/sym11101300
Slavchev BMasliankova EKelk S(2019)A Machine Learning Approach to Algorithm Selection for Exact Computation of TreewidthAlgorithms10.3390/a1210020012:10(200)Online publication date: 20-Sep-2019
https://doi.org/10.3390/a12100200
Korhonen TBerg JJärvisalo M(2019)Solving Graph Problems via Potential Maximal CliquesACM Journal of Experimental Algorithmics10.1145/330129724(1-19)Online publication date: 18-Feb-2019
https://dl.acm.org/doi/10.1145/3301297
Tamaki H(2019)Positive-instance driven dynamic programming for treewidthJournal of Combinatorial Optimization10.1007/s10878-018-0353-z37:4(1283-1311)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s10878-018-0353-z
Tamaki H(2019)Computing Treewidth via Exact and Heuristic Lists of Minimal SeparatorsAnalysis of Experimental Algorithms10.1007/978-3-030-34029-2_15(219-236)Online publication date: 14-Nov-2019
https://doi.org/10.1007/978-3-030-34029-2_15
Jegou PKanso HTerrioux C(2018)On the Relevance of Optimal Tree Decompositions for Constraint Networks2018 IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI)10.1109/ICTAI.2018.00116(738-743)Online publication date: Nov-2018
https://doi.org/10.1109/ICTAI.2018.00116
Garraffa MShang LDella Croce FT'kindt V(2018)An exact exponential branch-and-merge algorithm for the single machine total tardiness problemTheoretical Computer Science10.1016/j.tcs.2018.05.040745(133-149)Online publication date: Oct-2018
https://doi.org/10.1016/j.tcs.2018.05.040
Kelk SStamoulis GWu T(2018)Treewidth distance on phylogenetic treesTheoretical Computer Science10.1016/j.tcs.2018.04.004731:C(99-117)Online publication date: 30-Jun-2018
https://dl.acm.org/doi/10.1016/j.tcs.2018.04.004
Benjumeda MBielza CLarrañaga P(2018)Tractability of most probable explanations in multidimensional Bayesian network classifiersInternational Journal of Approximate Reasoning10.1016/j.ijar.2017.10.02493(74-87)Online publication date: Feb-2018
https://doi.org/10.1016/j.ijar.2017.10.024
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents