Slightly Superexponential Parameterized Problems

Abstract

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, the first natural goal is to make f(k) single-exponential, that is, ck for some constant c. This has led to the development of parameterized algorithms for various problems where f(k) appearing in their running time is of form 2O(k). However there are still plenty of problems where the “slightly superexponential” f(k) appearing in the best known running time has remained non single-exponential even after a lot of 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.