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 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. More precisely we prove following tight lower bounds, for four natural problems, arising from three different domains: • In the Closest String problem, given strings s 1 , . . . , s t over an alphabet Σ of length L each, and an integer d, the question is whether there exists a string s over Σ of length L, such that its hamming distance from each of the strings s i , 1 ≤ i ≤ t, is at most d. The pattern matching problem Closest String is known to be solvable in time 2 1) time algorithms, unless the Exponential Time Hypothesis (ETH) fails. • The graph embedding problem Distortion, that is, deciding whether a graph G has a metric embedding into the integers with distortion at most d can be solved in time 2 1) time algorithm, unless the ETH fails. • The Disjoint Paths problem can be solved in time in time 2 O(w log w) · n O(1) on graphs of treewidth at most w. We show that there is no 2 o(w log w) · n O(1) time algorithm, unless the ETH fails. • The Chromatic Number problem can be solved in time in time 2 O(w log w) · n on graphs of treewidth at most w. We show that there is no 2 o(w log w) · n O(1) time algorithm, unless the ETH fails. To obtain our results, we first prove the lower bound for variants of basic problems: finding cliques, independent sets, and hitting sets. These artificially constrained variants form a good starting point for proving lower bounds on natural problems without any * A preliminary version of the paper appeared in the proceedings of SODA 2011. technical restrictions and could be of independent interest. Several follow up works have already obtained tight lower bounds by using our framework, and we believe it will prove useful in obtaining even more lower bounds in the future.
A nearly-matching lower bound on the running time (assuming ETH) was obtained by Lokshtanov et al. REF .
Slightly Superexponential Parameterized Problems
SIAM Journal on Computing, 2018
Computer Science Mathematics