Document Open Access Logo

Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems

Authors Jean Cardinal, Jerri Nummenpalo, Emo Welzl

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2017.11.pdf
  • Filesize: 0.52 MB
  • 12 pages

Document Identifiers

Author Details

Jean Cardinal
Jerri Nummenpalo
Emo Welzl

Cite As Get BibTex

Jean Cardinal, Jerri Nummenpalo, and Emo Welzl. Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 11:1-11:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.IPEC.2017.11

Abstract

We investigate parameterizing hard combinatorial problems by the size of the solution set compared to all solution candidates. Our main result is a uniform sampling algorithm for satisfying assignments of 2-CNF formulas that runs in expected time O^*(eps^{-0.617}) where eps is the fraction of assignments that are satisfying. This improves significantly over the trivial sampling bound of expected Theta^*(eps^{-1}), and on all previous algorithms whenever eps = Omega(0.708^n). We also consider algorithms for 3-SAT with an eps fraction of satisfying assignments, and prove that it can be solved in O^*(eps^{-2.27}) deterministic time, and in O^*(eps^{-0.936}) randomized time. Finally, to further demonstrate the applicability of this framework, we also explore how similar techniques can be used for vertex cover problems.

Subject Classification

Keywords
  • Satisfiability
  • Sampling
  • Parameterized complexity

Metrics

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

References

  1. Bengt Aspvall, Michael F Plass, and Robert Endre Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters, 8(3):121-123, 1979. Google Scholar
  2. Jean Cardinal, Jerri Nummenpalo, and Emo Welzl. Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems. ArXiv e-prints, 2017. URL: http://arxiv.org/abs/1708.01122.
  3. Anindya De, Omid Etesami, Luca Trevisan, and Madhur Tulsiani. Improved pseudorandom generators for depth 2 circuits. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX, and 14th International Workshop, RANDOM, pages 504-517, 2010. Google Scholar
  4. Peter Frankl and Zoltán Füredi. A short proof for a theorem of Harper about hamming-spheres. Discrete Mathematics, 34(3):311-313, 1981. Google Scholar
  5. Timon Hertli. 3-SAT faster and simpler - unique-SAT bounds for PPSZ hold in general. SIAM Journal on Computing, 43(2):718-729, 2014. Google Scholar
  6. Edward A Hirsch. A fast deterministic algorithm for formulas that have many satisfying assignments. Logic Journal of IGPL, 6(1):59-71, 1998. Google Scholar
  7. Mark R Jerrum. Counting, sampling and integrating: algorithms and complexity. Springer Science &Business Media, 2003. Google Scholar
  8. Mark R Jerrum, Leslie G Valiant, and Vijay V Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169-188, 1986. Google Scholar
  9. Daniel M Kane and Osamu Watanabe. A short implicant of cnfs with relatively many satisfying assignments. In Electronic Colloquium on Computational Complexity (ECCC), volume 20, page 176, 2013. Google Scholar
  10. Kuldeep S Meel, Moshe Y Vardi, Supratik Chakraborty, Daniel J Fremont, Sanjit A Seshia, Dror Fried, Alexander Ivrii, and Sharad Malik. Constrained sampling and counting: Universal hashing meets sat solving. In AAAI Workshop: Beyond NP, 2016. Google Scholar
  11. Burkhard Monien and Ewald Speckenmeyer. Solving satisfiability in less than 2ⁿ steps. Discrete Applied Mathematics, 10(3):287-295, 1985. Google Scholar
  12. Yehuda Naveh, Michal Rimon, Itai Jaeger, Yoav Katz, Michael Vinov, Eitan s Marcu, and Gil Shurek. Constraint-based random stimuli generation for hardware verification. AI magazine, 28(3):13, 2007. Google Scholar
  13. Tian Sang, Paul Beame, and Henry A Kautz. Performing bayesian inference by weighted model counting. In AAAI, volume 5, pages 475-481, 2005. Google Scholar
  14. Manuel Schmitt and Rolf Wanka. Exploiting independent subformulas: A faster approximation scheme for #k-SAT. Information Processing Letters, 113(9):337-344, 2013. Google Scholar
  15. Uwe Schöning. A probabilistic algorithm for k-SAT based on limited local search and restart. Algorithmica, 32(4):615-623, 2002. Google Scholar
  16. Rocco Servedio and Li-Yang Tan. Deterministic search for CNF satisfying assignments in almost polynomial time. Unpublished manuscript, 2016. Google Scholar
  17. Luca Trevisan. A note on approximate counting for k-DNF. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 417-425. Springer, 2004. Google Scholar
  18. Magnus Wahlström. A tighter bound for counting max-weight solutions to 2SAT instances. In International Workshop on Parameterized and Exact Computation, pages 202-213. Springer, 2008. 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