6 Search Results for "Butti, Silvia"

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2024.152
On Homomorphism Indistinguishability and Hypertree Depth

Authors: Benjamin Scheidt

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
GC^k is a logic introduced by Scheidt and Schweikardt (2023) to express properties of hypergraphs. It is similar to first-order logic with counting quantifiers (C) adapted to the hypergraph setting. It has distinct sets of variables for vertices and for hyperedges and requires vertex variables to be guarded by hyperedge variables on every quantification. We prove that two hypergraphs G, H satisfy the same sentences in the logic GC^k with guard depth at most k if, and only if, they are homomorphism indistinguishable over the class of hypergraphs of strict hypertree depth at most k. This lifts the analogous result for tree depth ≤ k and sentences of first-order logic with counting quantifiers of quantifier rank at most k due to Grohe (2020) from graphs to hypergraphs. The guard depth of a formula is the quantifier rank with respect to hyperedge variables, and strict hypertree depth is a restriction of hypertree depth as defined by Adler, Gavenčiak and Klimošová (2012). To justify this restriction, we show that for every H, the strict hypertree depth of H is at most 1 larger than its hypertree depth, and we give additional evidence that strict hypertree depth can be viewed as a reasonable generalisation of tree depth for hypergraphs.
Cite as

Benjamin Scheidt. On Homomorphism Indistinguishability and Hypertree Depth. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 152:1-152:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{scheidt:LIPIcs.ICALP.2024.152,
  author =	{Scheidt, Benjamin},
  title =	{{On Homomorphism Indistinguishability and Hypertree Depth}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{152:1--152:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.152},
  URN =		{urn:nbn:de:0030-drops-202958},
  doi =		{10.4230/LIPIcs.ICALP.2024.152},
  annote =	{Keywords: homomorphism indistinguishability, counting logics, guarded logics, hypergraphs, incidence graphs, tree depth, elimination forest, hypertree width}
}
Document
DOI: 10.4230/LIPIcs.CP.2022.2
Fixed-Template Promise Model Checking Problems

Authors: Kristina Asimi, Libor Barto, and Silvia Butti

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
The fixed-template constraint satisfaction problem (CSP) can be seen as the problem of deciding whether a given primitive positive first-order sentence is true in a fixed structure (also called model). We study a class of problems that generalizes the CSP simultaneously in two directions: we fix a set ℒ of quantifiers and Boolean connectives, and we specify two versions of each constraint, one strong and one weak. Given a sentence which only uses symbols from ℒ, the task is to distinguish whether the sentence is true in the strong sense, or it is false even in the weak sense. We classify the computational complexity of these problems for the existential positive equality-free fragment of first-order logic, i.e., ℒ = {∃,∧,∨}, and we prove some upper and lower bounds for the positive equality-free fragment, ℒ = {∃,∀,∧,∨}. The partial results are sufficient, e.g., for all extensions of the latter fragment.
Cite as

Kristina Asimi, Libor Barto, and Silvia Butti. Fixed-Template Promise Model Checking Problems. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{asimi_et_al:LIPIcs.CP.2022.2,
  author =	{Asimi, Kristina and Barto, Libor and Butti, Silvia},
  title =	{{Fixed-Template Promise Model Checking Problems}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{2:1--2:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.2},
  URN =		{urn:nbn:de:0030-drops-166310},
  doi =		{10.4230/LIPIcs.CP.2022.2},
  annote =	{Keywords: Model Checking Problem, First-Order Logic, Promise Constraint Satisfaction Problem, Multi-Homomorphism}
}
Document
DOI: 10.4230/LIPIcs.CP.2022.4
Weisfeiler-Leman Invariant Promise Valued CSPs

Authors: Libor Barto and Silvia Butti

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
In a recent line of work, Butti and Dalmau have shown that a fixed-template Constraint Satisfaction Problem is solvable by a certain natural linear programming relaxation (equivalent to the basic linear programming relaxation) if and only if it is solvable on a certain distributed network, and this happens if and only if its set of Yes instances is closed under Weisfeiler-Leman equivalence. We generalize this result to the much broader framework of fixed-template Promise Valued Constraint Satisfaction Problems. Moreover, we show that two commonly used linear programming relaxations are no longer equivalent in this broader framework.
Cite as

Libor Barto and Silvia Butti. Weisfeiler-Leman Invariant Promise Valued CSPs. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{barto_et_al:LIPIcs.CP.2022.4,
  author =	{Barto, Libor and Butti, Silvia},
  title =	{{Weisfeiler-Leman Invariant Promise Valued CSPs}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.4},
  URN =		{urn:nbn:de:0030-drops-166332},
  doi =		{10.4230/LIPIcs.CP.2022.4},
  annote =	{Keywords: Promise Valued Constraint Satisfaction Problem, Linear programming relaxation, Distributed algorithms, Symmetric fractional polymorphisms, Color refinement algorithm}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.27
Fractional Homomorphism, Weisfeiler-Leman Invariance, and the Sherali-Adams Hierarchy for the Constraint Satisfaction Problem

Authors: Silvia Butti and Víctor Dalmau

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
Given a pair of graphs 𝐀 and 𝐁, the problems of deciding whether there exists either a homomorphism or an isomorphism from 𝐀 to 𝐁 have received a lot of attention. While graph homomorphism is known to be NP-complete, the complexity of the graph isomorphism problem is not fully understood. A well-known combinatorial heuristic for graph isomorphism is the Weisfeiler-Leman test together with its higher order variants. On the other hand, both problems can be reformulated as integer programs and various LP methods can be applied to obtain high-quality relaxations that can still be solved efficiently. We study so-called fractional relaxations of these programs in the more general context where 𝐀 and 𝐁 are not graphs but arbitrary relational structures. We give a combinatorial characterization of the Sherali-Adams hierarchy applied to the homomorphism problem in terms of fractional isomorphism. Collaterally, we also extend a number of known results from graph theory to give a characterization of the notion of fractional isomorphism for relational structures in terms of the Weisfeiler-Leman test, equitable partitions, and counting homomorphisms from trees. As a result, we obtain a description of the families of CSPs that are closed under Weisfeiler-Leman invariance in terms of their polymorphisms as well as decidability by the first level of the Sherali-Adams hierarchy.
Cite as

Silvia Butti and Víctor Dalmau. Fractional Homomorphism, Weisfeiler-Leman Invariance, and the Sherali-Adams Hierarchy for the Constraint Satisfaction Problem. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{butti_et_al:LIPIcs.MFCS.2021.27,
  author =	{Butti, Silvia and Dalmau, V{\'\i}ctor},
  title =	{{Fractional Homomorphism, Weisfeiler-Leman Invariance, and the Sherali-Adams Hierarchy for the Constraint Satisfaction Problem}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{27:1--27:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.27},
  URN =		{urn:nbn:de:0030-drops-144679},
  doi =		{10.4230/LIPIcs.MFCS.2021.27},
  annote =	{Keywords: Weisfeiler-Leman algorithm, Sherali-Adams hierarchy, Graph homomorphism, Constraint Satisfaction Problem}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.20
The Complexity of the Distributed Constraint Satisfaction Problem

Authors: Silvia Butti and Victor Dalmau

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
We study the complexity of the Distributed Constraint Satisfaction Problem (DCSP) on a synchronous, anonymous network from a theoretical standpoint. In this setting, variables and constraints are controlled by agents which communicate with each other by sending messages through fixed communication channels. Our results endorse the well-known fact from classical CSPs that the complexity of fixed-template computational problems depends on the template’s invariance under certain operations. Specifically, we show that DCSP(Γ) is polynomial-time tractable if and only if Γ is invariant under symmetric polymorphisms of all arities. Otherwise, there are no algorithms that solve DCSP(Γ) in finite time. We also show that the same condition holds for the search variant of DCSP. Collaterally, our results unveil a feature of the processes' neighbourhood in a distributed network, its iterated degree, which plays a major role in the analysis. We explore this notion establishing a tight connection with the basic linear programming relaxation of a CSP.
Cite as

Silvia Butti and Victor Dalmau. The Complexity of the Distributed Constraint Satisfaction Problem. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{butti_et_al:LIPIcs.STACS.2021.20,
  author =	{Butti, Silvia and Dalmau, Victor},
  title =	{{The Complexity of the Distributed Constraint Satisfaction Problem}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.20},
  URN =		{urn:nbn:de:0030-drops-136654},
  doi =		{10.4230/LIPIcs.STACS.2021.20},
  annote =	{Keywords: Constraint Satisfaction Problems, Distributed Algorithms, Polymorphisms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.17
Sparsification of Binary CSPs

Authors: Silvia Butti and Stanislav Živný

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
A cut epsilon-sparsifier of a weighted graph G is a re-weighted subgraph of G of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of epsilon. Since their introduction by Benczúr and Karger [STOC'96], cut sparsifiers have proved extremely influential and found various applications. Going beyond cut sparsifiers, Filtser and Krauthgamer [SIDMA'17] gave a precise classification of which binary Boolean CSPs are sparsifiable. In this paper, we extend their result to binary CSPs on arbitrary finite domains.
Cite as

Silvia Butti and Stanislav Živný. Sparsification of Binary CSPs. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 17:1-17:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{butti_et_al:LIPIcs.STACS.2019.17,
  author =	{Butti, Silvia and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Sparsification of Binary CSPs}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{17:1--17:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.17},
  URN =		{urn:nbn:de:0030-drops-102564},
  doi =		{10.4230/LIPIcs.STACS.2019.17},
  annote =	{Keywords: constraint satisfaction problems, minimum cuts, sparsification}
}
  • Refine by Author
  • 5 Butti, Silvia
  • 2 Barto, Libor
  • 1 Asimi, Kristina
  • 1 Dalmau, Victor
  • 1 Dalmau, Víctor
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Constraint and logic programming
  • 1 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Hypergraphs
  • 1 Theory of computation → Complexity theory and logic
  • 1 Theory of computation → Finite Model Theory
  • Show More...

  • Refine by Keyword
  • 1 Color refinement algorithm
  • 1 Constraint Satisfaction Problem
  • 1 Constraint Satisfaction Problems
  • 1 Distributed Algorithms
  • 1 Distributed algorithms
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2021
  • 2 2022
  • 1 2019
  • 1 2024

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact