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

Jean Cardinal, Jerri Nummenpalo, Emo Welzl

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 s…