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

DOI10.4230/LIPICS.ITCS.2018.36zbMATH Open1462.68068arXiv1805.03867OpenAlexW2964171575MaRDI QIDQ4993301FDOQ4993301

Authors: Irit Dinur, Pasin Manurangsi 

Publication date: 15 June 2021

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$.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)

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)