Cut&count technique for connectivity problems parameterized by treewidth

Speaker(s)

Marek Cygan

Affiliation

Uniwersytet Warszawski

Date

April 21, 2011, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

The notion of treewidth, introduced in 1984 by Robertson and Seymour, has in many cases proved to be a good measure of the intrinsic difficulty of various NP-hard problems on graphs, and a useful tool for attacking those problems. Many of them can be efficiently solved through dynamic programming if we assume the input graph to have bounded treewidth. For several problems with
global connectivity requirement the best known algorithms were of t^O(t) n^O(1) time complexity, where t is the width of the given tree decomposition. We present a technique named Cut&Count that allows us to produce c^t n^O(1) Monte Carlo algorithms for most connectivity type problems, including Hamiltonian Path, Feedback Vertex Set and Connected Dominating Set. The constant c we obtain 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. Our results have numerous consequences in various fields, like FPT algorithms, exact and approximate  algorithms on planar and H-minor-free graphs and
algorithms on graphs of bounded degree. In all these fields we are able to improve the best-known results for some problems.

This is a joint work with Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan van Rooij, Jakub Onufry Wojtaszczyk.

---