Hans L. Bodlaender
Fedor V. Fomin
Arie M. C. A. Koster
Skip Abstract Section
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*(2n). 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*(4n) algorithm that requires polynomial space. We also show that with a more complicated algorithm using balanced separators, Treewidth can be computed in O*(2.9512n) time and polynomial space.
- 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. Google Scholar
Digital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Bodlaender, H. L. 1998. A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209, 1--45. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Bodlaender, H. L., and Koster, A. M. C. A. 2010. Treewidth computations I. Upper bounds. Inf. Computat. 208, 259--275. Google ScholarDigital Library
- Bodlaender, H. L., and Koster, A. M. C. A. 2011. Treewidth computations II. Lower bounds. Inf. Computat. 209, 1103--1119. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Bodlaender, H. L., Koster, A. M. C. A., and Wolle, T. 2006. Contraction and treewidth lower bounds. J. Graph Algor. Appl. 10, 5--49.Google ScholarCross Ref
- Boost 1999--2009. Boost C++ libraries. http://www.boost.org/.Google Scholar
- Bouchitté, V., and Todinca, I. 2001. Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput. 31, 212--232. Google ScholarDigital Library
- Bouchitté, V., and Todinca, I. 2002. Listing all potential maximal cliques of a graph. Theoret. Comput. Sci. 276, 17--32. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- Fomin, F. V. and Villanger, Y. 2012. Treewidth computation and extremal combinatorics. Combinatorica 32, 3, 289--308.Google ScholarCross Ref
- Fulkerson, D. R. and Gross, O. A. 1965. Incidence matrices and interval graphs. Pac. J. Math. 15, 835--855.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Golumbic, M. C. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York.Google Scholar
- Gurevich, Y. and Shelah, S. 1987. Expected computation time for Hamiltonian path problem. SIAM J. Comput. 16, 486--502. Google ScholarDigital Library
- Held, M. and Karp, R. 1962. A dynamic programming approach to sequencing problems. J. SIAM 10, 196--210.Google Scholar
- Kitsunai, K., Kobayashi, Y., Komuro, K., Tamaki, H., and Tano, T. 2012. Computing directed pathwidth in O(1.89n) 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Koster, A. M. C. A. 2009. ComputeTW -- An interactive platform for computing treewidth of graphs. http://www.math2.rwth-aachen.de/~koster/ComputeTW.Google Scholar
- 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. Google ScholarDigital Library
- Rose, D. J., Tarjan, R. E., and Lueker, G. S. 1976. Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5, 266--283.Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Suchan, K. and Villanger, Y. 2009. Computing pathwidth faster than 2n. In Proceedigs of the International Workshop on Parameterized and Exact Computaion (IWPEC 2009). Lecture Notes in Computer Science, vol. 5917, Springer, 324--335. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- TreewidthLib. 2004. Treewidthlib. http://www.cs.uu.nl/people/hansb/treewidthlib.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
Index Terms
- On exact algorithms for treewidth
Recommendations
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 ...
Restricted space algorithms for isomorphism on bounded treewidth graphs
The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time. We give restricted space algorithms for these problems proving the following results:*Isomorphism for ...
Comments