Impatient PPSZ - A Faster Algorithm for CSP

Authors Shibo Li , Dominik Scheder



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.33.pdf
  • Filesize: 0.96 MB
  • 20 pages

Document Identifiers

Author Details

Shibo Li
  • Shanghai Jiao Tong University, China
Dominik Scheder
  • Shanghai Jiao Tong University, China

Acknowledgements

Dominik Scheder wants to thank Timon Hertli, Isabelle Hurbain, Sebastian Millius, Robin A. Moser, and May Szedlák, his co-authors of [Hertli et al., 2016]. The idea of impatient assignment came up when we were working on [Hertli et al., 2016].

Cite AsGet BibTex

Shibo Li and Dominik Scheder. Impatient PPSZ - A Faster Algorithm for CSP. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 33:1-33:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ISAAC.2021.33

Abstract

PPSZ is the fastest known algorithm for (d,k)-CSP problems, for most values of d and k. It goes through the variables in random order and sets each variable randomly to one of the d colors, excluding those colors that can be ruled out by looking at few constraints at a time. We propose and analyze a modification of PPSZ: whenever all but 2 colors can be ruled out for some variable, immediately set that variable randomly to one of the remaining colors. We show that our new "impatient PPSZ" outperforms PPSZ exponentially for all k and all d ≥ 3 on formulas with a unique satisfying assignment.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Randomized algorithms
  • Constraint Satisfaction Problems
  • exponential-time algorithms

Metrics

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

References

  1. Richard Beigel and David Eppstein. 3-coloring in time O (1.3289ⁿ). J. Algorithms, 54(2):168-204, 2005. URL: https://doi.org/10.1016/j.jalgor.2004.06.008.
  2. Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, and Uri Zwick. Faster k-SAT algorithms using biased-PPSZ. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 578-589. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316359.
  3. Timon Hertli. 3-SAT faster and simpler - unique-SAT bounds for PPSZ hold in general. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science - FOCS 2011, pages 277-284. IEEE Computer Soc., Los Alamitos, CA, 2011. URL: https://doi.org/10.1109/FOCS.2011.22.
  4. 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
  5. Michal Koucký, Vojtech Rödl, and Navid Talebanfard. A separator theorem for hypergraphs and a CSP-SAT algorithm. CoRR, abs/2105.06744, 2021. URL: http://arxiv.org/abs/2105.06744.
  6. 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
  7. Ramamohan Paturi, Pavel Pudlák, and Francis Zane. Satisfiability coding lemma. In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 566-574. IEEE, 1997. Google Scholar
  8. 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.
  9. Dominik Scheder. PPSZ is better than you think. Electron. Colloquium Comput. Complex., 28:69, 2021. URL: https://eccc.weizmann.ac.il/report/2021/069.
  10. Dominik Scheder and John P. Steinberger. PPSZ for General k-SAT - making Hertli’s analysis simpler and 3-SAT faster. In Ryan O'Donnell, editor, 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, volume 79 of LIPIcs, pages 9:1-9:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.9.
  11. Uwe Schöning. A probabilistic algorithm for k-SAT and constraint satisfaction problems. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pages 410-414. IEEE Computer Society, Los Alamitos, CA, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814612.
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