On the existence of subexponential parameterized algorithms

摘要

The existence of subexponential-time parameterized algorithms is examined for various parameterized problems solvable in time O(2O(k)p(n)). It is shown that for each t⩾1, there are parameterized problems in FPT for which the existence of O(2o(k)p(n))-time parameterized algorithms implies the collapse of W[t] to FPT. Evidence is demonstrated that Max-SNP-hard optimization problems do not admit subexponential-time parameterized algorithms. In particular, it is shown that each Max-SNP-complete problem is solvable in time O(2o(k)p(n)) if and only if 3-SAT∈DTIME(2o(n)). These results are also applied to show evidence for the non-existence of O(2o(k)p(n))-time parameterized algorithms for a number of other important problems such as Dominating Set, Vertex Cover, and Independent Set on planar graph instances.