Bounded Degree Nonnegative Counting CSP

被引:0
作者
Cai, Jin-Yi [1 ]
Szabo, Daniel P. [1 ]
机构
[1] Univ Wisconsin Madison, Dept Comp Sci, 1210 W Dayton St, Madison, WI 53706 USA
基金
美国国家科学基金会;
关键词
Computational counting complexity; constraint satisfaction problems; counting CSPs; complexity dichotomy; nonnegative counting CSP; graph homomorphisms; GRAPH HOMOMORPHISMS; COMPLEXITY; DICHOTOMY; PROPAGATION;
D O I
10.1145/3632184
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Constraint satisfaction problems (CSP) encompass an enormous variety of computational problems. In particular, all partition functions from statistical physics, such as spin systems, are special cases of counting CSP (#CSP). We prove a complete complexity classification for every counting problem in #CSP with nonnegative valued constraint functions that is valid when every variable occurs a bounded number of times in all constraints. We show that, depending on the set of constraint functions F, every problem in the complexity class #CSP(F) defined by F is either polynomial-time computable for all instances without the bounded occurrence restriction, or is #P-hard even when restricted to bounded degree input instances. The constant bound in the degree depends on F. The dichotomy criterion on F is decidable. As a second contribution, we prove a slightly modified but more streamlined decision procedure (from [14]) to test for the tractability of #CSP( F). This procedure on an input F tells us which case holds in the dichotomy for #CSP(F). This more streamlined decision procedure enables us to fully classify a family of directed weighted graph homomorphism problems. This family contains both P-time tractable problems and #P-hard problems. To our best knowledge, this is the first family of such problems explicitly classified that are not acyclic, thereby the Lovasz-goodness criterion of Dyer-Goldberg-Paterson [24] cannot be applied.
引用
收藏
页数:18
相关论文
共 50 条
[41]   On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem [J].
Ganian, Robert ;
Klute, Fabian ;
Ordyniak, Sebastian .
ALGORITHMICA, 2021, 83 (01) :297-336
[42]   Counting List Homomorphisms from Graphs of Bounded Treewidth: Tight Complexity Bounds [J].
Focke, Jacob ;
Marx, Daniel ;
Rzazewski, Pawel .
ACM TRANSACTIONS ON ALGORITHMS, 2024, 20 (02)
[43]   Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds [J].
Focke, Jacob ;
Marx, Daniel ;
Rzazewski, Pawel .
PROCEEDINGS OF THE 2022 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2022, :431-458
[44]   Ehrenfeucht-Fraisse goes elementarily automatic for structures of bounded degree [J].
Durand-Gasselin, Antoine ;
Habermehl, Peter .
29TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, (STACS 2012), 2012, 14 :242-253
[45]   Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs [J].
Yoshida, Yuichi .
2011 IEEE 26TH ANNUAL CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC), 2011, :34-44
[46]   Location of zeros for the partition function of the Ising model on bounded degree graphs [J].
Peters, Han ;
Regts, Guus .
JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 2020, 101 (02) :765-785
[47]   The complexity of ferromagnetic 2-spin systems on bounded degree graphs [J].
Bai, Zonglei ;
Cao, Yongzhi ;
Wang, Hanpin .
THEORETICAL COMPUTER SCIENCE, 2025, 1028
[48]   Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width [J].
de Menibus, Benjamin Hellouin ;
Uno, Takeaki .
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2011, 2011, 6648 :483-494
[49]   Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs [J].
Coelho, H. ;
Faria, L. ;
Gravier, S. ;
Klein, S. .
DISCRETE APPLIED MATHEMATICS, 2016, 198 :109-117
[50]   Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs [J].
Hasan, Mohammad Khairul ;
Yoon, Sung-Eui ;
Chwa, Kyung-Yong .
FRONTIERS IN ALGORITHMICS, PROCEEDINGS, 2009, 5598 :153-162