The complexity of approximating bounded-degree Boolean #CSP

被引：6
|
作者：
Dyer, Martin [1 ]
Goldberg, Leslie Ann [2 ]
Jalsenius, Markus [3 ]
Richerby, David [2 ]
机构：
[1] Univ Leeds, Sch Comp, Leeds LS2 9JT, W Yorkshire, England
[2] Univ Liverpool, Dept Comp Sci, Liverpool L69 3BX, Merseyside, England
[3] Univ Bristol, Dept Comp Sci, Bristol BS8 1UB, Avon, England
来源：
INFORMATION AND COMPUTATION | 2012年 / 220卷
基金：
英国工程与自然科学研究理事会;
关键词：
Counting constraint satisfaction problem; CSP; Approximation algorithm; Complexity; CONSTRAINT SATISFACTION; GENERALIZED SATISFIABILITY; ENUMERATION;
D O I：
10.1016/j.ic.2011.12.007
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The degree of a CSP instance is the maximum number of times that any variable appears in the scopes of constraints. We consider the approximate counting problem for Boolean CSP with bounded-degree instances, for constraint languages containing the two unary constant relations {0} and {1}. When the maximum allowed degree is large enough (at least 6) 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, where the complexity is related to the complexity of approximately counting independent sets in hypergraphs. (C) 2012 Elsevier Inc. All rights reserved.
引用
收藏
页码：1 / 14
页数：14
相关论文
共 50 条
12345