Solving connectivity problems parameterized by treewidth in single exponential time
Venue
Foundations of Computer Science 2011, Rynek Główny 12 (to appear)
Publication Year
2011
Authors
Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johann M. M. van Rooij, Jakub Onufry Wojtaszczyk
BibTeX
Abstract
For 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 c^tw
|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 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.
