Slightly Superexponential Parameterized Problems
share
A central problem in parameterized algorithms is to obtain algorithms with running time f(k)· n^O(1) such that f is as slow growing function of the parameter k as possible. In particular, a large number of basic parameterized problems admit parameterized algorithms where f(k) is single-exponential, that is, c^k for some constant c, which makes aiming for such a running time a natural goal for other problems as well. However there are still plenty of problems where the f(k) appearing in the best known running time is worse than single-exponential and it remained "slightly superexponential" even after serious attempts to bring it down. A natural question to ask is whether the f(k) appearing in the running time of the best-known algorithms is optimal for any of these problems. In this paper, we examine parameterized problems where f(k) is k^O(k)=2^O(k k) in the best known running time and for a number of such problems, we show that the dependence on k in the running time cannot be improved to single exponential. (See paper for the longer abstract.)
READ FULL TEXT