Slightly Superexponential Parameterized Problems

Abstract

A central problem in parameterized algorithms is to obtain algorithms with running time $f(k)\cdot 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\log 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.)

References in corpus (1)

• Randomized Algorithms for the Loop Cutset Problem

Cited by in corpus (8)

• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• Parameterized Algorithms for Matrix Completion With Radius Constraints
• Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation
• Lower Bounds for QBFs of Bounded Treewidth
• A subexponential parameterized algorithm for Directed Subset Traveling Salesman Problem on planar graphs
• Hitting minors on bounded treewidth graphs. I. General upper bounds
• Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
• Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth