Computer Science – Computational Complexity
Scientific paper
2010-01-27
Computer Science
Computational Complexity
12-page conference version for STACS 2010
Scientific paper
The degree of a CSP instance is the maximum number of times that a variable may appear in the scope of constraints. We consider the approximate counting problem for Boolean CSPs with bounded-degree instances, for constraint languages containing the two unary constant relations {0} and {1}. When the maximum degree is at least 25 we obtain a complete classification of the complexity of this problem. It is exactly solvable in polynomial-time if every relation in the constraint language is affine. It is equivalent to the problem of approximately counting independent sets in bipartite graphs if every relation can be expressed as conjunctions of {0}, {1} and binary implication. Otherwise, there is no FPRAS unless NP=RP. For lower degree bounds, additional cases arise in which the complexity is related to the complexity of approximately counting independent sets in hypergraphs.
Dyer Martin E.
Goldberg Leslie Ann
Jalsenius Markus
Richerby David
No associations
LandOfFree
The Complexity of Approximating Bounded-Degree Boolean #CSP (Extended Abstract) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Complexity of Approximating Bounded-Degree Boolean #CSP (Extended Abstract), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Approximating Bounded-Degree Boolean #CSP (Extended Abstract) will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-240322