Complexity of approximating #CSPs
Amir Hedayaty · Summit (Simon Fraser University) · 2012
Constraint satisfactions is a framework to express combinatorial problems. #CSP is the problem of finding the number of solutions for a constraint satisfaction problem instance. In this work, we study complexity of approximately solving the #CSP. We provide several techniques for approximation preserving reductions among counting problems. Most of this work focuses on reduction to #BIS, the problem of finding the number of independent sets in a bipartite graph. We prove that approximately solving #CSP(Γ) over relations which we call monotone, is not harder than #BIS. We also prove that approximately solving #Hom(H) for reflexive oriented graphs is not easier than #BIS. Finally, we investigate monotone reflexive graphs.