1 Search Results for "Szabo, Daniel P."

Document

DOI: 10.4230/LIPIcs.MFCS.2022.27

Bounded Degree Nonnegative Counting CSP

Authors: Jin-Yi Cai and Daniel P. Szabo

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

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.

Cite as

Jin-Yi Cai and Daniel P. Szabo. Bounded Degree Nonnegative Counting CSP. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.27},
  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}
}

Refine by Author
1 Cai, Jin-Yi
1 Szabo, Daniel P.

Refine by Classification
1 Theory of computation → Complexity classes
1 Theory of computation → Problems, reductions and completeness

Refine by Keyword
1 Complexity Dichotomy
1 Computational Counting Complexity
1 Constraint Satisfaction Problems
1 Counting CSPs
1 Graph Homomorphisms
Show More...

Refine by Type
1 document

Refine by Publication Year
1 2022

1 Search Results for "Szabo, Daniel P."

Bounded Degree Nonnegative Counting CSP

Abstract

Cite as

Thanks for your feedback!

Could not send message