ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network

Abstract

We study 2-ary constraint satisfaction problems (2-CSPs), which can be stated as follows: given a constraint graph G = (V,E), an alphabet set Sigma and, for each edge {u, v}, a constraint C_uv, the goal is to find an assignment sigma from V to Sigma that satisfies as many constraints as possible, where a constraint C_uv is said to be satisfied by sigma if C_uv contains (sigma(u),sigma(v)).

While the approximability of 2-CSPs is quite well understood when the alphabet size |Sigma| is constant (see e.g. [37]), many problems are still open when |Sigma| becomes super constant. One open problem that has received significant attention in the literature is whether it is hard to approximate 2-CSPs to within a polynomial factor of both |Sigma| and |V| (i.e. (|Sigma||V|)^Omega(1) factor). As a special case of the so-called Sliding Scale Conjecture, Bellare et al. [5] suggested that the answer to this question might be positive. Alas, despite many efforts by researchers to resolve this conjecture (e.g. [39, 4, 20, 21, 35]), it still remains open to this day.

In this work, we separate |V| and |Sigma| and ask a closely related but weaker question: is it hard to approximate 2-CSPs to within a polynomial factor of |V| (while |Sigma| may be super-polynomial in |Sigma|)? Assuming the exponential time hypothesis (ETH), we answer this question positively: unless ETH fails, no polynomial time algorithm can approximate 2-CSPs to within a factor of |V|^{1-o(1)}. Note that our ratio is not only polynomial but also almost linear. This is almost optimal since a trivial algorithm yields an O(|V|)-approximation for 2-CSPs.

Thanks to a known reduction [25, 16] from 2-CSPs to the Directed Steiner Network (DSN) problem, our result implies an inapproximability result for the latter with polynomial ratio in terms of the number of demand pairs. Specifically, assuming ETH, no polynomial time algorithm can approximate DSN to within a factor of k^{1/4 - o(1)} where k is the number of demand pairs. The ratio is roughly the square root of the approximation ratios achieved by best known polynomial time algorithms [15, 26], which yield O(k^{1/2 + epsilon})-approximation for every constant epsilon > 0.

Additionally, under Gap-ETH, our reduction for 2-CSPs not only rules out polynomial time algorithms, but also fixed parameter tractable (FPT) algorithms parameterized by the number of variables |V|. These are algorithms with running time g(|V|)·|Sigma|^O(1) for some function g. Similar improvements apply for DSN parameterized by the number of demand pairs k.