2026-08-11T08:10:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16825 2024-03-06T10:58:25Z ddc:004 open_access

Bounded Degree Nonnegative Counting CSP Cai, Jin-Yi Szabo, Daniel P. Computational Counting Complexity Constraint Satisfaction Problems Counting CSPs Complexity Dichotomy Nonnegative Counting CSP Graph Homomorphisms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jin-Yi Cai and Daniel P. Szabo 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.27 urn:nbn:de:0030-drops-168250 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.27 eng https://creativecommons.org/licenses/by/4.0/legalcode