ETH-hardness of approximating 2-CSPs and directed Steiner network

DOI10.4230/LIPICS.ITCS.2018.36MaRDI QIDQ4993301zbMATH OpenOpenAlexFDO

Authors Irit Dinur, Pasin Manurangsi

Publication date 15 June 2021

Full work available at URL https://arxiv.org/abs/1805.03867

zbMATH Keywords

constraint satisfaction problemsparameterized complexityhardness of approximationdirected Steiner network

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: 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 $Sigma$ and, for each $u,vinE$, a constraint $C_{uv}subseteqSigmaimesSigma$, the goal is to find an assignment $sigma:VoSigma$ that satisfies as many constraints as possible, where a constraint $C_{uv}$ is satisfied if $(sigma(u),sigma(v))in{C}_{uv}$. While the approximability of 2-CSPs is quite well understood when $|Sigma|$ is constant, many problems are still open when $|Sigma|$ becomes super constant. One such problem is whether it is hard to approximate 2-CSPs to within a polynomial factor of $|Sigma||V|$. Bellare et al. (1993) suggested that the answer to this question might be positive. Alas, despite efforts to resolve this conjecture, it remains open to this day. In this work, we separate $|V|$ and $|Sigma|$ and ask a 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 $|V|$)? Assuming the exponential time hypothesis (ETH), we answer this question positively by showing that no polynomial time algorithm can approximate 2-CSPs to within a factor of $|V{|}^{1-o(1)}$. Note that our ratio is almost linear, which is almost optimal as a trivial algorithm gives a $|V|$-approximation for 2-CSPs. Thanks to a known reduction, our result implies an ETH-hardness of approximating Directed Steiner Network with ratio $k^{1/4-o(1)}$ where $k$ is the number of demand pairs. The ratio is roughly the square root of the best known ratio achieved by polynomial time algorithms (Chekuri et al., 2011; Feldman et al., 2012). Additionally, under Gap-ETH, our reduction for 2-CSPs not only rules out polynomial time algorithms, but also FPT algorithms parameterized by $|V|$. Similar statement applies for DSN parameterized by $k$.

Recommendations

• scientific article; zbMATH DE number 2019637
• 2 CSPs all are approximable within a constant differential factor
• Towards sharp inapproximability for any 2-CSP
• Is constraint satisfaction over two variables always easy?
• Approximation of non-Boolean 2CSP

Cites work

• scientific article; zbMATH DE number 5485536 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 1559564 (Why is no real title available?)
• A Parallel Repetition Theorem
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Analytical approach to parallel repetition
• Approximating spanners and directed Steiner forest: upper and lower bounds
• Approximation Algorithms for Directed Steiner Problems
• Approximation algorithms for spanner problems and directed Steiner forest
• Approximation resistance from pairwise independent subgroups
• Constant rate PCPs for circuit-SAT with sublinear query complexity
• Design networks with bounded pairwise distance
• Efficient probabilistically checkable proofs and applications to approximations
• Exponentially small soundness for the direct product Z-test
• Improved approximation algorithms for directed Steiner forest
• Improved approximation algorithms for label cover problems
• Low-degree test with polynomially small error
• New direct-product testers and 2-query PCPs
• On a problem of K. Zarankiewicz
• On the complexity of \(k\)-SAT
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• PCP characterizations of NP: toward a polynomially-small error-probability
• Polynomially low error PCPs with \(\operatorname{polyloglog} n\) queries via modular composition
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Reachability preservers: new extremal bounds and approximation algorithms
• Robust Characterizations of Polynomials with Applications to Program Testing
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• Short PCPs with Polylog Query Complexity
• Some optimal inapproximability results
• Sub-constant error probabilistically checkable proof of almost-linear size
• The PCP theorem by gap amplification
• Which problems have strongly exponential complexity?

Cited in

(7)

• An ETH-tight algorithm for bidirected Steiner connectivity
• Imperfect gaps in Gap-ETH and PCPs
• A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems
• Parameterized approximation algorithms for bidirected Steiner network problems
• Complexity of the Steiner Network Problem with Respect to the Number of Terminals
• Parameterized inapproximability of independent set in \(H\)-free graphs
• scientific article; zbMATH DE number 7650083 (Why is no real title available?)

This page was built for publication: ETH-hardness of approximating 2-CSPs and directed Steiner network

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993301)