Slightly Superexponential Parameterized Problems

A central problem in parameterized algorithms is to obtain algorithms with running time f(k)· nO(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, ck 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 kO(k)=2O(klog 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.)