Slightly Superexponential Parameterized Problems

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, the first natural goal is to make f ( k ) single-exponential, that is, c k 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 2 O ( 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. 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. More precisely we prove following tight lower bounds, for three natural problems, arising from three different domains: The pattern matching problem C losest S tring is known to be solvable in time 2 O ( d log d ) · n O (1) and 2 O ( d log |σ|) · n O (1). We show that there is no 2 o ( d log d ). · n O (1) and 2 o ( d log |σ|) · n O (1) time algorithm, unless Exponential Time Hypothesis (ETH) fails. The graph embedding problem D istortion, that is, deciding whether a graph G has a metric embedding into the integers with distortion at most d can be done in time 2 O ( d log d ) · n O (1). We show that there is no 2 o ( d log d ) · n O (1) time algorithm, unless ETH fails. The D isjoint P aths 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 ETH fails. To obtain our result 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 technical restrictions and could be of independent interest. We believe that many further results of this form can be obtained by using the framework of the current paper.

Authors

• Daniel Lokshtanov
• Dániel Marx
• Saket Saurabh 0001

Keywords

No keywords are indexed for this paper.