21 Search Results for "Bulatov, Andrei A."

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}
}
Document
DOI: 10.4230/LIPIcs.CSL.2013.149
Descriptive complexity of approximate counting CSPs

Authors: Andrei Bulatov, Victor Dalmau, and Marc Thurley

Published in: LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013)

Abstract
Motivated by Fagin's characterization of NP, Saluja et al. have introduced a logic based frame- work for expressing counting problems. In this setting, a counting problem (seen as a mapping C from structures to non-negative integers) is `defined’ by a first-order sentence phi if for every instance A of the problem, the number of possible satisfying assignments of the variables of phi in A is equal to C(A). The logic RHPI_1 has been introduced by Dyer et al. in their study of the counting complexity class #BIS. The interest in the class #BIS stems from the fact that, it is quite plausible that the problems in #BIS are not #P-hard, nor they admit a fully polynomial randomized approximation scheme. In the present paper we investigate which counting constraint satisfaction problems #CSP(H) are definable in the monotone fragment of RHPI_1. We prove that #CSP(H) is definable in monotone RHPI_1 whenever H is invariant under meet and join operations of a distributive lattice. We prove that the converse also holds if H contains the equality relation. We also prove similar results for counting CSPs expressible by linear Datalog. The results in this case are very similar to those for monotone RHPI1, with the addition that H has, additionally, \top (the greatest element of the lattice) as a polymorphism.
Cite as

Andrei Bulatov, Victor Dalmau, and Marc Thurley. Descriptive complexity of approximate counting CSPs. In Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 23, pp. 149-164, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:LIPIcs.CSL.2013.149,
  author =	{Bulatov, Andrei and Dalmau, Victor and Thurley, Marc},
  title =	{{Descriptive complexity of approximate counting CSPs}},
  booktitle =	{Computer Science Logic 2013 (CSL 2013)},
  pages =	{149--164},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-60-6},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{23},
  editor =	{Ronchi Della Rocca, Simona},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.149},
  URN =		{urn:nbn:de:0030-drops-41955},
  doi =		{10.4230/LIPIcs.CSL.2013.149},
  annote =	{Keywords: Constraint Satisfaction Problems, Approximate Counting, Descriptive Complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.302
Log-supermodular functions, functional clones and counting CSPs

Authors: Andrei A. Bulatov, Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
Motivated by a desire to understand the computational complexity of counting constraint satisfaction problems (counting CSPs), particularly the complexity of approximation, we study functional clones of functions on the Boolean domain, which are analogous to the familiar relational clones constituting Post's lattice. One of these clones is the collection of log-supermodular (lsm) functions, which turns out to play a significant role in classifying counting CSPs. In our study, we assume that non-negative unary functions (weights) are available. Given this, we prove that there are no functional clones lying strictly between the clone of lsm functions and the total clone (containing all functions). Thus, any counting CSP that contains a single nontrivial non-lsm function is computationally as hard as any problem in #P. Furthermore, any non-trivial functional clone (in a sense that will be made precise below) contains the binary function "implies". As a consequence, all non-trivial counting CSPs (with non-negative unary weights assumed to be available) are computationally at least as difficult as #BIS, the problem of counting independent sets in a bipartite graph. There is empirical evidence that #BIS is hard to solve, even approximately.
Cite as

Andrei A. Bulatov, Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. Log-supermodular functions, functional clones and counting CSPs. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 302-313, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{bulatov_et_al:LIPIcs.STACS.2012.302,
  author =	{Bulatov, Andrei A. and Dyer, Martin and Goldberg, Leslie Ann and Jerrum, Mark},
  title =	{{Log-supermodular functions, functional clones and counting CSPs}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{302--313},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.302},
  URN =		{urn:nbn:de:0030-drops-34078},
  doi =		{10.4230/LIPIcs.STACS.2012.302},
  annote =	{Keywords: counting constraint satisfaction problems, approximation, complexity}
}
  • Refine by Author
  • 11 Bulatov, Andrei A.
  • 4 Grohe, Martin
  • 3 Krokhin, Andrei
  • 2 Bharathi, Arpitha P.
  • 2 Dalmau, Victor
  • Show More...

  • Refine by Classification

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

  • Refine by Type
  • 21 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