23 Search Results for "Bulatov, Andrei A."

Document
DOI: 10.4230/LIPIcs.STACS.2025.60
Modular Counting CSP: Reductions and Algorithms

Authors: Amirhossein Kazeminia and Andrei A. Bulatov

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
The Constraint Satisfaction Problem (CSP) is ubiquitous in various areas of mathematics and computer science. Many of its variations have been studied including the Counting CSP, where the goal is to find the number of solutions to a CSP instance. The complexity of finding the exact number of solutions of a CSP is well understood (Bulatov, 2013, and Dyer and Richerby, 2013) and the focus has shifted to other variations of the Counting CSP such as counting the number of solutions modulo an integer. This problem has attracted considerable attention recently. In the case of CSPs based on undirected graphs Bulatov and Kazeminia (STOC 2022) obtained a complexity classification for the problem of counting solutions modulo p for arbitrary prime p. In this paper we report on the progress made towards a similar classification for the general CSP, not necessarily based on graphs. We identify several features that make the general case very different from the graph case such as a stronger form of rigidity and the structure of automorphisms of powers of relational structures. We provide a solution algorithm in the case p = 2 that works under some additional conditions and prove the hardness of the problem under some assumptions about automorphisms of the powers of the relational structure. We also reduce the general CSP to the case that only uses binary relations satisfying strong additional conditions.
Cite as

Amirhossein Kazeminia and Andrei A. Bulatov. Modular Counting CSP: Reductions and Algorithms. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 60:1-60:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kazeminia_et_al:LIPIcs.STACS.2025.60,
  author =	{Kazeminia, Amirhossein and Bulatov, Andrei A.},
  title =	{{Modular Counting CSP: Reductions and Algorithms}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{60:1--60:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.60},
  URN =		{urn:nbn:de:0030-drops-228853},
  doi =		{10.4230/LIPIcs.STACS.2025.60},
  annote =	{Keywords: Constraint Satisfaction Problem, Modular Counting}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2024.148
An Order out of Nowhere: A New Algorithm for Infinite-Domain CSPs

Authors: Antoine Mottet, Tomáš Nagy, and Michael Pinsker

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

Abstract
We consider the problem of satisfiability of sets of constraints in a given set of finite uniform hypergraphs. While the problem under consideration is similar in nature to the problem of satisfiability of constraints in graphs, the classical complexity reduction to finite-domain CSPs that was used in the proof of the complexity dichotomy for such problems cannot be used as a black box in our case. We therefore introduce an algorithmic technique inspired by classical notions from the theory of finite-domain CSPs, and prove its correctness based on symmetries that depend on a linear order that is external to the structures under consideration. Our second main result is a P/NP-complete complexity dichotomy for such problems over many sets of uniform hypergraphs. The proof is based on the translation of the problem into the framework of constraint satisfaction problems (CSPs) over infinite uniform hypergraphs. Our result confirms in particular the Bodirsky-Pinsker conjecture for CSPs of first-order reducts of some homogeneous hypergraphs. This forms a vast generalization of previous work by Bodirsky-Pinsker (STOC'11) and Bodirsky-Martin-Pinsker-Pongrácz (ICALP'16) on graph satisfiability.
Cite as

Antoine Mottet, Tomáš Nagy, and Michael Pinsker. An Order out of Nowhere: A New Algorithm for Infinite-Domain CSPs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 148:1-148:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mottet_et_al:LIPIcs.ICALP.2024.148,
  author =	{Mottet, Antoine and Nagy, Tom\'{a}\v{s} and Pinsker, Michael},
  title =	{{An Order out of Nowhere: A New Algorithm for Infinite-Domain CSPs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{148:1--148: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.148},
  URN =		{urn:nbn:de:0030-drops-202912},
  doi =		{10.4230/LIPIcs.ICALP.2024.148},
  annote =	{Keywords: Constraint Satisfaction Problems, Hypergraphs, Polymorphisms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.70
Homomorphism Tensors and Linear Equations

Authors: Martin Grohe, Gaurav Rattan, and Tim Seppelt

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Lovász (1967) showed that two graphs G and H are isomorphic if and only if they are homomorphism indistinguishable over the class of all graphs, i.e. for every graph F, the number of homomorphisms from F to G equals the number of homomorphisms from F to H. Recently, homomorphism indistinguishability over restricted classes of graphs such as bounded treewidth, bounded treedepth and planar graphs, has emerged as a surprisingly powerful framework for capturing diverse equivalence relations on graphs arising from logical equivalence and algebraic equation systems. In this paper, we provide a unified algebraic framework for such results by examining the linear-algebraic and representation-theoretic structure of tensors counting homomorphisms from labelled graphs. The existence of certain linear transformations between such homomorphism tensor subspaces can be interpreted both as homomorphism indistinguishability over a graph class and as feasibility of an equational system. Following this framework, we obtain characterisations of homomorphism indistinguishability over several natural graph classes, namely trees of bounded degree, graphs of bounded pathwidth (answering a question of Dell et al. (2018)), and graphs of bounded treedepth.
Cite as

Martin Grohe, Gaurav Rattan, and Tim Seppelt. Homomorphism Tensors and Linear Equations. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 70:1-70:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.ICALP.2022.70,
  author =	{Grohe, Martin and Rattan, Gaurav and Seppelt, Tim},
  title =	{{Homomorphism Tensors and Linear Equations}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{70:1--70:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.70},
  URN =		{urn:nbn:de:0030-drops-164113},
  doi =		{10.4230/LIPIcs.ICALP.2022.70},
  annote =	{Keywords: homomorphisms, labelled graphs, treewidth, pathwidth, treedepth, linear equations, Sherali-Adams relaxation, Wiegmann-Specht Theorem, Weisfeiler-Leman}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.18
The Ideal Membership Problem and Abelian Groups

Authors: Andrei A. Bulatov and Akbar Rafiey

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Given polynomials f_0, f_1, …, f_k the Ideal Membership Problem, IMP for short, asks if f₀ belongs to the ideal generated by f_1, …, f_k. In the search version of this problem the task is to find a proof of this fact. The IMP is a well-known fundamental problem with numerous applications, for instance, it underlies many proof systems based on polynomials such as Nullstellensatz, Polynomial Calculus, and Sum-of-Squares. Although the IMP is in general intractable, in many important cases it can be efficiently solved. Mastrolilli [SODA'19] initiated a systematic study of IMPs for ideals arising from Constraint Satisfaction Problems (CSPs), parameterized by constraint languages, denoted IMP(Γ). The ultimate goal of this line of research is to classify all such IMPs accordingly to their complexity. Mastrolilli achieved this goal for IMPs arising from CSP(Γ) where Γ is a Boolean constraint language, while Bulatov and Rafiey [arXiv'21] advanced these results to several cases of CSPs over finite domains. In this paper we consider IMPs arising from CSPs over "affine" constraint languages, in which constraints are subgroups (or their cosets) of direct products of Abelian groups. This kind of CSPs include systems of linear equations and are considered one of the most important types of tractable CSPs. Some special cases of the problem have been considered before by Bharathi and Mastrolilli [MFCS'21] for linear equation modulo 2, and by Bulatov and Rafiey [arXiv'21] to systems of linear equations over GF(p), p prime. Here we prove that if Γ is an affine constraint language then IMP(Γ) is solvable in polynomial time assuming the input polynomial has bounded degree.
Cite as

Andrei A. Bulatov and Akbar Rafiey. The Ideal Membership Problem and Abelian Groups. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:LIPIcs.STACS.2022.18,
  author =	{Bulatov, Andrei A. and Rafiey, Akbar},
  title =	{{The Ideal Membership Problem and Abelian Groups}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra 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.2022.18},
  URN =		{urn:nbn:de:0030-drops-158280},
  doi =		{10.4230/LIPIcs.STACS.2022.18},
  annote =	{Keywords: Polynomial Ideal Membership, Constraint Satisfaction Problems, Polymorphisms, Gr\"{o}bner Bases, Abelian Groups}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.16
Ideal Membership Problem for Boolean Minority and Dual Discriminator

Authors: Arpitha P. Bharathi and Monaldo Mastrolilli

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

Abstract
The polynomial Ideal Membership Problem (IMP) tests if an input polynomial f ∈ 𝔽[x_1,… ,x_n] with coefficients from a field 𝔽 belongs to a given ideal I ⊆ 𝔽[x_1,… ,x_n]. It is a well-known fundamental problem with many important applications, though notoriously intractable in the general case. In this paper we consider the IMP for polynomial ideals encoding combinatorial problems and where the input polynomial f has degree at most d = O(1) (we call this problem IMP_d). A dichotomy result between "hard" (NP-hard) and "easy" (polynomial time) IMPs was achieved for Constraint Satisfaction Problems over finite domains [Andrei A. Bulatov, 2017; Dmitriy Zhuk, 2020] (this is equivalent to IMP_0) and IMP_d for the Boolean domain [Mastrolilli, 2019], both based on the classification of the IMP through functions called polymorphisms. For the latter result, there are only six polymorphisms to be studied in order to achieve a full dichotomy result for the IMP_d. The complexity of the IMP_d for five of these polymorphisms has been solved in [Mastrolilli, 2019] whereas for the ternary minority polymorphism it was incorrectly declared in [Mastrolilli, 2019] to have been resolved by a previous result. In this paper we provide the missing link by proving that the IMP_d for Boolean combinatorial ideals whose constraints are closed under the minority polymorphism can be solved in polynomial time. This completes the identification of the precise borderline of tractability for the IMP_d for constrained problems over the Boolean domain. We also prove that the proof of membership for the IMP_d for problems constrained by the dual discriminator polymorphism over any finite domain can also be found in polynomial time. Bulatov and Rafiey [Andrei A. Bulatov and Akbar Rafiey, 2020] recently proved that the IMP_d for this polymorphism is decidable in polynomial time, without needing a proof of membership. Our result gives a proof of membership and can be used in applications such as Nullstellensatz and Sum-of-Squares proofs.
Cite as

Arpitha P. Bharathi and Monaldo Mastrolilli. Ideal Membership Problem for Boolean Minority and Dual Discriminator. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bharathi_et_al:LIPIcs.MFCS.2021.16,
  author =	{Bharathi, Arpitha P. and Mastrolilli, Monaldo},
  title =	{{Ideal Membership Problem for Boolean Minority and Dual Discriminator}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{16:1--16:20},
  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.16},
  URN =		{urn:nbn:de:0030-drops-144560},
  doi =		{10.4230/LIPIcs.MFCS.2021.16},
  annote =	{Keywords: Polynomial ideal membership, Polymorphisms, Gr\"{o}bner basis theory, Constraint satisfaction problems}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2021.2
Symmetries and Complexity (Invited Talk)

Authors: Andrei A. Bulatov

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
The Constraint Satisfaction Problem (CSP) and a number of problems related to it have seen major advances during the past three decades. In many cases the leading driving force that made these advances possible has been the so-called algebraic approach that uses symmetries of constraint problems and tools from algebra to determine the complexity of problems and design solution algorithms. In this presentation we give a high level overview of the main ideas behind the algebraic approach illustrated by examples ranging from the regular CSP, to counting problems, to optimization and promise problems, to graph isomorphism.
Cite as

Andrei A. Bulatov. Symmetries and Complexity (Invited Talk). In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bulatov:LIPIcs.ICALP.2021.2,
  author =	{Bulatov, Andrei A.},
  title =	{{Symmetries and Complexity}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{2:1--2:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.2},
  URN =		{urn:nbn:de:0030-drops-140717},
  doi =		{10.4230/LIPIcs.ICALP.2021.2},
  annote =	{Keywords: constraint problems, algebraic approach, dichotomy theorems}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.13
Ideal Membership Problem and a Majority Polymorphism over the Ternary Domain

Authors: Arpitha P. Bharathi and Monaldo Mastrolilli

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
The Ideal Membership Problem (IMP) asks if an input polynomial f ∈ 𝔽[x₁,… ,x_n] with coefficients from a field 𝔽 belongs to an input ideal I ⊆ 𝔽[x₁,… ,x_n]. It is a well-known fundamental problem with many important applications, though notoriously intractable in the general case. In this paper we consider the IMP for polynomial ideals encoding combinatorial problems and where the input polynomial f has degree at most d = O(1) (we call this problem IMP_d). Our main interest is in understanding when the inherent combinatorial structure of the ideals makes the IMP_d "hard" (NP-hard) or "easy" (polynomial time) to solve. Such a dichotomy result between "hard" and "easy" IMPs was recently achieved for Constraint Satisfaction Problems over finite domains [Andrei A. Bulatov, 2017; Dmitriy Zhuk, 2017] (this is equivalent to IMP₀) and IMP_d for the Boolean domain [Mastrolilli, 2019], both based on the classification of the IMP through functions called polymorphisms. For the latter result, each polymorphism determined the complexity of the computation of a suitable Gröbner basis. In this paper we consider a 3-element domain and a majority polymorphism (constraints under this polymorphism are a generalisation of the 2-SAT problem). By using properties of the majority polymorphism and assuming graded lexicographic ordering of monomials, we show that the reduced Gröbner basis of ideals whose varieties are closed under the majority polymorphism can be computed in polynomial time. This proves polynomial time solvability of the IMP_d for these constrained problems. We conjecture that this result can be extended to a general finite domain of size k = O(1). This is a first step towards the long term and challenging goal of generalizing the dichotomy results of solvability of the IMP_d for a finite domain.
Cite as

Arpitha P. Bharathi and Monaldo Mastrolilli. Ideal Membership Problem and a Majority Polymorphism over the Ternary Domain. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bharathi_et_al:LIPIcs.MFCS.2020.13,
  author =	{Bharathi, Arpitha P. and Mastrolilli, Monaldo},
  title =	{{Ideal Membership Problem and a Majority Polymorphism over the Ternary Domain}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.13},
  URN =		{urn:nbn:de:0030-drops-126829},
  doi =		{10.4230/LIPIcs.MFCS.2020.13},
  annote =	{Keywords: Polynomial ideal membership, Polymorphisms, Gr\"{o}bner basis theory, Constraint satisfaction problems}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.21
Counting Homomorphisms in Plain Exponential Time

Authors: Andrei A. Bulatov and Amineh Dadsetan

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

Abstract
In the counting Graph Homomorphism problem (#GraphHom) the question is: Given graphs G,H, find the number of homomorphisms from G to H. This problem is generally #P-complete, moreover, Cygan et al. proved that unless the Exponential Time Hypothesis fails there is no algorithm that solves this problem in time O(|V(H)|^o(|V(G)|)). This, however, does not rule out the possibility that faster algorithms exist for restricted problems of this kind. Wahlström proved that #GraphHom can be solved in plain exponential time, that is, in time O((2k+1)^(|V(G)|+|V(H)|) poly(|V(H)|,|V(G)|)) provided H has clique width k. We generalize this result to a larger class of graphs, and also identify several other graph classes that admit a plain exponential algorithm for #GraphHom.
Cite as

Andrei A. Bulatov and Amineh Dadsetan. Counting Homomorphisms in Plain Exponential Time. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:LIPIcs.ICALP.2020.21,
  author =	{Bulatov, Andrei A. and Dadsetan, Amineh},
  title =	{{Counting Homomorphisms in Plain Exponential Time}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{21:1--21: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.21},
  URN =		{urn:nbn:de:0030-drops-124287},
  doi =		{10.4230/LIPIcs.ICALP.2020.21},
  annote =	{Keywords: graph homomorphisms, plain exponential time, clique width}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.66
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.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
DOI: 10.4230/LIPIcs.MFCS.2019.36
On the Strength of Uniqueness Quantification in Primitive Positive Formulas

Authors: Victor Lagerkvist and Gustav Nordh

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
Uniqueness quantification (Exists!) is a quantifier in first-order logic where one requires that exactly one element exists satisfying a given property. In this paper we investigate the strength of uniqueness quantification when it is used in place of existential quantification in conjunctive formulas over a given set of relations Gamma, so-called primitive positive definitions (pp-definitions). We fully classify the Boolean sets of relations where uniqueness quantification has the same strength as existential quantification in pp-definitions and give several results valid for arbitrary finite domains. We also consider applications of Exists!-quantified pp-definitions in computer science, which can be used to study the computational complexity of problems where the number of solutions is important. Using our classification we give a new and simplified proof of the trichotomy theorem for the unique satisfiability problem, and prove a general result for the unique constraint satisfaction problem. Studying these problems in a more rigorous framework also turns out to be advantageous in the context of lower bounds, and we relate the complexity of these problems to the exponential-time hypothesis.
Cite as

Victor Lagerkvist and Gustav Nordh. On the Strength of Uniqueness Quantification in Primitive Positive Formulas. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{lagerkvist_et_al:LIPIcs.MFCS.2019.36,
  author =	{Lagerkvist, Victor and Nordh, Gustav},
  title =	{{On the Strength of Uniqueness Quantification in Primitive Positive Formulas}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{36:1--36:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.36},
  URN =		{urn:nbn:de:0030-drops-109808},
  doi =		{10.4230/LIPIcs.MFCS.2019.36},
  annote =	{Keywords: Primitive positive definitions, clone theory, constraint satisfaction problems}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.59
Counting Homomorphisms Modulo a Prime Number

Authors: Amirhossein Kazeminia and Andrei A. Bulatov

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
Counting problems in general and counting graph homomorphisms in particular have numerous applications in combinatorics, computer science, statistical physics, and elsewhere. One of the most well studied problems in this area is #GraphHom(H) - the problem of finding the number of homomorphisms from a given graph G to the graph H. Not only the complexity of this basic problem is known, but also of its many variants for digraphs, more general relational structures, graphs with weights, and others. In this paper we consider a modification of #GraphHom(H), the #_{p}GraphHom(H) problem, p a prime number: Given a graph G, find the number of homomorphisms from G to H modulo p. In a series of papers Faben and Jerrum, and Göbel et al. determined the complexity of #_{2}GraphHom(H) in the case H (or, in fact, a certain graph derived from H) is square-free, that is, does not contain a 4-cycle. Also, Göbel et al. found the complexity of #_{p}GraphHom(H) when H is a tree for an arbitrary prime p. Here we extend the above result to show that the #_{p}GraphHom(H) problem is #_{p}P-hard whenever the derived graph associated with H is square-free and is not a star, which completely classifies the complexity of #_{p}GraphHom(H) for square-free graphs H.
Cite as

Amirhossein Kazeminia and Andrei A. Bulatov. Counting Homomorphisms Modulo a Prime Number. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 59:1-59:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kazeminia_et_al:LIPIcs.MFCS.2019.59,
  author =	{Kazeminia, Amirhossein and Bulatov, Andrei A.},
  title =	{{Counting Homomorphisms Modulo a Prime Number}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{59:1--59:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.59},
  URN =		{urn:nbn:de:0030-drops-110032},
  doi =		{10.4230/LIPIcs.MFCS.2019.59},
  annote =	{Keywords: graph homomorphism, modular counting, computational hardness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.60
Approximate Counting CSP Seen from the Other Side

Authors: Andrei A. Bulatov and Stanislav Živný

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
In this paper we study the complexity of counting Constraint Satisfaction Problems (CSPs) of the form #CSP(C,-), in which the goal is, given a relational structure A from a class C of structures and an arbitrary structure B, to find the number of homomorphisms from A to B. Flum and Grohe showed that #CSP(C,-) is solvable in polynomial time if C has bounded treewidth [FOCS'02]. Building on the work of Grohe [JACM'07] on decision CSPs, Dalmau and Jonsson then showed that, if C is a recursively enumerable class of relational structures of bounded arity, then assuming FPT != #W[1], there are no other cases of #CSP(C,-) solvable exactly in polynomial time (or even fixed-parameter time) [TCS'04]. We show that, assuming FPT != W[1] (under randomised parametrised reductions) and for C satisfying certain general conditions, #CSP(C,-) is not solvable even approximately for C of unbounded treewidth; that is, there is no fixed parameter tractable (and thus also not fully polynomial) randomised approximation scheme for #CSP(C,-). In particular, our condition generalises the case when C is closed under taking minors.
Cite as

Andrei A. Bulatov and Stanislav Živný. Approximate Counting CSP Seen from the Other Side. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:LIPIcs.MFCS.2019.60,
  author =	{Bulatov, Andrei A. and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Approximate Counting CSP Seen from the Other Side}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{60:1--60:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.60},
  URN =		{urn:nbn:de:0030-drops-110041},
  doi =		{10.4230/LIPIcs.MFCS.2019.60},
  annote =	{Keywords: constraint satisfaction, approximate counting, homomorphisms}
}
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.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}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.91
Toward a Dichotomy for Approximation of H-Coloring

Authors: Akbar Rafiey, Arash Rafiey, and Thiago Santos

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

Abstract
Given two (di)graphs G, H and a cost function c:V(G) x V(H) -> Q_{>= 0} cup {+infty}, in the minimum cost homomorphism problem, MinHOM(H), we are interested in finding a homomorphism f:V(G)-> V(H) (a.k.a H-coloring) that minimizes sum limits_{v in V(G)}c(v,f(v)). The complexity of exact minimization of this problem is well understood [Pavol Hell and Arash Rafiey, 2012], and the class of digraphs H, for which the MinHOM(H) is polynomial time solvable is a small subset of all digraphs. In this paper, we consider the approximation of MinHOM within a constant factor. In terms of digraphs, MinHOM(H) is not approximable if H contains a digraph asteroidal triple (DAT). We take a major step toward a dichotomy classification of approximable cases. We give a dichotomy classification for approximating the MinHOM(H) when H is a graph (i.e. symmetric digraph). For digraphs, we provide constant factor approximation algorithms for two important classes of digraphs, namely bi-arc digraphs (digraphs with a conservative semi-lattice polymorphism or min-ordering), and k-arc digraphs (digraphs with an extended min-ordering). Specifically, we show that: - Dichotomy for Graphs: MinHOM(H) has a 2|V(H)|-approximation algorithm if graph H admits a conservative majority polymorphims (i.e. H is a bi-arc graph), otherwise, it is inapproximable; - MinHOM(H) has a |V(H)|^2-approximation algorithm if H is a bi-arc digraph; - MinHOM(H) has a |V(H)|^2-approximation algorithm if H is a k-arc digraph. In conclusion, we show the importance of these results and provide insights for achieving a dichotomy classification of approximable cases. Our constant factors depend on the size of H. However, the implementation of our algorithms provides a much better approximation ratio. It leaves open to investigate a classification of digraphs H, where MinHOM(H) admits a constant factor approximation algorithm that is independent of |V(H)|.
Cite as

Akbar Rafiey, Arash Rafiey, and Thiago Santos. Toward a Dichotomy for Approximation of H-Coloring. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 91:1-91:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{rafiey_et_al:LIPIcs.ICALP.2019.91,
  author =	{Rafiey, Akbar and Rafiey, Arash and Santos, Thiago},
  title =	{{Toward a Dichotomy for Approximation of H-Coloring}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{91:1--91:16},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.91},
  URN =		{urn:nbn:de:0030-drops-106678},
  doi =		{10.4230/LIPIcs.ICALP.2019.91},
  annote =	{Keywords: Approximation algorithms, minimum cost homomorphism, randomized rounding}
}
Document
DOI: 10.4230/DagRep.5.7.22
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301)

Authors: Andrei A. Bulatov, Venkatesan Guruswami, Andrei Krokhin, and Dániel Marx

Published in: Dagstuhl Reports, Volume 5, Issue 7 (2016)

Abstract
During the past two decades, an impressive array of diverse methods from several different mathematical fields, including algebra, logic, mathematical programming, probability theory, graph theory, and combinatorics, have been used to analyze both the computational complexity and approximabilty of algorithmic tasks related to the constraint satisfaction problem (CSP), as well as the applicability/limitations of algorithmic techniques. This research direction develops at an impressive speed, regularly producing very strong and general results. The Dagstuhl Seminar 15301 "The Constraint Satisfaction Problem: Complexity and Approximability" was aimed at bringing together researchers using all the different techniques in the study of the CSP, so that they can share their insights obtained during the past three years. This report documents the material presented during the course of the seminar.
Cite as

Andrei A. Bulatov, Venkatesan Guruswami, Andrei Krokhin, and Dániel Marx. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301). In Dagstuhl Reports, Volume 5, Issue 7, pp. 22-41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{bulatov_et_al:DagRep.5.7.22,
  author =	{Bulatov, Andrei A. and Guruswami, Venkatesan and Krokhin, Andrei and Marx, D\'{a}niel},
  title =	{{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301)}},
  pages =	{22--41},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{7},
  editor =	{Bulatov, Andrei A. and Guruswami, Venkatesan and Krokhin, Andrei and Marx, D\'{a}niel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.7.22},
  URN =		{urn:nbn:de:0030-drops-56714},
  doi =		{10.4230/DagRep.5.7.22},
  annote =	{Keywords: Constraint satisfaction problem (CSP), Computational complexity, CSP dichotomy conjecture, Hardness of approximation, Unique games conjecture, Fixed-parameter tractability, Descriptive complexity, Universal algebra, Logic, Decomposition methods}
}
  • Refine by Author
  • 12 Bulatov, Andrei A.
  • 4 Grohe, Martin
  • 3 Krokhin, Andrei
  • 2 Bharathi, Arpitha P.
  • 2 Dalmau, Victor
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 4 Polymorphisms
  • 3 CSP dichotomy conjecture
  • 3 Constraint Satisfaction Problems
  • 3 Constraint satisfaction problem (CSP)
  • 2 Constraint satisfaction problems
  • Show More...

  • Refine by Type
  • 23 document

  • Refine by Publication Year
  • 5 2010
  • 5 2019
  • 3 2020
  • 2 2021
  • 2 2022
  • Show More...

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 About DROPS Imprint Privacy Contact