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 条

[11] Near-optimal bounded-degree spanning trees
J. C. Hansen
E. Schmutz
Algorithmica, 2001, 29 : 148 - 180
[12] The complexity of weighted Boolean #CSP with mixed signs
Bulatov, Andrei
Dyer, Martin
Goldberg, Leslie Ann
Jalsenius, Markus
Richerby, David
THEORETICAL COMPUTER SCIENCE, 2009, 410 (38-40) : 3949 - 3961
[13] The Complexity of Weighted Boolean #CSP Modulo k
Guo, Heng
Huang, Sangxia
Lu, Pinyan
Xia, Mingji
28TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2011), 2011, 9 : 249 - 260
[14] Near-optimal bounded-degree spanning trees
Hansen, JC
Schmutz, E
ALGORITHMICA, 2001, 29 (1-2) : 148 - 180
[15] Bounded-degree forbidden patterns problems are constraint satisfaction problems
Dantchev, Stefan
Madelaine, Florent
COMPUTER SCIENCE - THEORY AND APPLICATIONS, 2006, 3967 : 159 - 170
[16] Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs
Hasan, Mohammad Khairul
Yoon, Sung-Eui
Chwa, Kyung-Yong
FRONTIERS IN ALGORITHMICS, PROCEEDINGS, 2009, 5598 : 153 - 162
[17] The complexity of approximating MAPs for belief networks with bounded probabilities
Abdelbar, AM
Hedetniemi, ST
Hedetniemi, SM
ARTIFICIAL INTELLIGENCE, 2000, 124 (02) : 283 - 288
[18] Approximating Bounded Degree Deletion via Matroid Matching
Fujito, Toshihiro
ALGORITHMS AND COMPLEXITY (CIAC 2017), 2017, 10236 : 234 - 246
[19] APPROXIMATELY COUNTING INDEPENDENT SETS OF A GIVEN SIZE IN BOUNDED-DEGREE GRAPHS
Davies, Ewan
Perkins, Will
SIAM JOURNAL ON COMPUTING, 2023, 52 (02) : 618 - 640
[20] Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight
Creignou, Nadia
Olive, Frederic
Schmidt, Johannes
THEORY AND APPLICATIONS OF SATISFIABILITY TESTING - SAT 2011, 2011, 6695 : 120 - 133

← 1 2 3 4 5 →