1 Search Results for "Briceño, Raimundo"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.29
Dismantlability, Connectedness, and Mixing in Relational Structures

Authors: Raimundo Briceño, Andrei A. Bulatov, Víctor Dalmau, and Benoît Larose

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
The Constraint Satisfaction Problem (CSP) and its counting counterpart appears under different guises in many areas of mathematics, computer science, statistical physics, and elsewhere. Its structural and algorithmic properties have demonstrated to play a crucial role in many of those applications. For instance, topological properties of the solution set such as connectedness is related to the hardness of CSPs over random structures. In approximate counting and statistical physics, where CSPs emerge in the form of spin systems, mixing properties and the uniqueness of Gibbs measures have been heavily exploited for approximating partition functions or the free energy of spin systems. Additionally, in the decision CSPs, structural properties of the relational structures involved - like, for example, dismantlability - and their logical characterizations have been instrumental for determining the complexity and other properties of the problem. In spite of the great diversity of those features, there are some eerie similarities between them. These were observed and made more precise in the case of graph homomorphisms by Brightwell and Winkler, who showed that the structural property of dismantlability of the target graph, the connectedness of the set of homomorphisms, good mixing properties of the corresponding spin system, and the uniqueness of Gibbs measure are all equivalent. In this paper we go a step further and demonstrate similar connections for arbitrary CSPs. This requires much deeper understanding of dismantling and the structure of the solution space in the case of relational structures, and new refined concepts of mixing introduced by Briceño. In addition, we develop properties related to the study of valid extensions of a given partially defined homomorphism, an approach that turns out to be novel even in the graph case. We also add to the mix the combinatorial property of finite duality and its logic counterpart, FO-definability, studied by Larose, Loten, and Tardif.
Cite as

Raimundo Briceño, Andrei A. Bulatov, Víctor Dalmau, and Benoît Larose. Dismantlability, Connectedness, and Mixing in Relational Structures. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{briceno_et_al:LIPIcs.ICALP.2019.29,
  author =	{Brice\~{n}o, Raimundo and Bulatov, Andrei A. and Dalmau, V{\'\i}ctor and Larose, Beno\^{i}t},
  title =	{{Dismantlability, Connectedness, and Mixing in Relational Structures}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.29},
  URN =		{urn:nbn:de:0030-drops-106059},
  doi =		{10.4230/LIPIcs.ICALP.2019.29},
  annote =	{Keywords: relational structure, constraint satisfaction problem, homomorphism, mixing properties, Gibbs measure}
}
  • Refine by Author
  • 1 Briceño, Raimundo
  • 1 Bulatov, Andrei A.
  • 1 Dalmau, Víctor
  • 1 Larose, Benoît

  • Refine by Classification
  • 1 Mathematics of computing → Paths and connectivity problems

  • Refine by Keyword
  • 1 Gibbs measure
  • 1 constraint satisfaction problem
  • 1 homomorphism
  • 1 mixing properties
  • 1 relational structure

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact