Source-linked AI summary
Slightly Superexponential Parameterized Problems
Daniel Lokshtanov, Daniel Marx, Saket Saurabh
TL;DR
The paper asks whether parameterized problems with best-known dependence 2^{O(k log k)} can be improved to single-exponential dependence. It develops lower bounds from constrained basic problems and transfers them to four natural problems, showing that such improvements would violate ETH. The paper also notes that some other slightly superexponential algorithms may still be improvable.
Problem
The paper addresses whether the 2^{O(k log k)} dependence in best-known algorithms for some parameterized problems is optimal or can be reduced to single-exponential dependence.
Method
The paper proves lower bounds for constrained clique, independent-set, and hitting-set variants, then uses them to establish tight bounds for natural problems across three domains.
Results
Under ETH, no 2^{o(k log k)} algorithms exist for the studied problems, including Closest String, Distortion, Disjoint Paths, and Chromatic Number with their respective parameters.
Takeaways & Limitations
For these four well-studied problems, the known slightly superexponential dependence is optimal under ETH rather than merely an artifact of current algorithm design.
Takeaways & Limitations
The paper explicitly leaves open the possibility that some other 2^{O(k log k)} algorithms can be improved to single-exponential dependence.
Abstract
from arXiv · showhide
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.)
1 Introduction
The paper studies parameterized problems with slightly superexponential dependence 2^{O(k log k)} and proves that, for several natural problems, improving this to single-exponential dependence would violate ETH.
- 1 Introduction: The paper identifies problems where the known 2^{O(k log k)} parameter dependence is inherent unless ETH fails.This challenges the assumption that every natural FPT problem should eventually admit c^k dependence.
- 1 Introduction: The proof first establishes lower bounds for constrained clique, independent-set, and hitting-set variants whose search spaces have size 2^{O(k log k)}.These basic results are then used as a starting point for lower bounds on natural problems without technical restrictions.
- 1 Introduction: Four natural problems—Closest String, Distortion, Disjoint Paths, and Chromatic Number—have no corresponding 2^{o(k log k)} algorithms under ETH.The lower bounds use d for the first two problems and treewidth w for the latter two.
- 1 Introduction: Closest String has no 2^{o(d log d)} or 2^{o(d log |Σ|)} algorithm under ETH, matching its known 2^{O(d log d)} and 2^{O(d log |Σ|)} algorithms.The problem asks whether one string lies within Hamming distance d of every input string.
- 1 Introduction: Distortion has no 2^{o(d log d)} algorithm under ETH, matching the known 2^{O(d log d)} algorithm for embedding graph metrics into the integers.The parameter d bounds the embedding distortion.
- 1 Introduction: Disjoint Paths and Chromatic Number on graphs of treewidth w have no 2^{o(w log w)} algorithms under ETH, matching their known 2^{O(w log w)} algorithms.These results extend the lower-bound pattern across two treewidth-parameterized problems.
2 Basic problems
The section develops constrained clique, independent-set, and hitting-set variants whose 2^{O(k log k)} brute-force search is ETH-tight, then uses them as starting points for natural problem lower bounds.
- 2 Basic problems: Selecting one element from every row of a k × k table yields a search space of k^k = 2^{O(k log k)}, with permutation variants also selecting one per column.These constrained variants provide the core lower-bound framework for later reductions.
- 2 Basic problems: 2^{o(k log k)}-time algorithms are ruled out under ETH for k × k Clique and k × k Permutation Clique.Permutation Clique is obtained through randomized reordering, with repetition reducing the probability of rejecting a yes-instance.
- 2.1 k × k Clique: The reductions encode 3-Coloring by partitioning a graph into k groups and representing each group's proper colorings as row vertices.Compatible local colorings become adjacent, so a row-respecting clique corresponds to a proper global coloring; k log k = O(n) preserves subexponential contradiction.
3 Closest String
Closest String asks for a center string within Hamming distance d of every input string. The section shows that its known slightly superexponential dependence on d, or on alphabet size, cannot generally be reduced to single exponential under ETH.
- 3 Closest String: Closest String asks whether a length-L center string has Hamming distance at most d from each of t input strings over alphabet Σ.Hamming distance counts positions with different characters.
- 3 Closest String: No 2^{o(d log d)}·|I|^{O(1)} or 2^{o(d log |Σ|)}·|I|^{O(1)} algorithm exists for Closest String unless ETH fails.The result matches the known 2^{O(d log d)} and 2^{O(d log |Σ|)} upper bounds in the relevant parameters.
- 3 Closest String: The lower bound reduces k × k Hitting Set to Closest String using alphabet [2k + 1], string length k, and d = k − 1.With d = k − 1, the center string must share at least one character with every input string.
- 3 Closest String: The constructed Closest String instance has a solution exactly when the original Hitting Set instance has one.A hitting-set selection becomes the center string, and conversely an unused alphabet character allows extraction of a row-wise selection.
- 3 Closest String: Because the constructed instance is polynomial in k and m, a faster Closest String algorithm would yield a 2^{o(k log k)} algorithm for k × k Hitting Set, contradicting ETH.This transfers the lower bound from the constrained Hitting Set problem to both parameter dependences of Closest String.
4 Distortion
This section proves that Distortion cannot be solved in time 2^o(d log d) · n^O(1) under ETH, matching the known d^O(d) dependence. The lower bound is obtained by reducing Constrained Permutation to Distortion.
- Problem and context: The known exact algorithm for Distortion runs in time d^O(d) · n, and the section shows this parameter dependence is optimal under ETH.The problem asks for an embedding into the integers whose distances have distortion at most d.
- Intermediate problem: Constrained Permutation asks for a permutation of [k] containing neighboring pairs from every set S_i.Two values are neighbors when they are consecutive in the permutation.
- Intermediate problem: Assuming ETH, Constrained Permutation has no 2^o(k log k) m^O(1) time algorithm.This lower bound is established before transferring it to Distortion.
- Reduction construction: The reduction constructs an equivalent Constrained Permutation instance with k′ = 24k using row and column elements arranged into constrained groups.The construction introduces elements r^ℓ_i and c^ℓ_j and several groups of sets.
- Lower bound: Assuming ETH, Distortion has no 2^o(d log d) · n^O(1) time algorithm.The section presents this as Theorem 4.2.
- Reduction consequence: A faster Distortion algorithm would solve Constrained Permutation in 2^o(k log k) · (km)^O(1) time, contradicting the ETH-based lower bound.The constructed graph has polynomially many vertices in k and m.
5 Disjoint Paths
This section proves an ETH-based 2^o(w log w) lower bound for Disjoint Paths parameterized by treewidth. The proof transfers a lower bound from Hitting Set through directed disjoint paths and a gadget encoding set-hitting choices.
- Reduction strategy: The reduction first proves the same lower bound for Directed Disjoint Paths parameterized by pathwidth, then transfers it to undirected Disjoint Paths.The resulting lower bound also applies when parameterized by treewidth.
- Gadget construction: Each gadget G_k,S contains row vertices, paths P_i, auxiliary vertices, and source-target edges corresponding to pairs in S.Its demands include (a_i, c_i,k), auxiliary pairs, and (s,t).
- Gadget behavior: A gadget solution represents a mapping ρ by selecting exactly one vertex v_i,ρ(i) in every row.The construction forces the selected mapping to hit S, while the complementary path vertices are used by other demands.
- Global reduction: The Hitting Set instance is encoded by chaining m gadgets, identifying selected vertices of one gadget with complementary vertices of the next.This produces the Directed Disjoint Paths instance.
- Parameter preservation: The constructed graph has pathwidth O(k), and the reduction establishes equivalence between the source instance and the directed disjoint-paths instance.A subsequent reduction from directed to undirected paths yields the stated treewidth lower bound.
- Lower bound: Assuming ETH, Disjoint Paths has no 2^o(w log w) · n^O(1) time algorithm.This matches the known 2^O(w log w) · n algorithm dependence.
6 Chromatic Number
The paper proves that Chromatic Number remains slightly superexponential when parameterized by treewidth and even by vertex cover, via a reduction from k × k Permutation Clique.
- Treewidth parameterization: For graphs of treewidth w, the known w^O(w) · n^O(1) algorithm for Chromatic Number is optimal up to the exponent's constant factors.The paper states that this running time cannot be improved to 2^o(w log w) · n^O(1) unless the ETH fails.
- Vertex-cover parameterization: The construction has vertex cover C_a ∪ C_b of size 2k, so a faster Chromatic Number algorithm would contradict the ETH-based lower bound for Permutation Clique.The constructed graph has polynomially many vertices in k.
- Vertex-cover parameterization: Assuming the ETH, Chromatic Number parameterized by vertex cover number has no 2^o(k log k) · n^O(1)-time algorithm.The reduction constructs graphs with vertex cover size at most 2k.
- Reduction: The reduction represents a k × k Permutation Clique instance using two k-vertex cliques and auxiliary vertices for nonedges.The target graph contains cliques C_a and C_b, plus vertices w^ij_xy associated with incompatible choices.
- Reduction: A permutation clique yields a proper k-coloring by assigning distinct row and permutation colors to the two cliques and extending the coloring to auxiliary vertices.The reverse direction extracts a permutation from the colors on C_b and derives the required clique.
7 Conclusion
The conclusion establishes tight slightly superexponential lower bounds for four parameterized problems and argues that this framework can guide further optimality studies. It also records subsequent developments that answered several proposed questions.
- Main results: Assuming the ETH, no 2^o(d log d) · |I|^O(1) or 2^o(d log |Σ|) · |I|^O(1) algorithm exists for Closest String, and no 2^o(w log w) · |I|^O(1) algorithm exists for Distortion, Disjoint Paths, or treewidth-parameterized Chromatic Number.These lower bounds match the known slightly superexponential dependence on the relevant parameters.
- Open questions: The authors suggest applying their framework to determine whether Point Line Cover and Directed Feedback Vertex Set have optimal 2^O(k log k) · |I|^O(1) algorithms.These are presented as open questions in the conclusion.
- Subsequent developments: Subsequent work showed that Interval Completion admits a single-exponential 6^k · n^O(1) algorithm, resolving that proposed optimality question negatively.The conclusion notes that later work also obtained a k^O(k) · n^O(1) algorithm.
- Subsequent developments: Cut & Count and later deterministic algorithms established 2^O(w) · |I|^O(1) algorithms for Hamiltonian Path, Connected Vertex Cover, and Connected Dominating Set.These results answer another group of questions raised by the paper.
- Impact: The paper helped motivate broader investigation of whether 2^O(k log k) · n^O(1) algorithms can be improved to single-exponential time or matched by lower bounds.The conclusion connects this perspective to later work on bounded-treewidth and graph-modification problems.