DROPS

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

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}
}

Search Results

Documents authored by Kazeminia, Amirhossein

Modular Counting CSP: Reductions and Algorithms

Abstract

Cite as

Counting Homomorphisms Modulo a Prime Number

Abstract

Cite as

Thanks for your feedback!

Could not send message