Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

By Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, J. M. M. Van Rooij, Jakub Onufry Wojtaszczyk. IEEE Annual Symposium on Foundations of Computer Science, 2011

371 citations recorded by the source corpus.

For the vast majority of local problems on graphs of small tree width (where by local we mean that a solution can be verified by checking separately the neighbourhood of each vertex), standard dynamic programming techniques give c^tw |V|^O(1) time algorithms, where tw is the tree width of the input graph G = (V, E) and c is a constant. On the other hand, for problems with a global requirement (usually connectivity) the best -- known algorithms were naive dynamic programming schemes running in at least tw^tw time. We breach this gap by introducing a technique we named Cut&Count that allows to produce c^tw |V|^O(1) time Monte Carlo algorithms for most connectivity-type problems, including Hamiltonian Path, Steiner Tree, Feedback Vertex Set and Connected Dominating Set. These results have numerous consequences in various fields, like parameterized complexity, exact and approximate algorithms on planar and H-minor-free graphs and exact algorithms on graphs of bounded degree. The constant c in our algorithms is in all cases small, and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. In contrast to the problems aiming to minimize the number of connected components that we solve using Cut&Count as mentioned above, we show that, assuming the Exponential Time Hypothesis, the aforementioned gap cannot be breached for some problems that aim to maximize the number of connected components like Cycle Packing.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/df998286880a6a9c349feb94795e991f6c595c2f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems (2014, background): “Some other work that proves conditional lower bounds based on the SETH for NP-hard problems includes [25, 19, 28, 63, 27, 92, 71, 24, 26, 36].”
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth (2013, methodology): “Although this matrix has dimensions of order 2 θ ( | U | log | U | ) , we exploit a simple factorization in GF(2) of matrices with inner dimension 2 | U | using an idea of [8].”