LIPIcs.ISAAC.2021.33.pdf
- Filesize: 0.96 MB
- 20 pages
Document
Impatient PPSZ - A Faster Algorithm for CSP
Authors
Shibo Li 
,
Dominik Scheder
-
Part of:
Volume:
32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-11-30
File
Document Identifiers
Author Details
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 As Get 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)
0PDF Downloads
References
- 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.
- 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.
- 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.
-
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.
- 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.
-
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.
-
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.
- 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.
- Dominik Scheder. PPSZ is better than you think. Electron. Colloquium Comput. Complex., 28:69, 2021. URL: https://eccc.weizmann.ac.il/report/2021/069.
- 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.
- 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.