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

Authors Irit Dinur, Pasin Manurangsi



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.36.pdf
  • Filesize: 0.58 MB
  • 20 pages

Document Identifiers

Author Details

Irit Dinur
Pasin Manurangsi

Cite AsGet BibTex

Irit Dinur and Pasin Manurangsi. ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ITCS.2018.36

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.
Keywords
  • Hardness of Approximation
  • Constraint Satisfaction Problems
  • Directed Steiner Network
  • Parameterized Complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Amir Abboud and Greg Bodwin. Reachability preservers: New extremal bounds and approximation algorithms. CoRR, abs/1710.11250, 2017. URL: http://arxiv.org/abs/1710.11250.
  2. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501-555, may 1998. Google Scholar
  3. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70-122, 1998. Google Scholar
  4. Sanjeev Arora and Madhu Sudan. Improved low degree testing and its applications. In STOC, pages 485-495, 1997. Google Scholar
  5. Mihir Bellare, Shafi Goldwasser, Carsten Lund, and Alexander Russell. Efficient probabilistically checkable proofs and applications to approximations. In STOC, pages 294-304, 1993. Google Scholar
  6. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput., 36(4):889-974, 2006. Google Scholar
  7. Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, and Henning Stichtenoth. Constant rate PCPs for Circuit-SAT with sublinear query complexity. J. ACM, 63(4):32:1-32:57, 2016. Google Scholar
  8. Eli Ben-Sasson and Madhu Sudan. Short PCPs with polylog query complexity. SIAM J. Comput., 38(2):551-607, 2008. Google Scholar
  9. Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Approximation algorithms for spanner problems and directed steiner forest. Inf. Comput., 222:93-107, 2013. Google Scholar
  10. Edouard Bonnet, Bruno Escoffier, Eun Jung Kim, and Vangelis Th. Paschos. On subexponential and FPT-time inapproximability. Algorithmica, 71(3):541-565, 2015. Google Scholar
  11. Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From Gap-ETH to FPT-inapproximability: Clique, Dominating Set, and more. In FOCS, pages 743-754, 2017. Google Scholar
  12. Siu On Chan. Approximation resistance from pairwise-independent subgroups. J. ACM, 63(3):27:1-27:32, 2016. Google Scholar
  13. Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, and Ming Li. Approximation algorithms for directed steiner problems. J. Algorithms, 33(1):73-91, 1999. Google Scholar
  14. Moses Charikar, MohammadTaghi Hajiaghayi, and Howard J. Karloff. Improved approximation algorithms for label cover problems. Algorithmica, 61(1):190-206, 2011. Google Scholar
  15. Chandra Chekuri, Guy Even, Anupam Gupta, and Danny Segev. Set connectivity problems in undirected graphs and the directed steiner network problem. ACM Trans. Algorithms, 7(2):18:1-18:17, 2011. Google Scholar
  16. Rajesh Chitnis, Andreas Emil Feldmann, and Pasin Manurangsi. Parameterized approximation algorithms for directed steiner network problems. CoRR, abs/1707.06499, 2017. Google Scholar
  17. Eden Chlamtác, Michael Dinitz, Guy Kortsarz, and Bundit Laekhanukit. Approximating spanners and directed steiner forest: Upper and lower bounds. In SODA, pages 534-553, 2017. Google Scholar
  18. Irit Dinur. The PCP theorem by gap amplification. J. ACM, 54(3):12, 2007. Google Scholar
  19. Irit Dinur. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. ECCC, 23:128, 2016. Google Scholar
  20. Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, and Shmuel Safra. PCP characterizations of NP: Toward a polynomially-small error-probability. Computational Complexity, 20(3):413-504, 2011. Google Scholar
  21. Irit Dinur, Prahladh Harsha, and Guy Kindler. Polynomially low error PCPs with polyloglog n queries via modular composition. In STOC, pages 267-276, 2015. Google Scholar
  22. Irit Dinur and Tali Kaufman. High dimensional expanders imply agreement expanders. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 974-985. IEEE Computer Society, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.94.
  23. Irit Dinur and Inbal Livni Navon. Exponentially small soundness for the direct product z-test. In CCC, pages 29:1-29:50, 2017. Google Scholar
  24. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In STOC, pages 624-633, 2014. Google Scholar
  25. Yevgeniy Dodis and Sanjeev Khanna. Design networks with bounded pairwise distance. In STOC, pages 750-759, 1999. Google Scholar
  26. Moran Feldman, Guy Kortsarz, and Zeev Nutov. Improved approximation algorithms for directed steiner forest. J. Comput. Syst. Sci., 78(1):279-292, 2012. Google Scholar
  27. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, 2001. Google Scholar
  28. Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. New direct-product testers and 2-query pcps. SIAM J. Comput., 41(6):1722-1768, 2012. URL: http://dx.doi.org/10.1137/09077299X.
  29. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. Google Scholar
  30. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Google Scholar
  31. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319-357, 2007. Google Scholar
  32. Tamás Kővári, Vera T. Sós, and Pál Turán. On a problem of K. Zarankiewicz. Colloquium Mathematicae, 3(1):50-57, 1954. Google Scholar
  33. Pasin Manurangsi. Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. In STOC, pages 954-961, 2017. Google Scholar
  34. Pasin Manurangsi and Prasad Raghavendra. A birthday repetition theorem and complexity of approximating dense CSPs. CoRR, abs/1607.02986, 2016. Google Scholar
  35. Dana Moshkovitz. Low-degree test with polynomially small error. Computational Complexity, 26(3):531-582, 2017. Google Scholar
  36. Dana Moshkovitz and Ran Raz. Sub-constant error probabilistically checkable proof of almost-linear size. Computational Complexity, 19(3):367-422, 2010. Google Scholar
  37. Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? In STOC, pages 245-254, 2008. Google Scholar
  38. Ran Raz. A parallel repetition theorem. SIAM J. Comput., 27(3):763-803, 1998. Google Scholar
  39. Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In STOC, pages 475-484, 1997. Google Scholar
  40. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail