Document Open Access Logo

Faster Algorithm for Unique (k,2)-CSP

Author Or Zamir

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.92.pdf
  • Filesize: 0.63 MB
  • 13 pages

Document Identifiers

Author Details

Or Zamir
  • Institute for Advanced Study, Princeton, NJ, USA

Funding

Supported by NSF grant # CCF-1900460.

Cite As Get BibTex

Or Zamir. Faster Algorithm for Unique (k,2)-CSP. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 92:1-92:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ESA.2022.92

Abstract

In a (k,2)-Constraint Satisfaction Problem we are given a set of arbitrary constraints on pairs of k-ary variables, and are asked to find an assignment of values to these variables such that all constraints are satisfied. The (k,2)-CSP problem generalizes problems like k-coloring and k-list-coloring. In the Unique (k,2)-CSP problem, we add the assumption that the input set of constraints has at most one satisfying assignment.
Beigel and Eppstein gave an algorithm for (k,2)-CSP running in time O((0.4518k)^n) for k > 3 and O (1.356ⁿ) for k = 3, where n is the number of variables. Feder and Motwani improved upon the Beigel-Eppstein algorithm for k ≥ 11. Hertli, Hurbain, Millius, Moser, Scheder and Szedl{á}k improved these bounds for Unique (k,2)-CSP for every k ≥ 5.
We improve the result of Hertli et al. and obtain better bounds for Unique (k,2)-CSP for k ≥ 5. In particular, we improve the running time of Unique (5,2)-CSP from O (2.254ⁿ) to O (2.232^n) and Unique (6,2)-CSP from O (2.652^n) to O (2.641^n).
Recently, Li and Scheder also published an improvement over the algorithm of Hertli et al. in the same regime as ours. Their improvement does not include quantitative bounds, we compare the works in the paper.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
Keywords
  • Algorithms
  • Constraint Satisfaction Problem

Metrics

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

References

  1. Richard Beigel and David Eppstein. 3-coloring in time O(1.3289ⁿ). Journal of Algorithms, 54(2):168-204, 2005. Google Scholar
  2. Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set partitioning via inclusion-exclusion. SIAM Journal on Computing, 39(2):546-563, 2009. Google Scholar
  3. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The complexity of satisfiability of small depth circuits. In International Workshop on Parameterized and Exact Computation, pages 75-85. Springer, 2009. Google Scholar
  4. Tomás Feder and Rajeev Motwani. Worst-case time bounds for coloring and satisfiability problems. Journal of Algorithms, 45(2):192-201, 2002. Google Scholar
  5. Fedor V Fomin and Petteri Kaski. Exact exponential algorithms. Communications of the ACM, 56(3):80-88, 2013. Google Scholar
  6. F.V. Fomin and D. Kratsch. Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer Berlin Heidelberg, 2010. Google Scholar
  7. Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, and Uri Zwick. Faster k-SAT algorithms using biased-PPSZ. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 578-589, 2019. Google Scholar
  8. Timon Hertli. 3-SAT faster and simpler - unique-SAT bounds for PPSZ hold in general. SIAM J. Comput., 43(2):718-729, 2014. Announced at FOCS'11. Google Scholar
  9. Timon Hertli, Isabelle Hurbain, Sebastian Millius, Robin A Moser, Dominik Scheder, and May Szedlák. The ppsz algorithm for constraint satisfaction problems on more than two colors. In International Conference on Principles and Practice of Constraint Programming, pages 421-437. Springer, 2016. Google Scholar
  10. Eugene L Lawler. A note on the complexity of the chromatic number problem, 1976. Google Scholar
  11. Liang Li, Xin Li, Tian Liu, and Ke Xu. From k-sat to k-csp: Two generalized algorithms. arXiv preprint, 2008. URL: http://arxiv.org/abs/0801.3147.
  12. Shibo Li and Dominik Scheder. Impatient ppsz-a faster algorithm for csp. arXiv preprint, 2021. URL: http://arxiv.org/abs/2109.02795.
  13. Burkhard Monien and Ewald Speckenmeyer. Solving satisfiability in less than 2n steps. Discrete Applied Mathematics, 10(3):287-295, 1985. Google Scholar
  14. Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, and Francis Zane. An improved exponential-time algorithm for k-SAT. In 39th Annual Symposium on Foundations of Computer Science, FOCS '98, pages 628-637, 1998. URL: https://doi.org/10.1109/SFCS.1998.743513.
  15. Ramamohan Paturi, Pavel Pudlák, Michael E Saks, and Francis Zane. An improved exponential-time algorithm for k-SAT. Journal of the ACM (JACM), 52(3):337-364, 2005. Google Scholar
  16. Dominik Scheder. Ppz for more than two truth values-an algorithm for constraint satisfaction problems. arXiv preprint, 2010. URL: http://arxiv.org/abs/1010.5717.
  17. T Schoning. A probabilistic algorithm for k-SAT and constraint satisfaction problems. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 410-414. IEEE, 1999. Google Scholar
  18. Patrick Traxler. The time complexity of constraint satisfaction. In International Workshop on Parameterized and Exact Computation, pages 190-201. Springer, 2008. Google Scholar
  19. Gerhard J Woeginger. Exact algorithms for NP-hard problems: A survey. In Combinatorial optimization - eureka, you shrink!, pages 185-207. Springer, 2003. Google Scholar
  20. Or Zamir. Breaking the 2ⁿ barrier for 5-coloring and 6-coloring, 2020. 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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact