License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.27
URN: urn:nbn:de:0030-drops-168250
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16825/
Cai, Jin-Yi ;
Szabo, Daniel P.
Bounded Degree Nonnegative Counting CSP
Abstract
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 ℱ, every problem in the complexity class #CSP(ℱ) defined by ℱ 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 ℱ. The dichotomy criterion on ℱ is decidable. As a second contribution, we prove a slightly modified but more streamlined decision procedure (from [Jin-Yi Cai et al., 2011]) for tractability. This 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 Lovász-goodness criterion of Dyer-Goldberg-Paterson [Martin E. Dyer et al., 2006] cannot be applied.
BibTeX - Entry
@InProceedings{cai_et_al:LIPIcs.MFCS.2022.27,
author = {Cai, Jin-Yi and Szabo, Daniel P.},
title = {{Bounded Degree Nonnegative Counting CSP}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {27:1--27:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16825},
URN = {urn:nbn:de:0030-drops-168250},
doi = {10.4230/LIPIcs.MFCS.2022.27},
annote = {Keywords: Computational Counting Complexity, Constraint Satisfaction Problems, Counting CSPs, Complexity Dichotomy, Nonnegative Counting CSP, Graph Homomorphisms}
}
|
Keywords: |
|
Computational Counting Complexity, Constraint Satisfaction Problems, Counting CSPs, Complexity Dichotomy, Nonnegative Counting CSP, Graph Homomorphisms |
|
Collection: |
|
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
22.08.2022 |
