Dinur, Irit ;
Manurangsi, Pasin
ETHHardness of Approximating 2CSPs and Directed Steiner Network
Abstract
We study 2ary constraint satisfaction problems (2CSPs), 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 2CSPs 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 2CSPs to within a polynomial factor of both Sigma and V (i.e. (SigmaV)^Omega(1) factor). As a special case of the socalled 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 2CSPs to within a polynomial factor of V (while Sigma may be superpolynomial in Sigma)? Assuming the exponential time hypothesis (ETH), we answer this question positively: unless ETH fails, no polynomial time algorithm can approximate 2CSPs to within a factor of V^{1o(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 2CSPs.
Thanks to a known reduction [25, 16] from 2CSPs 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 GapETH, our reduction for 2CSPs 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.
BibTeX  Entry
@InProceedings{dinur_et_al:LIPIcs:2018:8367,
author = {Irit Dinur and Pasin Manurangsi},
title = {{ETHHardness of Approximating 2CSPs and Directed Steiner Network}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {36:136:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770606},
ISSN = {18688969},
year = {2018},
volume = {94},
editor = {Anna R. Karlin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8367},
URN = {urn:nbn:de:0030drops83670},
doi = {10.4230/LIPIcs.ITCS.2018.36},
annote = {Keywords: Hardness of Approximation, Constraint Satisfaction Problems, Directed Steiner Network, Parameterized Complexity}
}
2018
Keywords: 

Hardness of Approximation, Constraint Satisfaction Problems, Directed Steiner Network, Parameterized Complexity 
Seminar: 

9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Issue date: 

2018 
Date of publication: 

2018 