Paper Info
Title
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
Abstract
AbstractFor the vast majority of local problems on graphs of small treewidth (where, by local we mean that a solution can be verified by checking separately the neighbourhood of each vertex), standard dynamic programming techniques give ctw |V|O(1) time algorithms, where tw is the treewidth 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 twtw time.We bridge this gap by introducing a technique we named Cut&Count that allows to produce ctw |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 all these fields we are able to improve the best-known results for some problems. Also, looking from a more theoretical perspective, our results are surprising since the equivalence relation that partitions all partial solutions with respect to extendability to global solutions seems to consist of at least twtw equivalence classes for all these problems. Our results answer an open problem raised by Lokshtanov, Marx and Saurabh [SODA’11].In contrast to the problems aimed at minimizing 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 bridged for some problems that aim to maximize the number of connected components like Cycle Packing .
Year
DOI
Venue
2022
10.1145/3506707
ACM Transactions on Algorithms
Keywords
DocType
Volume
Treewidth, connectivity problems, feedback vertex set, steiner tree, hamilton path/cycle, Isolation Lemma
Journal
18
Issue
ISSN
Citations 
2
1549-6325
0
PageRank 
References 
Authors
0.34
0
6
Name
Order
Citations
PageRank
Marek Cygan155640.52
Jesper Nederlof200.34
Marcin Pilipczuk343647.86
michal pilipczuk440351.93
Johan M. M. Van Rooij500.34
Jakub Onufry Wojtaszczyk600.34