3 Search Results for "Dyer, Martin E."


Document
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}
}
Document
Track A: Algorithms, Complexity and Games
A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights

Authors: Artem Govorov, Jin-Yi Cai, and Martin Dyer

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)


Abstract
We consider the complexity of counting weighted graph homomorphisms defined by a symmetric matrix A. Each symmetric matrix A defines a graph homomorphism function Z_A(⋅), also known as the partition function. Dyer and Greenhill [Martin E. Dyer and Catherine S. Greenhill, 2000] established a complexity dichotomy of Z_A(⋅) for symmetric {0, 1}-matrices A, and they further proved that its #P-hardness part also holds for bounded degree graphs. Bulatov and Grohe [Andrei Bulatov and Martin Grohe, 2005] extended the Dyer-Greenhill dichotomy to nonnegative symmetric matrices A. However, their hardness proof requires graphs of arbitrarily large degree, and whether the bounded degree part of the Dyer-Greenhill dichotomy can be extended has been an open problem for 15 years. We resolve this open problem and prove that for nonnegative symmetric A, either Z_A(G) is in polynomial time for all graphs G, or it is #P-hard for bounded degree (and simple) graphs G. We further extend the complexity dichotomy to include nonnegative vertex weights. Additionally, we prove that the #P-hardness part of the dichotomy by Goldberg et al. [Leslie A. Goldberg et al., 2010] for Z_A(⋅) also holds for simple graphs, where A is any real symmetric matrix.

Cite as

Artem Govorov, Jin-Yi Cai, and Martin Dyer. A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 66:1-66:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{govorov_et_al:LIPIcs.ICALP.2020.66,
  author =	{Govorov, Artem and Cai, Jin-Yi and Dyer, Martin},
  title =	{{A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{66:1--66:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.66},
  URN =		{urn:nbn:de:0030-drops-124733},
  doi =		{10.4230/LIPIcs.ICALP.2020.66},
  annote =	{Keywords: Graph homomorphism, Complexity dichotomy, Counting problems}
}
Document
08201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms

Authors: Martin E. Dyer, Mark Jerrum, and Marek Karpinski

Published in: Dagstuhl Seminar Proceedings, Volume 8201, Design and Analysis of Randomized and Approximation Algorithms (2008)


Abstract
From 11.05.08 to 16.05.08, the Dagstuhl Seminar 08201 ``Design and Analysis of Randomized and Approximation Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research work, and ongoing work and open problems were discussed. Abstracts of the presentations which were given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full paper are provided, if available.

Cite as

Martin E. Dyer, Mark Jerrum, and Marek Karpinski. 08201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms. In Design and Analysis of Randomized and Approximation Algorithms. Dagstuhl Seminar Proceedings, Volume 8201, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{dyer_et_al:DagSemProc.08201.1,
  author =	{Dyer, Martin E. and Jerrum, Mark and Karpinski, Marek},
  title =	{{08201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms}},
  booktitle =	{Design and Analysis of Randomized and Approximation Algorithms},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8201},
  editor =	{Martin E. Dyer and Mark Jerrum and Marek Karpinski},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08201.1},
  URN =		{urn:nbn:de:0030-drops-15518},
  doi =		{10.4230/DagSemProc.08201.1},
  annote =	{Keywords: Randomized Algorithms, Approximation Algorithms, Optimization Problems, Measurement Problems, Approximation Complexity, Algorithmic Game Theory, Internet, Decentralized Networks, Network Design}
}
  • Refine by Author
  • 2 Cai, Jin-Yi
  • 1 Dyer, Martin
  • 1 Dyer, Martin E.
  • 1 Govorov, Artem
  • 1 Jerrum, Mark
  • Show More...

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

  • Refine by Keyword
  • 1 Algorithmic Game Theory
  • 1 Approximation Algorithms
  • 1 Approximation Complexity
  • 1 Complexity Dichotomy
  • 1 Complexity dichotomy
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2008
  • 1 2020
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail