Abstract
In a vertex subset problem we are given as input a universe U of size n, and a family F of subsets of the universe defined implicitly from the input. The task is to find a subset S in F of smallest possible size. For an example the Vertex Cover problem is a subset problem where input is a graph G, the universe is the vertex set of G, and the family F is the family of all vertex covers of G. Here a vertex set S is a vertex cover of G if every edge of G has at least one endpoint in S. Many problems, such as Vertex Cover, Feedback Vertex Set, Hitting Set and Minimum Weight Satisfiability can be formalized as vertex subset problems. The trivial algorithm for such problems runs in time 2^n. We show that (essentially) any vertex subset problem that admits an FPT algorithm with running time c^kn^O(1), where c is a constant and k is the size of the optimal solution, also admits an algorithm with running time (2-1/c)^n. In one stroke this theorem improves the best known exact exponential time algorithms for a number of problems, and gives tighter combinatorial bounds for several well-studied objects. The most natural variant of our algorithm is randomized, we also show how to get a deterministic algorithm with the same running time bounds, up to a sub-exponential factor in the running time. Our de-randomization relies on a new pseudo-random construction that may be of independent interest.
(Joint work with Serge Gaspers, Fedor Fomin and Saket Saurabh)