Near Optimal Constant Inapproximability under ETH for Fundamental Problems in Parameterized Complexity

Abstract

We prove that under the Exponential Time Hypothesis (ETH), for every ε > 0, there exists a constant C > 0 such that no algorithm running in time nk / logC k can determine whether a given 2-CSP instance with k variables, O(k) constraints, and alphabet size n, is perfectly satisfiable or if every assignment satisfies at most an ε fraction of the constraints. By known reductions in the literature, the above result implies near-optimal conditional lower bounds for approximating a host of parameterized problems, such as the k-Clique problem, k-Max-Coverage problem, k-Unique Set Cover problem, k-Median and k-Means problems, parameterized variants of the Nearest Codeword problem, Minimum Distance of a Code problem, Closest Vector problem, and Shortest Vector problem. We also establish a densification theorem for the parameterized 2-CSP problem, showing that the aforementioned conditional lower bound for sparse 2-CSPs also holds when the constraint graph is a complete graph. From this densification, we conclude that assuming ETH, there is no algorithm running in time n√k / logC k that approximates the k-Directed Steiner Network problem and the k-Strongly Connected Steiner Subgraph problem to some constant factors.