Abstract
It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in \(2^{\mathcal{O}(\mathtt{tw})}n^{\mathcal{O}(1)}\) time for graphs with a given tree decomposition of width tw. However, for nonlocal problems, like the fundamental class of connectivity problems, for a long time it was unknown how to do this faster than \(\mathtt{tw}^{\mathcal{O}(\mathtt{tw})}n^{\mathcal{O}(1)}\) until recently, when Cygan et al. (FOCS 2011) introduced the Cut&Count technique that gives randomized algorithms for a wide range of connectivity problems running in time \(c^{\mathtt{tw}}n^{\mathcal{O}(1)}\) for a small constant c.
In this paper, we show that we can improve upon the Cut&Count technique in multiple ways, with two new techniques. The first technique (rank-based approach) gives deterministic algorithms with O(c tw n) running time for connectivity problems (like Hamiltonian Cycle and Stei-ner Tree) and for weighted variants of these; the second technique (determinant approach) gives deterministic algorithms running in time \(c^{\mathtt{tw}}n^{\mathcal{O}(1)}\) for counting versions, e.g., counting the number of Hamiltonian cycles for graphs of treewidth tw.
The rank-based approach introduces a new technique to speed up dynamic programming algorithms which is likely to have more applications. The determinant-based approach uses the Matrix Tree Theorem for deriving closed formulas for counting versions of connectivity problems; we show how to evaluate those formulas via dynamic programming.
The second author is partially supported by NCN grant DEC-2012/05/D/ST6/03214 and Foundation for Polish Science. Part of the work of the third author was done at Utrecht University supported by the Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO), project: ’KERNELS’. The fourth author is supported by the NWO project ’Space and Time Efficient Structural Improvements of Dynamic Programming Algorithms’.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Hamiltonian Cycle
- Dynamic Programming Algorithm
- Deterministic Algorithm
- Tree Decomposition
- Internal Vertex
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aigner, M., Ziegler, G.: Proofs from the book, Berlin, Germany (2010)
Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844–856 (1995)
Björklund, A.: Determinant sums for undirected Hamiltonicity. In: FOCS, pp. 173–182 (2010)
Björklund, A., Husfeldt, T., Taslaman, N.: Shortest cycle through specified elements. In: Rabani, Y. (ed.) SODA, pp. 1747–1753. SIAM (2012)
Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time. CoRR, abs/1211.1505 (2012)
Cao, Y., Chen, J., Liu, Y.: On feedback vertex set new measure and new structures. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol. 6139, pp. 93–104. Springer, Heidelberg (2010)
Cygan, M., Kratsch, S., Nederlof, J.: Fast Hamiltonicity checking via bases of perfect matchings (2012) (to appear at STOC 2013)
Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: FOCS, pp. 150–159 (2011)
Dorn, F., Fomin, F.V., Thilikos, D.M.: Catalan structures and dynamic programming in H-minor-free graphs. J. Comput. Syst. Sci. 78(5), 1606–1622 (2012)
Eppstein, D.: The traveling salesman problem for cubic graphs. J. Graph Algorithms Appl. 11(1), 61–81 (2007)
Göös, M., Suomela, J.: Locally checkable proofs. In: PODC, pp. 159–168 (2011)
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. (2001)
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512–530 (2001)
Kleinberg, J., Tardos, É.: Algorithm Design (2005)
Koutis, I.: Faster algebraic algorithms for path and packing problems. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 575–586. Springer, Heidelberg (2008)
Koutis, I., Williams, R.: Limits and applications of group algebras for parameterized problems. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 653–664. Springer, Heidelberg (2009)
Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. In: SODA, pp. 777–789 (2011)
Lovász, L.: On determinants, matchings, and random algorithms. In: FCT, pp. 565–574 (1979)
Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica 7(1), 105–113 (1987)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms (2002)
Raz, R., Spieker, B.: On the ”log rank”-conjecture in communication complexity. Combinatorica 15(4), 567–588 (1995)
Robertson, N., Seymour, P.D.: Graph minors. III. Planar tree-width. J. Comb. Theory 36(1), 49–64 (1984)
Williams, R.: Finding paths of length k in \(\mathcal{O}^\star(2^{k}\)) time. Inf. Process. Lett. 109(6), 315–318 (2009)
Williams, V.V.: Multiplying matrices faster than coppersmith-winograd. In: STOC, pp. 887–898 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J. (2013). Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds) Automata, Languages, and Programming. ICALP 2013. Lecture Notes in Computer Science, vol 7965. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39206-1_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-39206-1_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39205-4
Online ISBN: 978-3-642-39206-1
eBook Packages: Computer ScienceComputer Science (R0)