2026-07-20T05:58:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8545 2024-03-06T10:41:30Z ddc:004 open_access

Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems Cardinal, Jean Nummenpalo, Jerri Welzl, Emo Satisfiability Sampling Parameterized complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jean Cardinal and Jerri Nummenpalo and Emo Welzl 2018 Is Part Of LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2017.11 urn:nbn:de:0030-drops-85459 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.11 eng https://creativecommons.org/licenses/by/3.0/legalcode