Cut&Count technique for graph connectivity problems parameterized by treewidth
Marek Cygan · 2011
For the vast majority of local algorithmic problems on graphs of small treewidth (where by local we mean that a solution can be verified by checking the neighbourhood of each vertex separately), 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 tw time. In this dissertation we breach this gap by introducing a novel technique we named Cut&Count that allows to produce ctw|V |O(1) time Monte Carlo algorithms for most connectivity-type problems, including HAMILTONIAN CYCLE, STEINER TREE, FEEDBACK VERTEX SET and CONNECTED VERTEX COVER. 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. In all these fields we are able to improve the bestknown 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 consists of at least tw equivalence classes for all these problems. 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. The constant c in our algorithms is in all cases small (at most 4 for undirected problems and at most 6 for directed ones), and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail.