The complexity of weighted and unweighted #CSP

We give some reductions among problems in (nonnegative) weighted #CSP which restrict the class of functions that needs to be considered in computational complexity studies. Our reductions can be applied to both exact and approximate computation. In particular, we show that the recent dichotomy for unweighted #CSP can be extended to rational-weighted #CSP.

► Proposes and applies a new class of reductions for weighted #CSP problems.
► The reductions can be applied to both exact and approximate computation.
► Shows equivalence for various classes of weighted #CSP problems.
► Extends the dichotomy for unweighted #CSP to rational-weighted #CSP.
► Shows that all weighted #CSP problems can be reduced to problems with one function.