Document Open Access Logo

Syntactic Separation of Subset Satisfiability Problems

Authors Eric Allender, Martín Farach-Colton, Meng-Tsung Tsai

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2019.16.pdf
  • Filesize: 0.64 MB
  • 23 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • Syntactic Class
  • Exponential Time Hypothesis
  • APX
  • PTAS

Metrics

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

Abstract

Variants of the Exponential Time Hypothesis (ETH) have been used to derive lower bounds on the time complexity for certain problems, so that the hardness results match long-standing algorithmic results. In this paper, we consider a syntactically defined class of problems, and give conditions for when problems in this class require strongly exponential time to approximate to within a factor of (1-epsilon) for some constant epsilon > 0, assuming the Gap Exponential Time Hypothesis (Gap-ETH), versus when they admit a PTAS. Our class includes a rich set of problems from additive combinatorics, computational geometry, and graph theory. Our hardness results also match the best known algorithmic results for these problems.

Cite As Get BibTex

Eric Allender, Martín Farach-Colton, and Meng-Tsung Tsai. Syntactic Separation of Subset Satisfiability Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.16

Author Details

Eric Allender
  • Rutgers University, Piscataway, NJ 08854, USA
Martín Farach-Colton
  • Rutgers University, Piscataway, NJ 08854, USA
Meng-Tsung Tsai
  • National Chiao Tung University, Hsinchu, Taiwan

Funding

  • Allender, Eric: This research was supported in part by NSF grant CCF 1514164.
  • Farach-Colton, Martín: This research was supported in part by NSF grants CCF 1637458, CNS 1408782, IIS 1541613, and NIH grant 1U01CA198952-01.
  • Tsai, Meng-Tsung: This research was supported in part by the Ministry of Science and Technology of Taiwan under contract MOST grant 107-2218-E-009-026-MY3.

References

  1. Amir Abboud and Virginia Vassilevska Williams. Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS, pages 434-443, Washington, DC, USA, 2014. IEEE Computer Society. URL: https://doi.org/10.1109/FOCS.2014.53.
  2. Tanbir Ahmed, Janusz Dybizbanski, and Hunter S. Snevily. Unique Sequences Containing No k-Term Arithmetic Progressions. Electr. J. Comb., 20(4):P29, 2013. Google Scholar
  3. M. Ajtai, P. Erdös, J. Komlós, and E. Szemerédi. On Turán’s theorem for sparse graphs. Combinatorica, 1(4):313-317, 1981. Google Scholar
  4. M. Ajtai, J. Komlós, and E. Szemerédi. A Dense Infinite Sidon Sequence. European Journal of Combinatorics, 2(1):1-11, 1981. Google Scholar
  5. Noga Alon and Joel Spencer. The Probabilistic Method. John Wiley, 1992. Google Scholar
  6. K. Appel and W. Haken. Every planar map is four colorable. Part I: Discharging. Illinois Journal of Mathematics, 21(3):429-490, September 1977. Google Scholar
  7. K. Appel, W. Haken, and J. Koch. Every planar map is four colorable. Part II: Reducibility. Illinois Journal of Mathematics, 21(3):491-567, September 1977. Google Scholar
  8. Arturs Backurs and Piotr Indyk. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False). SIAM J. Comput., 47(3):1087-1097, 2018. URL: https://doi.org/10.1137/15M1053128.
  9. Brenda S. Baker. Approximation Algorithms for NP-complete Problems on Planar Graphs. J. ACM, 41(1):153-180, January 1994. Google Scholar
  10. Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, and Noam Solomon. Subquadratic Algorithms for Algebraic 3SUM. Discrete & Computational Geometry, 61(4):698-734, 2019. URL: https://doi.org/10.1007/s00454-018-0040-y.
  11. Gill Barequet and Sariel Har-Peled. Polygon Containment and Translational Min-Hausdorff-Distance Between Segment Sets are 3Sum-hard. Int. J. Comput. Geometry Appl., 11(4):465-474, 2001. Google Scholar
  12. Piotr Berman and Marek Karpinski. On Some Tighter Inapproximability Results (Extended Abstract). In 26th International Colloquium in Automata, Languages and Programming (ICALP), pages 200-209, 1999. Google Scholar
  13. Prosenjit Bose and Stefan Langerman. Weighted Ham-Sandwich Cuts. In Discrete and Computational Geometry, Japanese Conference, JCDCG, Revised Selected Papers, pages 48-53, 2004. Google Scholar
  14. Karl Bringmann. Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 661-670, 2014. Google Scholar
  15. Harry Buhrman and John M. Hitchcock. NP-hard sets are exponentially dense unless coNP ⊆ NP/poly. In Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, (CCC), pages 1-7. IEEE Computer Society, 2008. URL: https://doi.org/10.1109/CCC.2008.21.
  16. Jean Cardinal, John Iacono, and Aurélien Ooms. Solving k-SUM Using Few Linear Queries. In 24th Annual European Symposium on Algorithms, ESA, pages 25:1-25:17, 2016. Google Scholar
  17. 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 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 743-754, 2017. Google Scholar
  18. Miroslav Chlebík and Janka Chlebíková. Approximation Hardness for Small Occurrence Instances of NP-hard Problems. In 5th Italian Conference on Algorithms and Complexity (CIAC), pages 152-164. Springer, 2003. Google Scholar
  19. Stephen A. Cook. Short Propositional Formulas Represent Nondeterministic Computations. Inf. Process. Lett., 26(5):269-270, 1988. URL: https://doi.org/10.1016/0020-0190(88)90152-4.
  20. Carlos Cotta, Iván Dotú, Antonio J. Fernández, and Pascal Van Hentenryck. A Memetic Approach to Golomb Rulers. In Proceedings of the 9th International Conference on Parallel Problem Solving from Nature, PPSN, pages 252-261, Berlin, Heidelberg, 2006. Springer-Verlag. Google Scholar
  21. Irit Dinur. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity (ECCC), 23:128, 2016. Google Scholar
  22. Irit Dinur and Pasin Manurangsi. ETH-hardness of approximating 2-CSPs and directed Steiner network. In 9th Innovations in Theoretical Computer Science Conference, ITCS, pages 36:1-36:20, 2018. Google Scholar
  23. Apostolos Dollas, William T. Rankin, and David Mccracken. New Algorithms for Golomb Ruler Derivation and Proof of the 19 Mark Ruler. IEEE Transactions on Information Theory, 44:379-382, 1998. Google Scholar
  24. J. Dybizbański. Sequences containing no 3-term arithmetic progressions. Elec. J. of Comb., 19(2):15-19, 2012. Google Scholar
  25. David Eppstein. Forbidden Configurations in Discrete Geometry. Cambridge University Press, 2018. Google Scholar
  26. David Eppstein, Gary L. Miller, and Shang-Hua Teng. A Deterministic Linear Time Algorithm for Geometric Separators and its Applications. Fundam. Inform., 22(4):309-329, 1995. URL: https://doi.org/10.3233/FI-1995-2241.
  27. S. Fajtlowicz. The independence ratio for cubic graphs. In 8th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, pages 273-277. LSU, 1977. Google Scholar
  28. Anka Gajentaan and Mark H. Overmars. On a Class of O(N²) Problems in Computational Geometry. Comput. Geom. Theory Appl., 5(3):165-185, October 1995. Google Scholar
  29. William I. Gasarch, James Glenn, and Clyde P. Kruskal. Finding large 3-free sets I: The small n case. J. Comput. Syst. Sci., 74(4):628-655, 2008. Google Scholar
  30. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  31. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? J. Comput. Syst. Sci., 63(4):512-530, December 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  32. Allan Grønlund Jørgensen and Seth Pettie. Threesomes, Degenerates, and Love Triangles. J. ACM, 65(4):22:1-22:25, 2018. URL: https://doi.org/10.1145/3185378.
  33. Sanjeev Khanna and Rajeev Motwani. Towards a Syntactic Characterization of PTAS. In 28th Annual ACM Symposium on Theory of Computing (STOC), pages 329-337. ACM, 1996. Google Scholar
  34. Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P. Williamson. The Approximability of Constraint Satisfaction Problems. SIAM J. Comput., 30(6):1863-1920, December 2001. Google Scholar
  35. John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is NP-complete. Journal of Computer and System Sciences, 20(2):219-230, 1980. Google Scholar
  36. Richard J. Lipton and Robert Endre Tarjan. Applications of a Planar Separator Theorem. SIAM J. Comput., 9(3):615-627, 1980. URL: https://doi.org/10.1137/0209046.
  37. Michael Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM J. Comput., 15(4):1036-1053, 1986. Google Scholar
  38. Michael Luby and Avi Wigderson. Pairwise Independence and Derandomization. Found. Trends Theor. Comput. Sci., 1(4):237-301, August 2006. Google Scholar
  39. Stephen R. Mahaney. Sparse Complete Sets of NP: Solution of a Conjecture of Berman and Hartmanis. J. Comput. Syst. Sci., 25(2):130-143, 1982. URL: https://doi.org/10.1016/0022-0000(82)90002-2.
  40. Pasin Manurangsi and Prasad Raghavendra. A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP, pages 78:1-78:15, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.78.
  41. Nimrod Megiddo and Kenneth J. Supowit. On the Complexity of Some Common Geometric Location Problems. SIAM J. Comput., 13(1):182-196, 1984. Google Scholar
  42. Christophe Meyer and Periklis A. Papakonstantinou. On the Complexity of Constructing Golomb Rulers. Discrete Appl. Math., 157(4):738-748, February 2009. Google Scholar
  43. Gary L. Miller, Shang-Hua Teng, William Thurston, and Stephen A. Vavasis. Separators for Sphere-packings and Nearest Neighbor Graphs. J. ACM, 44(1):1-29, January 1997. URL: https://doi.org/10.1145/256292.256294.
  44. Owen J. Murphy. Computing Independent Sets in Graphs with Large Girth. Discrete Appl. Math., 35(2):167-170, January 1992. Google Scholar
  45. Mitsunori Ogiwara and Osamu Watanabe. On Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets. SIAM J. Comput., 20(3):471-483, 1991. Google Scholar
  46. Mihai Pătraşcu and Ryan Williams. On the Possibility of Faster SAT Algorithms. In Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1065-1075, Philadelphia, PA, USA, 2010. Society for Industrial and Applied Mathematics. Google Scholar
  47. Liam Roditty and Virginia Vassilevska Williams. Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC, pages 515-524, New York, NY, USA, 2013. ACM. URL: https://doi.org/10.1145/2488608.2488673.
  48. J. T. Schwartz. Fast Probabilistic Algorithms for Verification of Polynomial Identities. J. ACM, 27(4):701-717, October 1980. Google Scholar
  49. Pascal Schweitzer. Problems of unknown complexity - Graph isomorphism and Ramsey theoretic numbers. PhD thesis, Universität des Saarlandes, 2009. Google Scholar
  50. James B. Shearer. A note on the independence number of triangle-free graphs. Discrete Mathematics, 46(1):83-87, 1983. Google Scholar
  51. Stephen W. Soliday, Abdollah Homaifar, and Gary L. Lebby. Genetic Algorithm Approach to the Search for Golomb Rulers. In Proceedings of the 6th International Conference on Genetic Algorithms, pages 528-535, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc. URL: http://dl.acm.org/citation.cfm?id=645514.658082.
  52. William Staton. Some Ramsey-Type Numbers and the Independence Ratio. Transactions of the American Mathematical Society, 256:353-370, 1979. Google Scholar
  53. T. Tao and V. H. Vu. Additive Combinatorics. Cambridge University Press, 2009. Google Scholar
  54. Jorge Tavares, Francisco B. Pereira, and Ernesto Costa. Understanding the role of insertion and correction in the evolution of Golomb rulers. In Proceedings of the IEEE Congress on Evolutionary Computation, CEC, pages 69-76, 2004. URL: https://doi.org/10.1109/CEC.2004.1330839.
  55. Pál Turán. Egy gráfelméleti szélsőérték feladatról. Matematikai és Fizikai Lapok, 48:436-452, 1941. Google Scholar
  56. D. W. Wang and Yue-Sun Kuo. A Study on Two Geometric Location Problems. Inf. Process. Lett., 28(6):281-286, 1988. Google Scholar
  57. D. J. A. Welsh. The Computational Complexity of Some Classical Problems from Statistical Physics. In In Disorder in Physical Systems, pages 307-321. Clarendon Press, 1990. Google Scholar
  58. Richard Zippel. Probabilistic Algorithms for Sparse Polynomials. In Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 216-226. Springer, 1979. 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
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact