We study the 2-ary constraint satisfaction problems (2-CSPs), which can be stated as follows: given a constraint graph G = ( V E ) , an alphabet set and, for each edge u v E , a constraint C u v , the goal is to find an assignment : V that satisfies as many constraints as possible, where a constraint C u v is said to be satisfied by if ( ( u ) ( v )) C u v .While the approximability of 2-CSPs is quite well understood when the alphabet size is constant, many problems are still open when 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 and V (i.e. ( V ) (1) factor). As a special case of what is now referred to as the Sliding Scale Conjecture, Bellare et al. (STOC, 1993) suggested that the answer to this question might be positive. Alas, despite many efforts by researchers to resolve this conjecture, it still remains open to this day.In this work, we separate between V and and ask a closely related but weaker question: is it hard to approximate 2-CSPs to within a polynomial factor of V (but while may be super-polynomial in V )? Assuming the exponential time hypothesis (ETH), we answer this question positively. Specifically, we show that, unless ETH fails, no polynomial time algorithm can approximate 2-CSPs to within a factor of V 1 ? 1 ( log V ) 1 2 ? for every 0" 0 . 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 from 2-CSPs to the Directed Steiner Network (DSN) problem (aka Directed Steiner Forest), 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 best known approximation ratio achieved by polynomial time algorithms due to Chekuri et al. (TALG, 2011) and Feldman et al. (JCSS, 2012), which yield O ( k 1 2+ ) -approximation for every constant 0" 0 .Additionally, if we assume a stronger assumption that there exists 0" 0 such that no subexponential time algorithm can distinguish a satisfiable 3-CNF formula from one which is not even (1 ? ) -satisfiable (aka Gap-ETH), then, for 2-CSPs, our reduction not only rules out polynomial time (i.e. ( V ) O (1) time) algorithms, but also fixed parameter tractable (FPT) algorithms parameterized by the number of variables V . These are algorithms with running time t ( V ) ( V ) O (1) where t can be any function. Similar improvements also apply for DSN parameterized by the number of demand pairs k .
展开▼
