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

DOI10.4230/LIPICS.IPEC.2017.11zbMATH Open1443.68069arXiv1708.01122OpenAlexW2745221522MaRDI QIDQ5111870FDOQ5111870

Jean Cardinal, Emo Welzl, Jerri Nummenpalo

Publication date: 27 May 2020

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^{*}(varepsilo{n}^{-0.617})$ where $varepsilon$ is the fraction of assignments that are satisfying. This improves significantly over the trivial sampling bound of expected $Thet{a}^{*}(varepsilo{n}^{-1})$, and on all previous algorithms whenever $varepsilon=Omega(0.708^n)$. We also consider algorithms for 3-SAT with an $varepsilon$ fraction of satisfying assignments, and prove that it can be solved in $O^{*}(varepsilo{n}^{-2.27})$ deterministic time, and in $O^{*}(varepsilo{n}^{-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.

Full work available at URL: https://arxiv.org/abs/1708.01122

Recommendations

• Solving and sampling with many solutions
• scientific article; zbMATH DE number 2090009
• Fast Sampling and Counting k -SAT Solutions in the Local Lemma Regime
• An approximation algorithm for \(\#k\)-SAT
• Why almost all satisfiable k-CNF formulas are easy

zbMATH Keywords

samplingparameterized complexitysatisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Analysis of algorithms (68W40) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Cites Work

• Random generation of combinatorial structures from a uniform distribution
• Title not available (Why is that?)
• A short proof for a theorem of Harper about Hamming-spheres
• Solving satisfiability in less than \(2^ n\) steps
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
• 3-SAT Faster and Simpler---Unique-SAT Bounds for PPSZ Hold in General
• Improved pseudorandom generators for depth 2 circuits
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• Theory and Applications of Satisfiability Testing
• A fast deterministic algorithm for formulas that have many satisfying assignments
• A short implicant of a CNF formula with many satisfying assignments
• Solving and sampling with many solutions: Satisfiability and other hard problems
• Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT

Cited In (3)

• Solving and sampling with many solutions: Satisfiability and other hard problems
• Solving and sampling with many solutions
• Practically uniform solution sampling in constraint programming

This page was built for publication: Solving and sampling with many solutions: satisfiability and other hard problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111870)