Solving and sampling with many solutions: Satisfiability and other hard problems

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∗(ϵ-0.617) where ϵ is the fraction of assignments that are satisfying. This improves significantly over the trivial sampling bound of expected Θ∗(ϵ-1), and on all previous algorithms whenever ϵ = Ω(0.708n). We also consider algorithms for 3-SAT with an ϵ fraction of satisfying assignments, and prove that it can be solved in O∗(ϵ-2.27) deterministic time, and in O∗(ϵ-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.SCOPUS: cp.p