The complexity of weighted and unweighted #CSP

Abstract

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 a recent dichotomy for unweighted #CSP can be extended to rational-weighted #CSP.

11 pages

References in corpus (1)

• The Complexity of Weighted Boolean #CSP

Cited by in corpus (12)

• The expressibility of functions on the Boolean domain, with applications to Counting CSPs
• The complexity of approximating conservative counting CSPs
• Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts
• Approximation Complexity of Maximum A Posteriori Inference in Sum-Product Networks
• Beyond #CSP: A Dichotomy for Counting Weighted Eulerian Orientations with ARS
• The Complexity of Holant Problems over Boolean Domain with Non-negative Weights
• An Effective Dichotomy for the Counting Constraint Satisfaction Problem
• Non-negative Weighted #CSPs: An Effective Complexity Dichotomy
• The Complexity of Weighted Counting for Acyclic Conjunctive Queries
• The Complexity of Bayesian Networks Specified by Propositional and Relational Languages
• The Weight in Enumeration
• New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification