Paper Info
Title
The complexity of approximating conservative counting CSPs
Abstract
We study the complexity of the approximate weighted counting constraint satisfaction problem #CSP ( F ) . In the conservative case, where F contains all unary functions, a classification is known over the Boolean domain; we extend this to arbitrary finite domains. We show that if F is \"weakly log-modular\", then #CSP ( F ) is in FP. Otherwise, it is at least as difficult to approximate as #BIS (counting independent sets in bipartite graphs). #BIS is complete for the complexity class # R H ¿ 1 , and believed to be intractable. We further sub-divide the #BIS-hard case: if F is \"weakly log-supermodular\", #CSP ( F ) is as easy as a Boolean log-supermodular weighted #CSP; otherwise, we show that it is NP-hard to approximate. Finally, we give a full trichotomy for the arity-2 case: #CSP ( F ) is in FP, is #BIS-equivalent, or is equivalent to #SAT (approximately counting the satisfying assignments of Boolean CNF formulas). We also discuss algorithmic aspects of our classification. We classify the complexity of approximating conservative weighted counting CSP.It is in FP, as hard as counting bipartite independent sets (#BIS) or as hard as #SAT.For functions of arity 2, the #BIS-hard case is equivalent to #BIS.For higher arity, the #BIS-hard case reduces to a Boolean weighted #CSP or is NP-hard.Given a weighted constraint language, the classification is decidable.
Year
DOI
Venue
2012
10.1016/j.jcss.2014.06.006
Journal of Computer and System Sciences
Keywords
DocType
Volume
constraint satisfaction problems,counting constraint satisfaction problem,complexity,approximation,counting complexity
Journal
81
Issue
ISSN
Citations 
Issue-in-Progress
0022-0000
6
PageRank 
References 
Authors
0.48
26
7
Name
Order
Citations
PageRank
Xi Chen195066.32
Martin E. Dyer2529116.66
leslie ann goldberg31411125.20
mark jerrum42755564.62
Pinyan Lu589868.92
Colin McQuillan6313.46
David M. Richerby714214.06