Modular Counting CSP: Reductions and Algorithms

Kazeminia, Amirhossein; Bulatov, Andrei A.

doi:10.4230/LIPIcs.STACS.2025.60

Modular Counting CSP: Reductions and Algorithms

Amirhossein Kazeminia Simon Fraser University, Burnaby, Canada Andrei A. Bulatov Simon Fraser University, Barnaby, Canada

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.

Keywords and phrases:

Constraint Satisfaction Problem, Modular Counting

Funding:

Andrei A. Bulatov: NSERC Discovery Grant.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Problems, reductions and completeness ; Theory of computation

\rightarrow

Constraint and logic programming

Editors:

Olaf Beyersdorff, Michał Pilipczuk, Elaine Pimentel, and Nguyễn Kim Thắng

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Counting problems in general have been intensively studied since the pioneering work by Valiant [34, 33]. One of the most interesting and well studied problems in this area is the Counting Constraint Satisfaction Problem ( $\#\mathsf{CSP}$ ), which provides a generic framework for a wide variety of counting combinatorial problems that arise frequently in multiple disciplines such as logic, graph theory, and artificial intelligence. The counting $\mathsf{CSP}$ also allows for generalizations including weighted CSPs and partition functions [2, 7] that yield connections with areas such as statistical physics, see, e.g. [27, 32]. While the complexity of exact counting solutions of a $\mathsf{CSP}$ is now well-understood [13, 3, 14, 12], modular counting such as finding the parity of the number of solutions remains widely open.

Homomorphisms and the Constraint Satisfaction Problem.

The most convenient way to introduce CSPs is through homomorphisms of relational structures. A relational signature $\sigma$ is a collection of relational symbols each of which is assigned a positive integer, the arity of the symbol. A relational structure $\mathcal{H}$ with signature $\sigma$ is a set $H$ and an interpretation $\mathcal{R}^{\mathcal{H}}$ of each $\mathcal{R}\in\sigma$ , where $\mathcal{R}^{\mathcal{H}}$ is a relation or a predicate on $H$ whose arity equals that of $\mathcal{R}$ . The set $H$ is said to be the base set or the universe of $\mathcal{H}$ . We will use the same letter for the base set as for the structure, only in the regular font. A structure with signature $\sigma$ is often called a $\sigma$ -structure. Structures with the same signature are called similar.

Let $\mathcal{G},\mathcal{H}$ be similar structures with signature $\sigma$ . A homomorphism from $\mathcal{G}$ to $\mathcal{H}$ is a mapping $\varphi:G\to H$ such that for any $\mathcal{R}\in\sigma$ , say, of arity $r$ , if $\mathcal{R}^{\mathcal{G}}(a_{1},\dots,a_{r})$ is true for $a_{1},\dots,a_{r}\in G$ , then $\mathcal{R}^{\mathcal{H}}(\varphi(a_{1}),\dots,\varphi(a_{r}))$ is also true. The set of all homomorphisms from $\mathcal{G}$ to $\mathcal{H}$ is denoted $\mathsf{Hom}(\mathcal{G},\mathcal{H})$ . The cardinality of $\mathsf{Hom}(\mathcal{G},\mathcal{H})$ is denoted by $\mathsf{hom}(\mathcal{G},\mathcal{H})$ . A homomorphism $\varphi$ is an isomorphism if it is bijective and the inverse mapping $\varphi^{-1}$ is a homomorphism from $\mathcal{H}$ to $\mathcal{G}$ . A homomorphism of a structure to itself is called an endomorphism, and an isomorphism to itself is called an automorphism.

Following Feder and Vardi [17], in a $\mathsf{CSP}$ , the goal is, given similar relational structures $\mathcal{G},\mathcal{H}$ , to decide whether there is a homomorphism from $\mathcal{G}$ to $\mathcal{H}$ . The restricted problem in which $\mathcal{H}$ is fixed and only $\mathcal{G}$ is given as an input is denoted by $\mathsf{CSP}(\mathcal{H})$ . The complexity of such problems is well understood [4, 35].

Counting CSP.

In the (exact) Counting $\mathsf{CSP}$ the goal is to find the number $\mathsf{hom}(\mathcal{G},\mathcal{H})$ of homomorphisms from a structure $\mathcal{G}$ to a similar structure $\mathcal{H}$ . Restricted versions of the Counting CSP can be introduced in the same way as for the decision one. In the counting version of $\mathsf{CSP}(\mathcal{H})$ denoted $\mathsf{\#CSP}(\mathcal{H})$ the goal is to find $\mathsf{hom}(\mathcal{G},\mathcal{H})$ for a given structure $\mathcal{G}$ as an input.

The complexity class the Counting $\mathsf{CSP}$ belongs to is #P, the class of problems of counting accepting paths of polynomial time nondeterministic Turing machines. There are several ways to define reductions between counting problems, but the most widely used ones are parsimonious reductions and Turing reductions. A parsimonious reduction from a counting problem $\#A$ to a counting problem $\#B$ is an algorithm that, given an instance $I$ of $\#A$ produces (in polynomial time) an instance $I^{\prime}$ of $\#B$ such that the answers to $I$ and $I^{\prime}$ are equal. A Turing reduction is a polynomial time algorithm that solves $\#A$ using $\#B$ as an oracle. Completeness in #P is then defined in the standard way. This paper and all the papers we cite predominantly use Turing reductions.

A complexity classification of counting $\mathsf{CSP}$ s of the form $\mathsf{\#CSP}(\mathcal{H})$ was obtained by Bulatov [3] and was further improved and simplified by Dyer and Richerby [14]. Bulatov’s proof makes heavy use of techniques of universal algebra. Dyer and Richerby’s proof, on the other hand, uses combinatorial and structural properties of relational structures. The more general version of the counting CSP, the weighted CSP, has also been thoroughly studied. Cai and Chen [10] obtained a complexity classification for weighted CSP, where each homomorphism has a complex weight. One of the main features of counting with complex weights is the phenomenon of cancellation, when complex weights of homomorphisms cancel each other rather than add up. This, of course, never happens in exact unweighted counting problems, but is frequently encountered in modular counting.

Modular Counting.

Another natural variation of counting problems is counting modulo some integer. In this paper we consider the problem of computing the number of solutions of a $\mathsf{CSP}$ modulo a prime number $p$ . If a relational structure $\mathcal{H}$ is fixed, this problem is denoted $\#_{p}\mathsf{CSP}(\mathcal{H})$ . More precisely, in $\#_{p}\mathsf{CSP}(\mathcal{H})$ the objective is, given a relational structure $\mathcal{G}$ , to find the number of homomorphisms from $\mathcal{G}$ to $\mathcal{H}$ modulo $p$ .

There are several complexity classes related to modular counting. The more established type of classes is $\mathsf{Mod}_{k}$ P, the class of problems of deciding whether the number of accepting paths of a polynomial time nondeterministic Turing machine is not divisible by $k$ , [11, 25]. In particular, if $k=2$ then $\mathsf{Mod}_{k}$ P is the class $\oplus$ P. However, problems of counting accepting paths naturally belong to classes of the form $\#_{k}$ P, introduced by Faben in [15] that contain problems of counting accepting paths modulo $k$ . The standard notion of reduction is again Turing reduction. Faben in [15] studied the basic properties of such classes, in particular, he identified several $\#_{k}$ P-complete problems.

In the case of the $\mathsf{CSP}$ , the research has mostly been focused on graph homomorphisms. The only exceptions we are aware of are a result of Faben [15], who characterized the complexity of counting the solutions of a Generalized Satisfiability problem modulo an integer, and a generalization of [15] to problems with weights by Guo et al. [21]. The study of modular counting of graph homomorphisms has been much more vibrant.

Before discussing the existing results on modular counting and the results of this study, we need to mention some features of the automorphism group of a relational structure. The automorphisms of a relational structure $\mathcal{H}$ form a group with respect to composition denoted $\mathsf{Aut}(\mathcal{H})$ . The order of an automorphism $\pi\in\mathsf{Aut}(\mathcal{H})$ is the smallest number $k$ such that $\pi^{k}$ is the identity permutation. An element $a\in H$ is a fixed point of $\pi\in\mathsf{Aut}(\mathcal{H})$ if $\pi(a)=a$ . The set of all fixed points of $\pi$ is denoted by $\mathsf{Fix}(\pi)$ .

A systematic study of counting homomorphisms in graphs was initiated by Faben and Jerrum in [15]. They observed that the automorphism group $\mathsf{Aut}(\mathcal{H})$ , particularly the automorphisms of order $p$ , plays a crucial role in the complexity of the problem $\#_{p}\mathsf{Hom}(\mathcal{H})$ . This insight extends to relational structures, as discussed in [9]. Specifically, for a homomorphism $\varphi$ from a relational structure $\mathcal{G}$ to $\mathcal{H}$ , composing $\varphi$ with an automorphism from $\mathsf{Aut}(\mathcal{H})$ yields another homomorphism from $\mathcal{G}$ to $\mathcal{H}$ . Thus, any automorphism of $\mathcal{H}$ acts on the set $\mathsf{Hom}(\mathcal{G},\mathcal{H})$ of all homomorphisms from $\mathcal{G}$ to $\mathcal{H}$ . If $\mathsf{Aut}(\mathcal{H})$ contains an automorphism $\pi$ of order $p$ , the size of the orbit of $\varphi$ is divisible by $p$ unless $\pi\circ\varphi=\varphi$ , making this orbit contribute $0$ modulo $p$ to the total homomorphism count from $\mathcal{G}$ to $\mathcal{H}$ . If $\pi\circ\varphi=\varphi$ , the range of $\varphi$ lies within the set of fixed points $\mathsf{Fix}(\pi)$ of $\pi$ . This observation motivates the following construction: let $\mathcal{H}^{\pi}$ denote the substructure of $\mathcal{H}$ induced by $\mathsf{Fix}(\pi)$ . We write $\mathcal{H}\rightarrow_{p}\mathcal{H}^{\prime}$ there exists $\pi\in\mathsf{Aut}(\mathcal{H})$ such that $\mathcal{H}^{\prime}$ is isomorphic to $\mathcal{H}^{\pi}$ . Furthermore, we write $\mathcal{H}\rightarrow^{*}_{p}\mathcal{H}^{\prime}$ if there exist structures $\mathcal{H}_{1},\dots,\mathcal{H}_{k}$ such that $\mathcal{H}$ is isomorphic to $\mathcal{H}_{1}$ , $\mathcal{H}^{\prime}$ is isomorphic to $\mathcal{H}_{k}$ , and $\mathcal{H}_{1}\rightarrow_{p}\mathcal{H}_{2}\rightarrow_{p}\cdots\rightarrow_% {p}\mathcal{H}_{k}$ .

Relational structures without order $p$ automorphisms will be called $p$ -rigid.

Lemma 1 ([9, 16]).

Let $\mathcal{H}$ be a relational structure and $p$ a prime. Then

(a)

Up to an isomorphism there exists a unique $p$ -rigid structure $\mathcal{H}^{*p}$ such that $\mathcal{H}\rightarrow_{p}^{*}\mathcal{H}^{*p}$ .
(b)

For any relational structure $\mathcal{G}$ it holds that $\mathsf{hom}(\mathcal{G},\mathcal{H})\equiv\mathsf{hom}(\mathcal{G},\mathcal{H% }^{*p})\pmod{p}.$

By Lemma 1 it suffices to determine the complexity of $\#_{p}\mathsf{CSP}(\mathcal{H})$ for $p$ -rigid structures $\mathcal{H}$ .

The existing results on modular counting.

As we mentioned before, the research in modular counting $\mathsf{CSP}$ s has mostly been aimed at counting graph homomorphisms. The complexity of the problem $\#_{p}\mathsf{Hom}(H)$ of counting homomorphism to a fixed graph $H$ modulo a prime number $p$ has received significant attention in the last ten years. Faben and Jerrum in [16] posed a conjecture that up to order $p$ automorphism reduction $\rightarrow_{p}$ the complexity of this problem is the same as that for exact counting. More precisely, they conjectured that $\#_{p}\mathsf{Hom}(H)$ is solvable in polynomial time if and only if $\mathsf{Hom}(H^{*p})$ is. By the result of Dyer and Greenhill [13] $\#_{p}\mathsf{Hom}(H)$ is solvable in polynomial time if and only if every connected component of $H^{*p}$ is a complete graph with all loops present or a complete bipartite graph. Therefore, proving that if a $p$ -rigid $H$ does not satisfy these conditions then $\#_{p}\mathsf{Hom}(H)$ is $\#_{p}P$ -hard suffices to confirm the conjecture of Faben and Jerrum. Over several years the hardness of $\#_{p}\mathsf{Hom}(H)$ was established for various graph classes [16, 22, 19, 20, 28, 18, 31]. Finally, it was proved for arbitrary graphs in [9].

Theorem 2 ([9]).

For any prime $p$ and any graph $H$ the problem $\#_{p}\mathsf{Hom}(H)$ is solvable in polynomial time if and only if $\mathsf{Hom}(H^{*p})$ is solvable in polynomial time. Otherwise it is $\#_{p}$ P-complete.

Our Results.

In this paper we begin a systematic study of the problem $\#_{p}\mathsf{CSP}(\mathcal{H})$ for general relational structures $\mathcal{H}$ . Note that to the best of our knowledge, it is the first paper attempting at such a general modular counting problem. The ultimate goal is to obtain a complexity classification similar to Theorem 2 for arbitrary relational structures. The full version of the paper can be found in [29].

The contribution of the paper is twofold. First, we analyse the existing techniques such as those from [9], and the methods used in exact counting [3, 14, 10], and their applicability to the general case. We conclude that few of them work. More specifically, Theorem 2 asserts that the complexity of modular counting for $p$ -rigid graphs is the same as of exact counting. We, however, suggest a relational structure, a digraph $\mathcal{T}_{p}$ , that is $p$ -rigid, its exact counting problem is hard, but modular counting is easy, see Example 18. Another important ingredient of the proof of Theorem 2 is a structural theorem on automorphisms of products of graphs [24]. No such result exists for products of relational structures. Moreover, in Example 18 in Section 6 we suggest an example (again, a digraph) showing that nothing similar to such a structural result can be true. Some of the standard techniques in counting CSPs involve properties of relations and relational structures such as rectangularity, permutability, balancedness, the presence of a Mal’tsev polymorphism. In the case of exact counting these concepts are closely related to each other and make efficient algorithms possible. Unfortunately, these concepts are of little help for modular counting. We introduce their modular equivalents, but then a series of examples show that no tight connections are possible in this case. This makes algorithm design very difficult.

On the positive side, we obtain some results to somewhat remedy the situation. The first step is to convert the problem into a richer framework of multi-sorted relational structures and CSPs. The main idea is, given a CSP instance $\mathcal{G}$ , to try to identify the possible images of each vertex of $\mathcal{G}$ , and then treat vertices with different ranges as having different types and map them to different disjoint domains. In Section 4 we call this process refinement and propose two types of refinement, one is based on local propagation techniques, and the other on solving the decision version of the problem. The main benefit of using multi-sorted structures and CSPs is the richer structure of their automorphisms. This often allows stronger reductions than single-sorted structures do. In particular, if the digraph $\mathcal{T}_{p}$ mentioned above is subjected to this process, it results in a multi-sorted structure that is no longer $p$ -rigid, the corresponding reduced structure is very simple and can easily be solved. We are not aware of any examples of a structure whose multi-sorted refinement is $p$ -rigid, but that would give rise to an easy modular counting problem.

In the next line of research we follow the approach of [9] to expand the relational structure $\mathcal{H}$ by adding relations to $\mathcal{H}$ that are primitive positive (pp-)definable in $\mathcal{H}$ , that is, relations that can be derived from the relations of $\mathcal{H}$ using equality, conjunction and existential quantifiers. However, expanding the general relational structure by pp-definable relations does not work as well as for graphs. To overcome this obstacle, we introduce a new form of expansion which uses $p$ -modular quantifiers instead of regular existential quantifiers. The semantics of a $p$ -modular quantifier is “there are non-zero modulo $p$ values of a variable” rather than “there exists at least one value of a variable” as the regular existential quantifier asserts. Every relational structure is associated with a relational clone $\langle\mathcal{H}\rangle$ that consists of all relations pp-definable in $\mathcal{H}$ . The new concept gives rise to new definitions of pp-formulas and relational clones. If regular existential quantifiers in pp-formulas are replaced with $p$ -modular quantifiers, we obtain $p$ -modular primitive positive formulas ( $p$ -mpp-formulas, for short). Then, similar to pp-definitions, a relation $\mathcal{R}$ is said to be $p$ -mpp-definable in a structure $\mathcal{H}$ if there is a $p$ -mpp-formula in $\mathcal{H}$ expressing $\mathcal{R}$ . The $p$ -modular clone $\langle\mathcal{H}\rangle_{p}$ associated with $\mathcal{H}$ is the set of all relations $p$ -mpp-definable in $\mathcal{H}$ . We show in Theorem 10 (see also Theorem 7) that, similar to the result of Bulatov and Dalmau [6], expanding a structure by a $p$ -mpp-definable relation does not change the complexity of the problem $\#_{p}\mathsf{CSP}(\mathcal{H})$ .

Theorem 3.

Let $p$ be a prime number and $\mathcal{H}$ a $p$ -rigid relational structure. If $\mathcal{R}$ is $p$ -mpp-definable in $\mathcal{H}$ , then $\#_{p}\mathsf{CSP}(\mathcal{H}+\mathcal{R})$ is polynomial time reducible to $\#_{p}\mathsf{CSP}(\mathcal{H})$ .

In the remaining part of the paper we identify a number of conditions under which it is possible to design an algorithm or to prove the hardness of the problem. One such case is $\#_{2}\mathsf{CSP}(\mathcal{H})$ when $\mathcal{H}$ satisfies both 2-rectangularity and the usual strong rectangularity conditions (or, equivalently, has a Mal’tsev polymorphism). It starts with applying the known techniques [5, 14] to find a concise representation or a frame of the set of solutions of a given CSP. However, such a representation cannot be used directly to find the parity of the number of solutions. The algorithm performs multiple recomputations of the frame to exclude the parts that produce an even number of solutions. Unfortunately, this algorithm does not generalize to larger $p$ even under very strong assumptions, because the structure of finite fields start playing a role.

While studying the structure of automorphisms of products of relational structures such as $\mathsf{Aut}(\mathcal{H}^{n})$ may be a difficult problem, in Section 7 we make a step forward by reducing the class of structures $\mathcal{H}$ for which such structural results are required. More precisely, for any relational structure $\mathcal{H}=(H;\mathcal{R}_{1},\dots,\mathcal{R}_{k})$ we construct its binarization $b(\mathcal{H})$ whose relations are binary and rectangular. This makes such structures somewhat closer to graphs and the hope is that it will be easier to study the structure of $\mathsf{Aut}(b(\mathcal{H})^{n})$ than $\mathsf{Aut}(\mathcal{H}^{n})$ itself. We prove that $\mathcal{H}$ and $b(\mathcal{H})$ share many important properties.

Theorem 4.

Let $\mathcal{H}$ be a relational structure. Then $\mathcal{H}$ is strongly rectangular ( $p$ -strongly rectangular, $p$ -rigid, has a Mal’tsev polymorphism) if and only if $b(\mathcal{H})$ is strongly rectangular ( $p$ -strongly rectangular, $p$ -rigid, has a Mal’tsev polymorphism).

2 Preliminaries

Let $[n]$ denote the set $\{1,2,\ldots,n\}$ . Let $H^{n}$ be the Cartesian product of the set $H$ with itself $n$ times and $H_{1}\times\dots\times H_{n}$ the Cartesian product of sets $H_{1},\dots,H_{n}$ . We denote the members of $H^{n}$ and $H_{1}\times\dots\times H_{n}$ using bold font, $\mathbf{a}\in H^{n}$ , $\mathbf{a}\in H_{1}\times\dots\times H_{n}$ . The $i$ -th element of $\mathbf{a}$ is denoted by $\mathbf{a}[i]$ or $\mathbf{a}_{i}$ .

For $I=\{i_{1},\dots,i_{k}\}\subseteq[n]$ we use $\mathsf{pr}_{I}\mathbf{a}$ to denote $(\mathbf{a}_{i_{1}},\dots,\mathbf{a}_{i_{k}})$ ; and for $\mathcal{R}\subseteq H_{1}\times\dots\times H_{n}$ we use $\mathsf{pr}_{I}\mathcal{R}$ to denote $\{\mathsf{pr}_{I}\mathbf{a}\mid\mathbf{a}\in\mathcal{R}\}$ . For $\mathbf{a}\in H^{s}$ by $\mathsf{\#ext}_{\mathcal{R}}(\mathbf{a})$ we denote the number of assignments $\mathbf{b}\in H^{n-s}$ such that $(\mathbf{a},\mathbf{b})\in\mathcal{R}$ . (Note that the order of elements in $\mathbf{a}$ and $\mathbf{b}$ and $\mathcal{R}$ might differ, hence we slightly abuse the notation here.) We denote the number of assignments mod $p$ by $\mathsf{\#_{p}ext}_{\mathcal{R}}(\mathbf{a})$ . Moreover, $\mathsf{pr}^{p}_{I}\mathcal{R}$ denotes the set $\{\mathsf{pr}_{I}\mathbf{a}|\mathbf{a}\in\mathcal{R}\text{ and }\mathsf{\#_{p}% ext}_{\mathcal{R}}(\mathsf{pr}_{I}\mathbf{a})\neq 0\}$ . Often, we treat relations $\mathcal{R}\subseteq H_{1}\times\dots\times H_{n}$ as predicates $\mathcal{R}:H_{1}\times\dots\times H_{n}\to\{0,1\}$ .

2.1 Multi-Sorted Sets and Relational Structures

We begin with introducing multi-sorted or typed sets. Let $H=\{H_{i}\}_{{i\in[k]}}=\{H_{1},\dots,H_{k}\}$ be a collection of sets. We will assume that the sets $H_{1},\dots,H_{k}$ are disjoint.

The cardinality of a multi-sorted set $H$ equals $|H|=\sum_{i\in[k]}|H_{i}|$ . A mapping $\varphi$ between two multi-sorted sets $G=\{G_{i}\}_{{i\in[k]}}$ and $H=\{H_{i}\}_{{i\in[k]}}$ is defined as a collection of mappings $\varphi=\{\varphi_{i}\}_{{i\in[k]}}$ , where $\varphi_{i}:G_{i}\to H_{i}$ , that is, $\varphi_{i}$ maps elements of the sort $i$ in $G$ to elements of the sort $i$ in $H$ . A mapping $\varphi=\{\varphi_{i}\}_{{i\in[k]}}$ from $\{G_{i}\}_{{i\in[k]}}$ to $\{H_{i}\}_{{i\in[k]}}$ is injective (bijective), if for all $i\in[k]$ , $\varphi_{i}$ is injective (bijective).

A multi-sorted relational signature $\sigma$ over a set of types $\{1,\dots,k\}$ is a collection of relational symbols, a symbol $\mathcal{R}\in\sigma$ is assigned a positive integer $\ell_{\mathcal{R}}$ , the arity of the symbol, and a tuple $(i_{1},\dots,i_{\ell_{\mathcal{R}}})\subseteq[k]^{\ell_{\mathcal{R}}}$ , the type of the symbol. A multi-sorted relational structure $\mathcal{H}$ with signature $\sigma$ is a multi-sorted set $\{H_{i}\}_{i\in[k]}$ and an interpretation $\mathcal{R}^{\mathcal{H}}$ of each $\mathcal{R}\in\sigma$ , where $\mathcal{R}^{\mathcal{H}}$ is a relation or a predicate on $H_{i_{1}}\times...\times H_{i_{\ell_{\mathcal{R}}}}$ . The multi-sorted structure $\mathcal{H}$ is finite if $H$ and $\sigma$ are finite. All structures in this paper are finite. The set $H$ is said to be the base set or the universe of $\mathcal{H}$ . For the base set we will use the same letter as for the structure, only in the regular font. Multi-sorted structures with the same signature and type are called similar.

Let $\mathcal{G},\mathcal{H}$ be similar multi-sorted structures with signature $\sigma$ . A homomorphism $\varphi$ from $\mathcal{G}$ to $\mathcal{H}$ is a collection of mappings $\varphi_{i}:G_{i}\to H_{i}$ , $i\in[k]$ , from $G$ to $H$ such that for any $\mathcal{R}\in\sigma$ with type $(i_{1},\dots,i_{\ell_{\mathcal{R}}})$ , if $\mathcal{R}^{\mathcal{G}}(a_{1},\dots,a_{\ell_{\mathcal{R}}})$ is true for $(a_{1},\dots,a_{r})\in G_{i_{1}}\times...\times G_{i_{\ell_{\mathcal{R}}}}$ , then $\mathcal{R}^{\mathcal{H}}(\varphi_{i_{1}}(a_{1}),\dots,\varphi_{i_{\ell_{% \mathcal{R}}}}(a_{\ell_{\mathcal{R}}}))$ is true as well. The set of all homomorphisms from $\mathcal{G}$ to $\mathcal{H}$ is denoted $\mathsf{Hom}(\mathcal{G},\mathcal{H})$ . The cardinality of $\mathsf{Hom}(\mathcal{G},\mathcal{H})$ is denoted by $\mathsf{hom}(\mathcal{G},\mathcal{H})$ . For a multi-sorted structure $\mathcal{H}$ , the corresponding counting CSP, $\#_{p}\mathsf{CSP}(\mathcal{H})$ , is the problem of computing $\mathsf{hom}(\mathcal{G},\mathcal{H})$ modulo a prime number $p$ for a given structure $\mathcal{G}$ . A homomorphism $\varphi$ is an isomorphism if it is bijective and the inverse mapping $\varphi^{-1}$ is a homomorphism from $\mathcal{H}$ to $\mathcal{G}$ . If $\mathcal{H}$ and $\mathcal{G}$ are isomorphic, we write $\mathcal{H}\cong\mathcal{G}$ . A homomorphism of a structure to itself is called an endomorphism, and an isomorphism to itself is called an automorphism. As is easily seen, automorphisms of a structure $\mathcal{H}$ form a group denoted $\mathsf{Aut}(\mathcal{H})$ .

The direct product of multi-sorted $\sigma$ -structures $\mathcal{H},\mathcal{G}$ , denoted $\mathcal{H}\times\mathcal{G}$ is the multi-sorted $\sigma$ -structure with the base set $H\times G=\{H_{i}\times G_{i}\}_{{i\in[k]}}$ , the interpretation of $\mathcal{R}\in\sigma$ is given by $\mathcal{R}^{\mathcal{H}\times\mathcal{G}}((a_{1},b_{1}),\dots,(a_{k},b_{k}))=1$ if and only if $\mathcal{R}^{\mathcal{H}}(a_{1},\dots,a_{k})=1$ and $\mathcal{R}^{\mathcal{G}}(b_{1},\dots,b_{k})=1$ . By $\mathcal{H}^{\ell}$ we will denote the $\ell$ th power of $\mathcal{H}$ , that is, the direct product of $\ell$ copies of $\mathcal{H}$ .

For a prime number $p$ we say that $\pi$ has order $p$ if $\pi$ is not the identity in $\mathsf{Aut}(\mathcal{H})$ and has order $p$ in $\mathsf{Aut}(\mathcal{H})$ . In other words, each of the $\pi_{j}$ ’s is either the identity mapping or has order $p$ , and at least one of the $\pi_{j}$ ’s is not the identity mapping. Structure $\mathcal{H}$ is said to be $p$ -rigid if it has no automorphism of order $p$ . Similar to regular relational structures we can introduce reductions of multi-sorted structures by their automorphisms of order $p$ .

A substructure $\mathcal{H}^{\prime}$ of $\mathcal{H}$ induced by a collection of sets $\{H^{\prime}_{i}\}_{i\in[k]}$ , where $H^{\prime}_{i}\subseteq H_{i}$ is the relational structure given by $(\{H^{\prime}_{i}\}_{{i\in[k]}};\mathcal{R}^{\prime}_{1},\dots,\mathcal{R}^{% \prime}_{m})$ , where $\mathcal{R}^{\prime}_{j}=\mathcal{R}_{j}\cap(H^{\prime}_{i_{1}}\times\dots% \times H^{\prime}_{i_{\ell}})$ and $(i_{1},\dots,i_{\ell})$ is the type of $\mathcal{R}_{j}$ . By $\mathsf{Fix}(\pi)$ we denote the collection $\{\mathsf{Fix}(\pi_{i})\}_{j\in[k]}$ of sets of fixed points of the $\pi_{i}$ ’s. Let $\mathcal{H}^{\pi}$ denote the substructure of $\mathcal{H}$ induced by $\mathsf{Fix}(\pi)$ . We write $\mathcal{H}\rightarrow_{p}\mathcal{H}^{\prime}$ if there is $\pi\in\mathsf{Aut}(\mathcal{H})$ of order $p$ such that $\mathcal{H}^{\prime}$ is isomorphic to $\mathcal{H}^{\pi}$ . We also write $\mathcal{H}\rightarrow^{*}_{p}\mathcal{H}^{\prime}$ if there are structures $\mathcal{H}_{1},\dots,\mathcal{H}_{t}$ such that $\mathcal{H}$ is isomorphic to $\mathcal{H}_{1}$ , $\mathcal{H}^{\prime}$ is isomorphic to $\mathcal{H}_{t}$ , and $\mathcal{H}_{1}\rightarrow_{p}\mathcal{H}_{2}\rightarrow_{p}\dots\rightarrow_{% p}\mathcal{H}_{t}$ . Let also $\mathcal{H}^{*p}$ be a $p$ -rigid structure such that $\mathcal{H}\rightarrow^{*}_{p}\mathcal{H}^{*p}$ .

Proposition 5.

Let $\mathcal{H}$ be a multi-sorted structure and $p$ a prime. Then up to an isomorphism there exists a unique $p$ -rigid multi-sorted structure $\mathcal{H}^{*p}$ such that $\mathcal{H}\rightarrow_{p}^{*}\mathcal{H}^{*p}$ . Moreover, for any relational structure $\mathcal{G}$ it holds $\mathsf{hom}(\mathcal{G},\mathcal{H})\equiv\mathsf{hom}(\mathcal{G},\mathcal{H% }^{*p})\pmod{p}$ .

The proof of Proposition 5 follows the same lines as the analogous statement in the single-sorted case.

We complete this section with a definition of polymorphisms. Let $\mathcal{R}\subseteq H^{n}$ be a relation over a set $H$ . A $k$ -ary polymorphism of $\mathcal{R}$ is a mapping $f:H^{k}\to H$ such that for any choice of $\mathbf{a}_{1},\dots,\mathbf{a}_{k}\in\mathcal{R}$ , it holds that $f(\mathbf{a}_{1},\dots,\mathbf{a}_{k})\in\mathcal{R}$ (computed component-wise). The mapping $f$ is a polymorphism of a (single-sorted) relational structure $\mathcal{H}=(H,\mathcal{R}_{1},\dots,\mathcal{R}_{m})$ if it is a polymorphism of each relation $\mathcal{R}_{1},\dots,\mathcal{R}_{m}$ . In the multi-sorted case the definitions are a bit more complicated. Let $\mathcal{R}\subseteq H_{1}\times\dots\times H_{n}$ be a multi-sorted relation. Instead of a single mapping we consider a family of mappings $f=\{f_{i}\}_{i\in[n]}$ , $f_{i}:H^{k}_{i}\to H_{i}$ . The family $f$ is said to be a polymorphism of $\mathcal{R}$ if it satisfies the same condition: for any choice of $\mathbf{a}_{1},\dots,\mathbf{a}_{k}\in\mathcal{R}$ , it holds that $f(\mathbf{a}_{1},\dots,\mathbf{a}_{k})\in\mathcal{R}$ , only in this case the mapping $f_{i}$ is applied in the $i$ th coordinate position, $i\in[n]$ . A polymorphism of a multi-sorted structure $\mathcal{H}=(\{H_{i}\}_{i\in[q]};\mathcal{R}_{1},\dots,\mathcal{R}_{m})$ is again a family $f=\{f_{i}\}_{i\in q}:H^{k}_{i}\to H_{i}$ such that for each $j\in[m]$ , $f$ (or rather its appropriate subfamily) is a polymorphism of $\mathcal{R}_{j}$ . For a complete introduction into polymorphisms the reader is referred to [1].

The following special type of polymorphisms often occurs in the study of counting CSPs. For a set $H$ a mapping $\varphi:H^{3}\rightarrow H$ is said to be a Mal’tsev operation if for any $a,b\in H$ it satisfies the conditions $f(a,a,b)=f(b,a,a)=b$ . In the multi-sorted case a family $f=\{f_{i}\}_{i\in[n]}$ is Mal’tsev, if every $f_{i}$ is Mal’tsev. A Mal’tsev operation (or a family of operations) that is a polymorphism of a relation $\mathcal{R}$ or a relational structure $\mathcal{H}$ is said to be a Mal’tsev polymorphism of $\mathcal{R}$ or $\mathcal{H}$ .

2.2 Expansion of relational structures

One of the standard techniques when studying constraint problems is to identify ways to expand the target relational structure or constraint language with additional relations without changing the complexity of the problem.

Let $\mathcal{H}$ be a relational structure with signature $\sigma$ and $\mathcal{H}^{=}$ its expansion by adding a binary relational symbol $=$ interpreted as $=_{H}$ , the equality relation on $H$ . The following reduction is straightforward.

Lemma 6 ([9]).

For any relational structure $\mathcal{H}$ and any prime $p$ , $\#_{p}\mathsf{CSP}(\mathcal{H}^{=})\leq_{T}\#_{p}\mathsf{CSP}(\mathcal{H})$ .

A constant relation over a set $H$ is a unary relation $C_{a}=\{a\}$ , $a\in H$ . For a relational structure $\mathcal{H}$ by $\mathcal{H}^{\mathsf{c}}$ we denote the expansion of $\mathcal{H}$ by all the constant relations $C_{a}$ , $a\in H$ . Theorem 7 was proved for exact counting in [6], for modular counting of graph homomorphisms in [16, 19, 20], and for general modular counting CSP in [9].

Theorem 7 ([9]).

Let $\mathcal{H}$ be a $p$ -rigid $\sigma$ -structure. Then $\#_{p}\mathsf{CSP}(\mathcal{H}^{\mathsf{c}})$ is polynomial time reducible to $\#_{p}\mathsf{CSP}(\mathcal{H})$ .

Lemma 6 and Theorem 7 can be generalized to the multi-sorted case. Let $\mathcal{H}=\{\mathcal{H}_{i}\}_{i\in[k]}$ be a multi-sorted structure with signature $\sigma$ and $\mathcal{H}^{=}$ its expansion by adding a family of binary relational symbols $=_{H_{i}}$ (one for each type) interpreted as the equality relation on $H_{i}$ , $i\in[k]$ .

A constant relation over a set $\{H_{i}\}_{i\in[k]}$ is a unary relation $C_{a}=\{a\}$ , $a\in H_{i},i\in[k]$ (such a predicate can only be applied to variables of type $i$ ). For a structure $\mathcal{H}$ by $\mathcal{H}^{\mathsf{c}}$ we denote the expansion of $\mathcal{H}$ by all the constant relations $C_{a}$ , $a\in H_{i},i\in[k]$ .

Theorem 8.

Let $\mathcal{H}$ be a multi-sorted relational structure and $p$ prime.

(1)

$\#_{p}\mathsf{CSP}(\mathcal{H}^{=})$ is Turing reducible to $\#_{p}\mathsf{CSP}(\mathcal{H})$ ;
(2)

Let $\mathcal{H}$ be $p$ -rigid. Then $\#_{p}\mathsf{CSP}(\mathcal{H}^{\mathsf{c}})$ is Turing reducible to $\#_{p}\mathsf{CSP}(\mathcal{H})$ .

Yet another way to expand a relational structure is by primitive positive definable (pp-definable for short) relations. Primitive-positive definitions have played a major role in the study of the CSP. It has been proved in multiple circumstances that expanding a structure with pp-definable relations does not change the complexity of the corresponding CSP. This has been proved for the decision CSP in [26, 8] and the exact Counting CSP [6]. The reader is referred to [1] for details about pp-definitions and their use in the study of the CSP.

Conjunctive definitions are a special case of pp-definitions that do not use quantifiers. Let $\mathcal{H}$ be a structure with signature $\sigma$ . A conjunctive formula $\Phi$ over variables $\{x_{1},\dots,x_{k}\}$ is a conjunction of atomic formulas of the form $\mathcal{R}(y_{1},\dots,y_{\ell})$ , where $\mathcal{R}\in\sigma$ is an ( $\ell$ -ary) symbol and $y_{1},\dots,y_{\ell}\in\{x_{1},\dots,x_{k}\}$ . A $k$ -ary predicate $\mathcal{Q}$ is conjunctive definable by $\Phi$ if $(a_{1},\dots,a_{k})\in\mathcal{Q}$ if and only if $\Phi(a_{1},\dots,a_{k})$ is true.

Lemma 9 ([9]).

Let $\mathcal{H}$ be a relational structure with signature $\sigma$ , $\mathcal{R}$ be conjunctive definable in $\mathcal{H}$ , and $\mathcal{H}+\mathcal{R}$ denote the expansion of $\mathcal{H}$ by a predicate symbol $\mathcal{R}$ that is interpreted as the relation $\mathcal{R}$ in $\mathcal{H}$ . Then $\#_{p}\mathsf{CSP}(\mathcal{H}+\mathcal{R})\leq_{T}\#_{p}\mathsf{CSP}(\mathcal% {H})$ .

We now extend the concept of primitive-positive definability to the multi-sorted case. Let $\mathcal{H}$ be a multi-sorted relational structure with the base set $H$ . As before primitive positive (pp-) formula in $\mathcal{H}$ is a first-order formula $\exists y_{1},\dots,y_{s}\Phi(x_{1},\dots,x_{k},y_{1},\dots,y_{s}),$ where $\Phi$ is a conjunction of atomic formulas of the form $z_{1}=_{H}z_{2}$ or $\mathcal{R}(z_{1},\dots,z_{\ell})$ , $z_{1},\dots,z_{\ell}\in\{x_{1},\dots,x_{k},y_{1},\dots,y_{s}\}$ , and $\mathcal{R}$ is a predicate of $\mathcal{H}$ . However, every variable in $\Phi$ is now assigned a type $\tau(x_{i}),\tau(y_{j})$ in such a way that for every atomic formula $z_{1}=_{H}z_{2}$ it holds that $\tau(z_{1})=\tau(z_{2})$ , and for any atomic formula $\mathcal{R}(z_{1},\dots,z_{\ell})$ the sequence $(\tau(z_{1}),\dots,\tau(z_{\ell}))$ matches the type of $\mathcal{R}$ . We say that $\mathcal{H}$ pp-defines a predicate $\mathcal{Q}$ if there exists a pp-formula such that

\mathcal{Q}(x_{1},\dots,x_{k})=\exists y_{1},\dots,y_{s}\Phi(x_{1},\dots,x_{k}% ,y_{1},\dots,y_{s}).

For $\mathbf{a}\in\mathcal{R}$ by $\mathsf{\#ext}_{\Phi}(\mathbf{a})$ we denote the number of assignments $\mathbf{b}\in H_{\tau(y_{1})}\times\dots\times H_{\tau(y_{s})}$ to $y_{1},\dots,y_{s}$ such that $\Phi(\mathbf{a},\mathbf{b})$ is true. We denote the number of such assignments mod $p$ by $\mathsf{\#_{p}ext}_{\Phi}(\mathbf{a})$ .

While when $\mathcal{H}$ is a graph it is possible to prove a statement similar to Lemma 9 for pp-definable relations [9], we will later see that it is unlikely to be true for general relational structures.

Finally, for a relational structure $\mathcal{H}$ (single- or multi-sorted) $\langle\mathcal{H}\rangle$ denotes the relational clone of $\mathcal{H}$ , that is, the set of all relations pp-definable in $\mathcal{H}$

2.3 Modular Expansion of Relational Structures

We follow the approach of [9] by expanding the relational structure $\mathcal{H}$ by adding pp-definable relations, but doing in a manner friendly to modular counting.

We introduce a new form of expansion which is using $p$ -modular quantifiers instead of regular existential quantifiers. The semantics of a $p$ -modular quantifier is “there are non-zero modulo $p$ values of a variable” rather than “there exists at least one value of a variable” as the regular existential quantifier asserts. The new concept gives rise to new definitions of pp-formulas. If regular existential quantifiers in pp-formulas are replaced with $p$ -modular quantifiers, we obtain $p$ -modular primitive positive formulas ( $p$ -mpp-formulas, for short). The $p$ -modular quantifier is denoted $\exists^{\equiv p}$ , and so $p$ -mpp-formulas have the form

\exists^{\equiv p}y_{1},\dots,y_{\ell_{1}}\dots\exists^{\equiv p}y_{\ell_{1}+% \dots+\ell_{s-1}+1},\dots,y_{k}\Phi(z_{1},\dots,z_{m}).

Note the more complicated form of the quantifier prefix: modular quantification is not as robust as the regular one and quantifying variables away in groups or one-by-one may change the result. For example, let $\mathcal{R}=\{(1,0,0),(1,1,0),(1,1,1),(2,2,2)\}$ be a relation on $\{0,1,2\}$ . Then formulas $\exists^{\equiv 3}y\exists^{\equiv 3}z\ \ \mathcal{R}(x,y,z)$ and $\exists^{\equiv 3}y,z\ \ \mathcal{R}(x,y,z)$ define sets $\{1,2\}$ and $\{2\}$ , respectively.

Every relational structure is associated with a relational clone $\langle\mathcal{H}\rangle$ that consists of all relations pp-definable in $\mathcal{H}$ . Then, similar to pp-definitions, a relation $\mathcal{R}$ is said to be $p$ -mpp-definable in a structure $\mathcal{H}$ if there is a $p$ -mpp-formula in $\mathcal{H}$ expressing $\mathcal{R}$ . The $p$ -modular clone $\langle\mathcal{H}\rangle_{p}$ associated with $\mathcal{H}$ is the set of all relations $p$ -mpp-definable in $\mathcal{H}$ . Similar to the result of Bulatov and Dalmau [6], expanding a structure by a $p$ -mpp-definable relation does not change the complexity of the problem $\#_{p}\mathsf{CSP}(\mathcal{H})$ .

Theorem 10.

Let $\mathcal{H}$ be a be a $\sigma$ -structure, and $p$ a prime. Let $\mathcal{R}$ be a relation that is defined by $R(x_{1},\dots,x_{k})=\exists^{\equiv p}y_{1},\dots,y_{\ell}\Phi(x_{1},\dots,x_% {k},y)$ , then $\#_{p}\mathsf{CSP}(\mathcal{H}+\mathcal{R})$ is polynomial time reducible to $\#_{p}\mathsf{CSP}(\mathcal{H})$ .

3 Structural Properties for Counting

3.1 Rectangularity, Permutability, and Friends

The key properties of relational structures heavily exploited in [3, 14, 10] to obtain characterizations of the complexity of exact counting are rectangularity, balancedness, congruence permutability, and the presence of a Mal’tsev polymorphism. Indeed, according to [14] $\#\mathsf{CSP}(\mathcal{H})$ is polynomial time solvable if and only if $\mathcal{H}$ is strongly balanced. However, in order for the solution algorithm to work, it requires a Mal’tsev polymorphism to be applied over and over again to construct a frame, that is, a compact representation of the set of solutions, [3, 14].

Using modular pp-definitions, we can modify these properties’ definitions accordingly to obtain the properties of strong $p$ -rectangularity, $p$ -balancedness, and $p$ -permutability. Modular-pp-definitions preserve the complexity of modular problems, however, they destroy the connections between the concepts above.

$𝒑$ -Rectangularity.

Recall that a binary relation $\mathcal{R}\subseteq H_{1}\times H_{2}$ is said to be rectangular if $(a,c),(a,d),(b,c)\in\mathcal{R}$ implies $(b,d)\in\mathcal{R}$ for any $a,b\in H_{1},c,d\in H_{2}$ . A relation $\mathcal{R}\subseteq H_{1}\times\dots\times H_{n}$ for $n\geq 2$ is rectangular if for every $I\subsetneq[n]$ , the relation $R$ is rectangular when viewed as a binary relation, a subset of $\mathsf{pr}_{I}\mathcal{R}\times\mathsf{pr}_{[n]-I}\mathcal{R}$ . A relational structure $\mathcal{H}$ is strongly rectangular if every relation $\mathcal{R}\in\langle\mathcal{H}\rangle$ of arity at least 2 is rectangular. Finally, a relational structure $\mathcal{H}$ is said to be strongly $p$ -rectangular, if every $\mathcal{R}\in\langle\mathcal{H}\rangle_{p}$ is rectangular.

$𝒑$ -Balancedness.

An $n$ -by- $m$ matrix $M$ is said to be a rank-1 block matrix if by permuting rows and columns it can be transformed to a block-diagonal matrix (not necessarily square), where every nonzero diagonal block has rank at most 1. Note that the rank can also be computed in $\mathbb{Z}_{p}$ , in which case we use the term rank-1 block matrix modulo $p$ .

Let $\mathcal{R}(x,y,z)$ be a ternary relation, a subset of $H_{1}\times H_{2}\times H_{3}$ . We call $\mathcal{R}$ balanced if the matrix $\mathsf{M}_{\mathcal{R}}\in\mathbb{Z}^{|H_{1}|\times|H_{2}|}$ , where $\mathsf{M}_{\mathcal{R}}[x,y]=|\{z\in H_{3}:(x,y,z)\in\mathcal{R}\}|$ such that $x\in H_{1}$ and $y\in H_{2}$ is a rank-1 block matrix. It is $p$ -balanced if $\mathsf{M}_{\mathcal{R}}$ is a rank-1 block matrix modulo $p$ . A relation $\mathcal{R}$ of arity $n>3$ is balanced if every representation of $\mathcal{R}$ as a ternary relation, a subset of $H^{k}\times H^{\ell}\times H^{n-k-\ell}$ , is balanced. Similarly, A relation $\mathcal{R}$ on $H$ of arity $n>3$ is $p$ -balanced if every representation of $\mathcal{R}$ as a ternary relation, a subset of $H^{k}\times H^{\ell}\times H^{n-k-\ell}$ , is $p$ -balanced.

A relational structure $\mathcal{H}$ is called strongly balanced if every relation $\mathcal{R}\in\langle\mathcal{H}\rangle$ is balanced. Similarly, a relational structure $\mathcal{H}$ is called strongly $p$ -balanced if every relation $\mathcal{R}\in\langle\mathcal{H}\rangle_{p}$ is $p$ -balanced.

$𝒑$ -Permutability.

A congruence of a relational structure $\mathcal{H}$ is an equivalence relation $\theta$ on $H$ that is pp-definable in $\mathcal{H}$ . More generally, let $\mathcal{R}\in\langle\mathcal{H}\rangle$ be a $k$ -ary relation. A congruence of $\mathcal{R}$ is a $2k$ -ary relation pp-definable in $\mathcal{H}$ that is an equivalence relation on $\mathcal{R}$ . We denote the set of all congruences of $\mathcal{H}$ (of $\mathcal{R}$ ) by $\mathsf{Con}(\mathcal{H})$ (respectively, by $\mathsf{Con}(\mathcal{R})$ ). By $\circ$ we denote the product of binary relations: $(a,b)\in\mathcal{R}\circ\mathcal{Q}$ if and only if there is $c$ such that $(a,c)\in\mathcal{R}$ and $(c,b)\in\mathcal{Q}$ . We say $\mathcal{H}$ is congruence permutable if for all $\alpha,\beta\in\mathsf{Con}(\mathcal{R})$ , where $\mathcal{R}\in\langle\mathcal{H}\rangle$ , it holds that $\alpha\circ\beta=\beta\circ\alpha$ .

Congruence $p$ -permutability is defined as follows: A $p$ -congruence of $\mathcal{H}$ or of $\mathcal{R}\in\langle\mathcal{H}\rangle_{p}$ is an equivalence relation on $H$ or $\mathcal{R}$ , respectively, that is $p$ -mpp-definable in $\mathcal{H}$ . We denote the set of all $p$ -congruences of $\mathcal{H}$ ( $\mathcal{R}$ ) by $\mathsf{Con}_{p}(\mathcal{H})$ ( $\mathsf{Con}_{p}(\mathcal{R})$ ). By $\bigcirc$ $\scriptscriptstyle p$ we denote the product of binary relations: $(a,b)\in\mathcal{R}\leavevmode\hbox{\set@color\hskip 3.25pt\hskip-3.25pt% \leavevmode\hbox{\set@color$\leavevmode\hbox{\set@color$\scalebox{0.65}{$% \bigcirc$}$}$}\hskip-3.25pt\hskip-1.25781pt\raisebox{1.03471pt}{\leavevmode% \hbox{\set@color$\rule{0.0pt}{0.0pt}\rule{0.0pt}{0.0pt}\leavevmode\hbox{% \set@color$\scriptscriptstyle p$}$}}\hskip-1.25781pt\hskip 3.25pt}\mathcal{Q}$ if and only if the number of elements $c$ such that $(a,c)\in\mathcal{R}$ and $(c,b)\in\mathcal{Q}$ is not a multiple of $p$ . We say that $\mathcal{H}$ is congruence $p$ -permutable if for all $\alpha,\beta\in\mathsf{Con}_{p}(\mathcal{R})$ , where $\mathcal{R}\in\langle\mathcal{H}\rangle_{p}$ , we have $\alpha\leavevmode\hbox{\set@color\hskip 3.25pt\hskip-3.25pt\leavevmode\hbox{% \set@color$\leavevmode\hbox{\set@color$\scalebox{0.65}{$\bigcirc$}$}$}\hskip-3% .25pt\hskip-1.25781pt\raisebox{1.03471pt}{\leavevmode\hbox{\set@color$\rule{0.% 0pt}{0.0pt}\rule{0.0pt}{0.0pt}\leavevmode\hbox{\set@color$\scriptscriptstyle p% $}$}}\hskip-1.25781pt\hskip 3.25pt}\beta=\beta\leavevmode\hbox{\set@color% \hskip 3.25pt\hskip-3.25pt\leavevmode\hbox{\set@color$\leavevmode\hbox{% \set@color$\scalebox{0.65}{$\bigcirc$}$}$}\hskip-3.25pt\hskip-1.25781pt% \raisebox{1.03471pt}{\leavevmode\hbox{\set@color$\rule{0.0pt}{0.0pt}\rule{0.0% pt}{0.0pt}\leavevmode\hbox{\set@color$\scriptscriptstyle p$}$}}\hskip-1.25781% pt\hskip 3.25pt}\alpha$ . Figure 1 demonstrates the connection between congruence permutabililty, strong rectangularity, the existence of a Mal’tsev polymorphism, strong balancedness and their modular counterparts. A collection of statements and examples proving these connections or lack thereof will be given in the full version of the paper. Below we give one such example showing that the existence of a Mal’tsev polymorphism does not guarantee 2-rectangularity.

(a) Congruence Permutability, Strong Rectangularity, and Mal’tsev polymorphism are equavalent (See [23, 14, 3]). Also, Strong Balancedness implies Strong Rectangularity(See [14]).

(b) The only connection that is preserved for the modular case is Congruence

p

-Permutability implies Strong

p

-rectangularity. Also, Strong 2-rectangularity is equivalence to Strong 2-Balancedness.

Figure 1: The connection between 4 properties is shown above. Figure (1(a)) shows the connection for the exact counting. Figure (1(b)) shows the the connection for the modular counterparts.

Example 11.

Let $H=\{0,1,2\}$ , $p=2$ , and $\mathcal{H}=(H;\mathcal{R})$ , where $\mathcal{R}$ is the following ternary relation, (triples are written vertically), $\mathcal{R}=\{(0,0,0),(0,1,1),(1,0,1),(1,0,2),(1,1,0)\}$ . As is easily see, $\exists^{\equiv 2}z\mathcal{R}(x,y,z)$ is the relation $\{(0,0),(0,1),(1,1)\}$ , which is not rectangular, and so, $\mathcal{H}$ is not strongly 2-rectangular. We now show that $\mathcal{H}$ is strongly rectangular by presenting a Mal’tsev polymorphism of $\mathcal{H}$ . Let $f(x,y,z)=x+y+z$ , where addition is modulo 2, is an operation on $\{0,1\}$ . For $\mathbf{a}=(a_{1},a_{2},a_{3})\in H^{3}$ , let also $\mathbf{a}^{\prime}\in\{0,1\}^{3}$ denote the triple obtained by replacing 2’s with 1’s. Then let $g(x,y,z)$ be given by

g(\mathbf{a})=\left\{\begin{array}[]{ll}2,&\text{if }\mathbf{a}\in\{(2,a,a),(a% ,a,2)\mid a\in H\},\\ f(\mathbf{a}^{\prime})&\text{otherwise}.\end{array}\right.

It is straightforward that $g$ is a Mal’tsev operation and is a polymorphism of $\mathcal{H}$ .

4 Rigitity and Multi-sorted Structures

We start with applying a well-known framework of multi-sorted relational structures to modular counting. While multi-sorted structures is a standard tool in the study of decision CSPs, it usually only used to simplify arguments and streamline algorithms. Here we use this framework in a more fundamental way, to strengthen the main (hypothetical) tractability condition.

The classification result in Theorem 2 asserts that $\#_{p}\mathsf{Hom}(H)$ for a $p$ -rigid graph $H$ is hard whenever the exact counting problem is hard. In the following example, we briefly show that this is no longer the case for general relational structures.

Example 12.

Let $p$ be a prime number and $T_{p}=\{0,\dots,p-1,p,p+1\}$ . A relational structure $\mathcal{T}_{p}$ has the base set $T_{p}$ and predicates $\mathcal{R},C_{0},\dots,C_{p+1}$ , where $C_{a}$ is the constant relation $\{(a)\}$ and $\mathcal{R}=T^{2}_{p}-\{(0,p),\dots,(p-1,p)\}$ . The structure $\mathcal{T}_{p}$ is $p$ -rigid as it contains all the constant relations and every automorphism must preserve them, implying that every element of $T_{p}$ is a fixed point. By [4, 35] the decision $\mathsf{CSP}(\mathcal{T}_{p})$ is solvable in polynomial time, while the exact counting problem $\#\mathsf{CSP}(\mathcal{T}_{p})$ is $\#$ P-complete by [6], as it does not have a Mal’tsev polymorphism and $\mathcal{R}$ is not rectangular (see below). However, if $\mathcal{G}$ is a structure similar to $\mathcal{T}_{p}$ and there is a homomorphism $\varphi:\mathcal{G}\to\mathcal{T}_{p}$ such that some vertex $v$ of $\mathcal{G}$ is mapped to $a\in\{0,\dots,p-1\}$ then, unless $v$ is bound by $C_{a}$ , the mapping that differs from $\varphi$ only at $v$ by sending it to any $b\in\{0,\dots,p-1\}$ is also a homomorphism. Since $|\{0,\dots,p-1\}|=p$ , this means that the elements $0,\dots,p-1$ can be effectively eliminated from $\mathcal{T}_{p}$ , and the resulting structure is somewhat trivial. Therefore $\#_{p}\mathsf{CSP}(\mathcal{T}_{p})$ can be solved in polynomial time.

We introduce a different concept of rigidity that is stronger than the one used before. In particular, it will explain the tractability of the problem from Example 12.

While Proposition 5 allows one to reduce CSPs over non- $p$ -rigid structures, it is sometimes possible to go further and reduce a CSP to one with a richer structure, and a richer set of automorphisms. Let $\mathcal{H}=(\{H_{i}\}_{{i\in[k]}};\mathcal{R}_{1},\dots,\mathcal{R}_{m})$ be a multi-sorted relational structure. We say that a structure $\mathcal{G}$ is a refinement of $\mathcal{H}$ if it satisfies the following conditions:

(a)

$\mathcal{G}=(\{G_{i}\}_{{i\in[q]}};\mathcal{Q}_{1},\dots,\mathcal{Q}_{t})$ , where the $G_{i}$ ’ are pairwise disjoint,
(b)

for every $i\in[q]$ , there is an injective mapping $\xi_{i}:G_{i}\to H_{i^{\prime}}$ for some $i^{\prime}\in[k]$ ,
(c)

for every $j\in[t]$ there is $j^{\prime}\in[m]$ with $\mathcal{R}_{j^{\prime}}\subseteq H_{i_{1}}\times\dots\times H_{i_{\ell}}$ and $\mathcal{Q}_{j}=\{(a_{1},\dots,a_{\ell})\in G_{i^{\prime}_{1}}\times\dots% \times G_{i^{\prime}_{\ell}}\mid(\xi_{i^{\prime}_{1}}(a_{1}),\dots,\xi_{i^{% \prime}_{\ell}}(a_{\ell}))\in\mathcal{R}_{j^{\prime}}\}$ , where $G_{i^{\prime}_{r}}$ is such that $\xi_{i^{\prime}_{r}}(G_{i^{\prime}_{r}})\subseteq H_{i_{r}}\cap\mathsf{pr}_{r}% \mathcal{R}_{j^{\prime}}$ .

Condition (a) is required because the domains of a multi-sorted structure have to be disjoint. Condition (b) basically says that $G_{i}$ consists of copies of some elements of $H_{i^{\prime}}$ . Condition (c) amounts to saying that $\mathcal{Q}_{j}\subseteq\mathcal{R}_{j^{\prime}}$ , except it uses copies of the elements of $\mathcal{H}$ . In the notation of item (c) we use $\xi(a_{1},\dots,a_{\ell})$ to denote $(\xi_{i^{\prime}_{1}}(a_{1}),\dots,\xi_{i^{\prime}_{\ell}}(a_{\ell}))$ , we use $\xi(\mathcal{Q}_{j})$ to denote $\{\xi(a_{1},\dots,a_{\ell})\mid(a_{1},\dots,a_{\ell})\in\mathcal{Q}_{j}\}$ , and $\xi^{-1}(\mathcal{R}_{j^{\prime}})$ for $\{(a_{1},\dots,a_{\ell})\in G_{i^{\prime}_{1}}\times\dots\times G_{i^{\prime}_% {\ell}}\mid\xi(a_{1},\dots,a_{\ell})\in\mathcal{R}_{j^{\prime}}\}$ .

It is possible that while $\mathcal{H}$ is $p$ -rigid, its refinement is not and Proposition 5.

In order to relate refinement structures with reductions between counting problems we introduce two special types of refinement. First of all, we will need an alternative approach to pp-definitions based on homomorphisms, see [17, 30].

Lemma 13 ([17, 30]).

A predicate $\mathcal{R}(x_{1},\dots,x_{k})$ is pp-definable in a multi-sorted structure $\mathcal{H}$ containing the equality predicate if and only if there exists a similar structure $\mathcal{G}_{\mathcal{R}}$ containing vertices $x_{1},\dots,x_{k}$ such that for any $(a_{1},\dots,a_{k})\in\mathcal{R}$ it holds that $(a_{1},\dots,a_{k})\in\mathcal{R}$ if and only if there is a homomorphism from $\mathcal{G}_{\mathcal{R}}$ to $\mathcal{H}$ that maps $x_{i}$ to $a_{i}$ , $i\in[k]$ . We will say that $\mathcal{G}_{\mathcal{R}}$ defines $R$ in $\mathcal{H}$ .

Let $\mathcal{H}=(\{H_{i}\}_{{i\in[k]}};\mathcal{R}_{1},\dots,\mathcal{R}_{m})$ be a multi-sorted relational structure. The Gaifman graph of $\mathcal{H}$ is the graph $G(\mathcal{H})=(V,E)$ , where $V=\bigcup_{i\in[k]}H_{i}$ and $(a,b)\in E$ if and only if there is $j\in[m]$ and $\mathbf{a}\in\mathcal{R}_{j}$ such that $\mathbf{a}[s]=a,\mathbf{a}[t]=b$ for some coordinate positions $s, t$ of $\mathcal{R}_{j}$ . The structure $\mathcal{H}$ has treewidth $d$ if $G(\mathcal{H})$ has treewidth $d$ .

We say that a refinement $\mathcal{G}=(\{G_{i}\}_{{i\in[q]}};\mathcal{Q}_{1},\dots,\mathcal{Q}_{t})$ of $\mathcal{H}$ is width $d$ definable if for every $i\in[q]$ there is a structure $\mathcal{G}_{i}$ of treewidth at most $d$ that defines $\xi_{i}(G_{i})$ in $\mathcal{H}$ . In a similar way, we say that $\mathcal{G}$ is a definable refinement if for every $i\in[q]$ the set $\xi_{i}(G_{i})$ is pp-definable in $\mathcal{H}$ . Finally, we say that $\mathcal{G}$ is the full width $d$ definable refinement (respectively, full definable refinement) if it satisfies the following conditions.

(1)

It is a width $d$ definable refinement (respectively, a definable refinement).
(2)

For every unary relation $U$ definable in $\mathcal{H}$ by a structure of treewidth at most $d$ (respectively, pp-definable unary relation) there is $i\in[q]$ such that $\xi_{i}(G_{i})=U$ .
(3)

For every relation $S$ obtained from some relation $\mathcal{R}_{j}$ by restricting it to domains definable by structures of width $d$ (respectively by pp-definable domains), there is $\mathcal{Q}_{j^{\prime}}$ such that $\xi(\mathcal{Q}_{j^{\prime}})=S$ .

Since the original domains $H_{i}$ , $i\in[k]$ , have trivial pp-definitions, they (or rather their copies) are always among the $G_{j}$ ’s, and copies of the original relations are also among the $\mathcal{Q}_{j}$ ’s, although they may be over different, smaller domains than the $\mathcal{R}_{i}$ ’s.

Next, we extend refinements to CSP instances. Let $\mathcal{G}=(\{G_{i}\}_{{i\in[q]}};\mathcal{Q}_{1},\dots,\mathcal{Q}_{t})$ be a refinement of $\mathcal{H}$ and $\mathcal{P}=(V,\mathcal{C})$ an instance of $\mathsf{CSP}(\mathcal{H})$ . Recall that every variable $v\in V$ is assigned a sort $\sigma(v)\in[k]$ . Let $\sigma^{\prime}:V\to[q]$ be such that $\xi_{\sigma^{\prime}(v)}:G_{\sigma^{\prime}(v)}\to H_{\sigma(v)}$ for each $v\in V$ . The instance $\mathcal{P}^{\sigma^{\prime}}=(V,\mathcal{C}^{\sigma^{\prime}})$ is said to be a refinement for $\mathcal{G}$ of $\mathcal{P}$ with the sort function $\sigma^{\prime}$ if it satisfies the following two conditions

(a)

every $v\in V$ is assigned the sort $\sigma^{\prime}(v)$ ;
(b)

for every $C=\langle\mathbf{s},\mathcal{R}\rangle\in\mathcal{C}$ , $\mathbf{s}=(v_{1},\dots,v_{\ell})$ , it holds that $\xi_{\sigma^{\prime}(v)}(G_{\sigma^{\prime}(v_{i})})\subseteq\mathsf{pr}_{i}% \mathcal{R}$ , $i\in[\ell]$ , and there is $C^{\prime}=\langle\mathbf{s},\xi^{-1}(\mathcal{R})\rangle\in\mathcal{C}^{% \sigma^{\prime}}$ .

The refinement $\mathcal{P}^{\sigma^{\prime}}$ is lossless if for every solution $\varphi$ of $\mathcal{P}$ the mapping $\xi^{-1}\circ\varphi$ is a solution of $\mathcal{P}^{\sigma^{\prime}}$ . Suppose $\mathcal{G}$ is full pp-definable. The refinement $\mathcal{P}^{\sigma^{\prime}}$ is minimal lossless if it is lossless and for each $v\in V$ , $\sigma^{\prime}(v)$ is minimal (with respect to inclusion of $\xi_{\sigma^{\prime}(v)}(G_{\sigma^{\prime}(v)})$ in the original domain). If $\mathcal{G}$ is full of treewidth $d$ , the definition is bit more complicated. The instance $\mathcal{P}$ can also be viewed as a structure $\mathcal{F}$ with vertex set $V$ and such that the solutions of $\mathcal{P}$ are exactly the homomorphisms from $\mathcal{F}$ to $\mathcal{H}$ , see [17]. Then $\mathcal{P}^{\sigma^{\prime}}$ is minimal lossless of width $d$ if it is lossless and for every $v\in V$ , $\xi_{\sigma^{\prime}(v)}(G_{\sigma^{\prime}(v)})$ is minimal with respect to inclusion among unary relations defined by a structure $\mathcal{G}_{v}$ of treewidth $d$ with a designated variable $x$ and such that there is a homomorphism from $\mathcal{G}_{i}$ to $\mathcal{F}$ mapping $x$ to $v$ . In fact, a minimal lossless of width $d$ structure $\mathcal{P}^{\sigma^{\prime}}$ is produced from $\mathcal{P}$ by applying an appropriate local propagation algorithm [30].

Proposition 14.

Let $\mathcal{H}$ be a multi-sorted relational structure.

(1)

Let $\mathcal{G}$ be the full width $d$ definable refinement of $\mathcal{H}$ . For any instance $\mathcal{P}$ of $\mathsf{CSP}(\mathcal{H})$ , its minimal lossless refinement of width $d$ for $\mathcal{G}$ can be found in polynomial time.
(2)

Let $\mathcal{H}$ be a relational structure containing all the constant relations and such that $\mathsf{CSP}(\mathcal{H})$ is solvable in polynomial time, and $\mathcal{G}$ the full definable refinement of $\mathcal{H}$ . Then for any instance $\mathcal{P}$ of $\mathsf{CSP}(\mathcal{H})$ , its minimal lossless refinement for $\mathcal{G}$ can be found in polynomial time.

5 An Algorithm for Parity

In this section we outline an algorithm that solves $\#_{2}\mathsf{CSP}(\mathcal{H})$ , that is, finds the parity of the number of homomorphisms to $\mathcal{H}$ , provided the structure $\mathcal{H}$ satisfies some additional conditions.

Theorem 15.

Let $\mathcal{H}$ be a 2-rigid, strongly 2-rectangular, and $\langle\mathcal{H}\rangle_{2}$ has a Mal’tsev polymorphism¹¹1Note that the latter condition does not follow from $\mathcal{H}$ having a Mal’tsev polymorphism, because 2-mpp-definitions do not preserve polymorphisms.. Then $\#_{2}\mathsf{CSP}(\mathcal{H})$ can be solved in time polynomial time.

In order to prove Theorem 15 we apply some of the existing techniques such as compact representations of relations with a Mal’tsev polymorphism, but in a novel way that is very different from its original use.

Frames and Witness Functions.

Suppose that $\mathcal{R}$ is an $n$ -ary relation with a Mal’tsev polymorphism $\varphi$ . For each $i\in[n]$ we define the following relation $\sim_{i}$ on $\mathsf{pr}_{i}\mathcal{R}$ : $a\sim_{i}b$ if there exist tuples $\mathbf{x}\in H^{i-1}$ and $\mathbf{y}_{a},\mathbf{y}_{b}\in H^{n-i}$ such that $(\mathbf{x},a,\mathbf{y}_{a})\in\mathcal{R}\text{ and }(\mathbf{x},b,\mathbf{y% }_{b})\in\mathcal{R}$ . For the case $i=1$ , we have $a\sim_{1}b$ for all $a,b\in\mathsf{pr}_{1}\mathcal{R}$ because they share the common empty prefix $\varepsilon$ . The relations $\sim_{i}$ will be called frame relations. The following observations are straightforward corollaries of the rectangularity of $\mathcal{R}$ and were used in [14].

Lemma 16 (Folklore).

Let $\mathcal{R}$ be a relation with a Mal’tsev polymorphism.

(1)

$\sim_{i}$ is an equivalence relation for all $i\in[n]$ .
(2)

If $a\sim_{i}b$ and $\mathbf{x}\in\mathcal{R}$ with $\mathbf{x}_{i}=a$ , then there is a $\mathbf{y}\in\mathcal{R}$ with $\mathbf{y}_{i}=b$ and $\mathsf{pr}_{[i-1]}\mathbf{x}=\mathsf{pr}_{[i-1]}\mathbf{y}$ .

A mapping $\omega:[n]\times H\rightarrow H^{n}\cup\{\bot\}$ is called a witness function of $\mathcal{R}$ if

(i)

For any $i\in[n]$ and $a\in H-\mathsf{pr}_{i}\mathcal{R}$ , $\omega(i,a)=\bot$ ;
(ii)

For any $i\in[n]$ and $a\in\mathsf{pr}_{i}\mathcal{R}$ , $\omega(i,a)\in\mathcal{R}$ is a witness for $(i,a)$ , i.e., $\mathsf{pr}_{i}\omega(i,a)=a$ ;
(iii)

For any $i\in[n]$ and $a,b\in\mathsf{pr}_{i}\mathcal{R}$ with $a\sim_{i}b$ , we have $\mathsf{pr}_{[i-1]}\omega(i,a)=\mathsf{pr}_{[i-1]}\omega(i,b)$ .

A witness function $\omega$ provides a concise representation of $\mathcal{R}$ . Let $F=\{\omega(i,a)\mid i\in[n],a\in\mathsf{pr}_{i}\mathcal{R}\}$ . Such a set of tuples is called a frame of $\mathcal{R}$ . A witness function (or a frame) can be found in polynomial time given a conjunctive definition (i.e. a CSP instance) of a relation in a relational structure with a Mal’tsev polymorphism. This is the property that makes them essential for solving CSPs. The following transformations of frames can be performed in polynomial time.

Proposition 17 ([5, 14]).

Let $\mathcal{H}$ be a relational structure with a Mal’tsev polymorphism and a relation $\mathcal{R}$ has a conjunctive definition $\mathcal{R}(x_{1},\dots,x_{n})=\bigwedge_{i\in[m]}\mathcal{R}_{i}(x_{i_{1}},% \dots,x_{i_{t}})$ in $\mathcal{H}$ .

(1)

A frame and a witness function for $\mathcal{R}$ can be computed in $O(mn^{4})$ .
(2)

Let $I\subseteq[n]$ . Given a frame $F$ for $\mathcal{R}$ , a frame for $\mathcal{R}(x_{1},x_{2},...,x_{n})\wedge(\bigwedge_{s\in I}C_{a_{s}}(x_{s}))$ (i.e., $x_{s}$ is the constant $a_{s}\in H$ , $s\in I$ ) can be constructed in $O(n^{3})$ time.
(3)

Given a frame $F$ for $\mathcal{R}$ , a frame for $\mathcal{Q}(x_{1},x_{2}...,x_{n-1})=\exists y\mathcal{R}(x_{1},...,x_{n-1},y)$ , can be constructed in $O(n)$ time.

Overview of the algorithm.

The exact counting algorithm in [14] first finds a frame of a conjunctive defined relation (a.k.a. the set of solutions of a CSP instance), and then uses the frame and the condition of balancedness to compute the number of solutions. Unfortunately, this approach does not work in our case, because according to the results of Section 3.1 the property of 2-balancedness that we need here does not correlate well with the existence of a Mal’tsev polymorphism. We therefore choose a different approach.

Let $\mathcal{H}$ be a structure satisfying the conditions of Theorem 15 and $\mathcal{R}\in\langle\mathcal{H}\rangle_{2}$ . Since $\langle\mathcal{H}\rangle_{2}$ has a Mal’tsev polymorphism, a frame for $\mathcal{R}$ can be computed in polynomial time by Proposition 17(1). Suppose that $\mathcal{R}$ is $n$ -ary. It is not hard to see that

|\mathcal{R}|\equiv|\exists^{\equiv 2}y\mathcal{R}(x_{1},\dots,x_{n-1},y)|% \pmod{2}.

Therefore, if it is possible to find a frame of $\widetilde{\mathcal{R}}=\exists^{\equiv 2}y\mathcal{R}(x_{1},\dots,x_{n-1},y)$ , we could repeat this process $n-1$ times eventually obtaining a unary relation $\mathcal{R}^{\prime}$ such that $|\mathcal{R}^{\prime}|\equiv|\mathcal{R}|\pmod{2}$ and then just count the elements in $\mathcal{R}^{\prime}$ using its frame. Unfortunately, it is not that straightforward, because Proposition 17(3) does not work for modular quantifiers. Instead, we use a more convoluted method.

Let $\mathsf{PAR}_{\mathcal{R}}(\mathbf{x},y)=\mathcal{R}(\mathbf{x},y)\wedge(% \exists^{\equiv 2}z\;\;\mathcal{R}(\mathbf{x},z))$ . This relation contains essentially the same tuples as $\widetilde{\mathcal{R}}$ , except it also keeps their extensions to the last coordinate position. This means that $\widetilde{\mathcal{R}}=\exists y\mathsf{PAR}_{\mathcal{R}}(\mathbf{x},y)$ , and if we know a frame of $\mathsf{PAR}_{\mathcal{R}}(\mathbf{x},y)$ , a frame of $\widetilde{\mathcal{R}}$ can be found by Proposition 17(3). Finding a frame for $\mathsf{PAR}_{\mathcal{R}}(\mathbf{x},y)$ is the crux of the algorithm.

Finding a frame for $\mathsf{PAR}_{\mathcal{R}}(\mathbf{x},y)$ .

Let $\sim_{i}$ and $\omega$ be frame relations and a witness function (a frame) of the relation $\mathcal{R}$ found in the previous step. Let $\mathcal{E}_{i}$ denote the collection of the equivalence classes of $\sim_{i}$ , and $\mathcal{E}_{i}=\{\mathcal{E}_{i,1},\dots,\mathcal{E}_{i,\ell_{i}}\}$ , $\mathcal{E}_{i,j}\subseteq\mathsf{pr}_{i}\mathcal{R}$ , where $j\in[\ell_{i}]$ . We often refer to these classes as frame classes. By $\sim^{\prime}_{i},\omega^{\prime}$ , and $\mathcal{E}^{\prime}_{i}$ , $i\in[n]$ , we denote yet unknown frame relations, witness function, and frame classes of $\mathsf{PAR}_{\mathcal{R}}$ (clearly, the number of classes in $\mathcal{E}^{\prime}_{i}$ may differ from that of $\mathcal{E}_{i}$ ).

First, we observe that by definition a tuple $(\mathbf{x},a)\in\mathcal{R}$ belongs to $\mathsf{PAR}_{\mathcal{R}}$ if and only if there is a class $\mathcal{E}_{n,s}\in\mathcal{E}_{n}$ , $s\in[\ell_{n}]$ , such that $a\in\mathcal{E}_{n,s}$ and $|\mathcal{E}_{n,s}|\equiv 1\pmod{2}$ . This makes finding $\sim^{\prime}_{n}$ and $\omega^{\prime}(n,*)$ easy, they are just restrictions of $\sim_{n}$ and $\omega(n,*)$ on the union of odd classes from $\mathcal{E}_{n}$ . For $k\in[n-1]$ and $a\in\mathsf{pr}_{k}\mathcal{R}$ we use Proposition 17(2) to find a witness function $\omega^{k\leftarrow a}$ and frame classes $\mathcal{E}_{i}^{k\leftarrow a}$ of $\mathcal{R}(x_{1},x_{2},...,x_{n})\wedge C_{a}(x_{k})$ . We examine $\mathcal{E}^{k\leftarrow a}_{n,s}$ for $s\in[|\mathcal{E}^{k\leftarrow a}_{n}|]$ . We check whether there exists $s\in[|\mathcal{E}^{k\leftarrow a}_{n}|]$ such that $|\mathcal{E}^{k\leftarrow a}_{n,s}|\equiv 1\mod 2$ . If we find such an $s$ , we select $b\in\mathcal{E}^{k\leftarrow a}_{n,s}$ and set $\omega^{\prime}(k,a)=\omega^{k\leftarrow a}(n,b)$ . By construction $\mathsf{pr}_{k}\omega^{\prime}(k,a)=\mathsf{pr}_{k}\omega^{k\leftarrow a}(n,b)=a$ , and by the observation above $\omega^{\prime}(k,a)\in\mathsf{PAR}_{\mathcal{R}}$ . Finally, in order to check whether for some $b\in\mathsf{pr}_{k}\mathcal{R}$ it holds that $a\sim^{\prime}_{k}b$ it suffices to complete the following steps. Use use Proposition 17(2) to compute a witness function $\omega^{\prime\prime}$ and frame classes of

\mathcal{R}(x_{1},\dots,x_{n})\wedge C_{b}(x_{k})\wedge(\bigwedge_{s=1}^{k-1}C% _{d_{s}}(x_{s})),

where $(d_{1},\dots,d_{n})=\omega^{k\leftarrow a}(k,a)$ . It can be shown that $a\sim^{\prime}_{k}b$ if and only if there exists $t\in[|\mathcal{E}^{\prime\prime}_{n}|]$ such that $|\mathcal{E}^{\prime\prime}_{n,t}|\equiv 1\pmod{2}$ .

This completes the outline of the algorithm.

6 Hardness and Automorphisms of Direct Products of Structures

Another crucial component of Theorem 2 is the structure of automorphisms of direct products of graphs [24]. It essentially asserts that every automorphism of a direct product $H_{1}\times\dots\times H_{n}$ can be thought of as a composition of a permutation of factors in the product and automorphisms of those factors. In the following example we show that this breaks down already for digraphs.

Example 18.

let $\mathcal{H}=(V,E)$ be a directed graph where $V=\{a,b,c,d\}$ with (directed) edge set $E=\{(b,a),(b,c),(c,d)\}$ . This digraph is rigid. However, the automorphism group of $\mathcal{H}^{2}$ , see Figure 2, has a complicated structure. As is easily seen $\mathcal{H}^{2}$ has a large number of automorphisms of order 2 and 3, not all of which have a simple representation mentioned above.

Figure 2: The structure of

\mathcal{H}

and

\mathcal{H}^{2}

.

In [9] one of the important applications of the structural theorem for automorphisms of graph products is that it allows one to prove that $\#_{p}\mathsf{Hom}(\mathcal{H}+\mathcal{R})$ , where $\mathcal{H}+\mathcal{R}$ denotes the expansion of $\mathcal{H}$ by a relation $\mathcal{R}$ pp-definable in $\mathcal{H}$ , is polynomial time reducible to $\#_{p}\mathsf{Hom}(\mathcal{H})$ . The example above indicates that this result may no longer be true for general relational structures.

Next, we explore what implications of a structural result similar to that in [24] that is used in [9] about $\mathsf{Aut}(\mathcal{H}^{n})$ can be. A rectangularity obstruction is a violation of the rectangularity or $p$ -rectangularity property, that is, a ( $n$ -ary) relation $\mathcal{R}$ pp- or $p$ -mpp-definable in a structure $\mathcal{H}$ , $k\in[n]$ , and tuples $\mathbf{a},\mathbf{b}\in\mathsf{pr}_{[k]}\mathcal{R},\mathbf{c},\mathbf{d}\in% \mathsf{pr}_{[n]-[k]}\mathcal{R}$ such that $(\mathbf{a},\mathbf{c}),(\mathbf{a},\mathbf{d}),(\mathbf{b},\mathbf{d})\in% \mathcal{R}$ , but $(\mathbf{b},\mathbf{c})\not\in\mathcal{R}$ . A generalized rectangularity obstruction are the relation $\mathcal{R}$ and sets $A_{1,1},A_{1,2}\subseteq\mathsf{pr}_{[k]}\mathcal{R}$ , $A_{2,1},A_{2,2}\subseteq\mathsf{pr}_{[n]-[k]}\mathcal{R}$ such that $A_{1,1}\cap A_{1,2}=\emptyset$ , $A_{2,1}\cap A_{2,2}=\emptyset$ , and any $\mathbf{a}\in A_{1,1},\mathbf{b}\in A_{1,2},\mathbf{c}\in A_{2,1},\mathbf{d}% \in A_{2,2}$ form a rectangularity obstruction.

At the first glance, if such an obstruction exists, it should be possible to prove the hardness of $\#_{p}\mathsf{CSP}(\mathcal{H})$ . Indeed, $\mathcal{R}$ can be viewed as a bipartite graph $\mathsf{K}_{\mathcal{R}}$ , whose parts of the bipartition are $\mathsf{pr}_{[k]}\mathcal{R}$ and $\mathsf{pr}_{[n]-[k]}\mathcal{R}$ , and as the rectangularity obstruction shows, this graph is not complete bipartite implying that $\#\mathsf{Hom}(\mathsf{K}_{\mathcal{R}})$ is #P-complete. However, the hardness of $\#_{p}\mathsf{Hom}(\mathsf{K}_{\mathcal{R}})$ also involves the requirement that $\mathsf{K}_{\mathcal{R}}$ is $p$ -rigid. $p$ -rigidity is achieved by restricting the problem to induced subgraphs of $\mathsf{K}_{\mathcal{R}}$ as in Lemma 1. However, such a subgraph may avoid the (generalized) rectangularity obstruction rendering it useless.

The obstruction $A_{1,1},A_{1,2}\subseteq\mathsf{pr}_{[k]}\mathcal{R}$ , $A_{2,1},A_{2,2}\subseteq\mathsf{pr}_{[n]-[k]}\mathcal{R}$ is said to be protected in $\mathcal{R}$ if, after applying a $p$ -reduction to $\mathcal{R}$ under a sequence of $p$ -automorphisms from $\mathsf{Aut}(\mathcal{R})$ , for the resulting relation $\tilde{\mathcal{R}}$ it holds that $\mathsf{pr}_{[k]}\tilde{\mathcal{R}}\cap A_{1,1},\mathsf{pr}_{[k]}\tilde{% \mathcal{R}}\cap A_{1,2}\neq\emptyset$ , $\mathsf{pr}_{[n]-[k]}\tilde{\mathcal{R}}\cap A_{2,1},\mathsf{pr}_{[n]-[k]}% \tilde{\mathcal{R}}\cap A_{2,2}\neq\emptyset$ . In fact, Theorem 4.2 [9] implies, although implicitly, that any $p$ -rigid graph that is not a complete bipartite graph contains a protected rectangularity obstruction. One case of a protected rectangularity obstruction is when it is protected in $\mathsf{K}_{\mathcal{R}}$ , that is, survives $p$ -reductions of $\mathsf{K}_{\mathcal{R}}$ itself. In this case we say that the obstruction is graph-protected.

Proposition 19.

Let $\mathcal{H}$ be a (multi-sorted) relational structure and $p$ a prime number. If $\mathcal{H}$ has a graph protected generalized rectangularity obstruction modulo $p$ , $\#_{p}\mathsf{CSP}(\mathcal{H})$ is $\#_{p}P$ -complete.

We consider a special case of graph-protected generalized rectangularity obstructions, standard hardness gadgets, that have to satisfy the additional condition $A_{1,1}\cup A_{1,2}=\mathsf{pr}_{[k]}\mathcal{R},A_{2,1}\cup A_{2,2}=\mathsf{% pr}_{[n]-[k]}\mathcal{R}$ . It is can be proved that a standard hardness gadget is indeed a graph-protected obstruction.

Standard hardness gadgets provide a fairly limited condition for the hardness of $\#_{p}\mathsf{CSP}(\mathcal{H})$ . In fact, it is possible to prove that $\#_{p}\mathsf{CSP}(\mathcal{H})$ is $\#_{p}P$ -complete whenever $\mathcal{H}$ has any protected rectangularity obstruction, not necessarily a standard gadget. However, it cannot be done using Theorem 2 as a black box, and is outside of the scope of this paper.

7 Binarization

While studying the structure of $\mathsf{Aut}(\mathcal{H}^{k})$ for a relational structure $\mathcal{H}$ and an integer $k$ may be a difficult problem, in this Section we make a step forward by reducing the class of structures $\mathcal{H}$ for which such a characterization is required. In particular, we show that it suffices to obtain a characterization for structures with only binary rectangular relations. More precisely, for any relational structure $\mathcal{H}=(H;\mathcal{R}_{1},\dots,\mathcal{R}_{k})$ we construct its binarization $b(\mathcal{H})$ as follows. The structure $b(\mathcal{H})$ is multi-sorted, and the domains are the relations $\mathcal{R}_{1},\dots,\mathcal{R}_{k}$ viewed as sets of tuples, thus, $b(\mathcal{H})$ has $k$ domains. For every pair $i,j\in[k]$ ( $i, j$ are allowed to be equal) and any $s\in[\ell_{i}],t\in[\ell_{j}]$ , where $\ell_{i},\ell_{j}$ are the arities of $\mathcal{R}_{i},\mathcal{R}_{j}$ , the structure $b(\mathcal{H})$ contains a binary relation $\mathcal{Q}^{ij}_{st}=\{(\mathbf{a},\mathbf{b})\mid\mathbf{a}\in\mathcal{R}_{i% },\mathbf{b}\in\mathcal{R}_{j},\mathbf{a}[s]=\mathbf{b}[t]\}$ . We show that $\mathcal{H}$ and $b(\mathcal{H})$ share many important properties.

Theorem 20.

Let $\mathcal{H}$ be a relational structure. Then $\mathcal{H}$ is strongly rectangular ( $p$ -strongly rectangular, $p$ -rigid, has a Mal’tsev polymorphism) if and only if $b(\mathcal{H})$ is strongly rectangular ( $p$ -strongly rectangular, $p$ -rigid, has a Mal’tsev polymorphism).

In addition to Theorem 20 every relation of $b(\mathcal{H})$ is binary and rectangular. This makes such structures somewhat closer to graphs and the hope is that it will be easier to study the structure of $\mathsf{Aut}(b(\mathcal{H})^{n})$ than $\mathsf{Aut}(\mathcal{H}^{n})$ itself.

References

[1] Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and how to use them. In Dagstuhl Follow-Ups, volume 7. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/DFU.VOL7.15301.1.
[2] Alexander I. Barvinok. Combinatorics and Complexity of Partition Functions, volume 30 of Algorithms and combinatorics. Springer, 2016. doi:10.1007/978-3-319-51829-9.
[3] Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. J. ACM, 60(5):34:1–34:41, 2013. doi:10.1145/2528400.
[4] Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In Chris Umans, editor, FOCS, pages 319–330, 2017. doi:10.1109/FOCS.2017.37.
[5] Andrei A. Bulatov and Víctor Dalmau. A simple algorithm for Mal’tsev constraints. SIAM J. Comput., 36(1):16–27, 2006. doi:10.1137/050628957.
[6] Andrei A. Bulatov and Víctor Dalmau. Towards a dichotomy theorem for the counting constraint satisfaction problem. Information and Computation, 205(5):651–678, 2007. doi:10.1016/J.IC.2006.09.005.
[7] Andrei A. Bulatov and Martin Grohe. The complexity of partition functions. Theor. Comput. Sci., 348(2-3):148–186, 2005. doi:10.1016/J.TCS.2005.09.011.
[8] Andrei A. Bulatov, Peter Jeavons, and Andrei A. Krokhin. Classifying the complexity of constraints using finite algebras. SIAM J. Comput., 34(3):720–742, 2005. doi:10.1137/S0097539700376676.
[9] Andrei A. Bulatov and Amirhossein Kazeminia. Complexity classification of counting graph homomorphisms modulo a prime number. In STOC, pages 1024–1037. ACM, 2022. doi:10.1145/3519935.3520075.
[10] Jin-Yi Cai and Xi Chen. Complexity of counting CSP with complex weights. J. ACM, 64(3), June 2017. doi:10.1145/2822891.
[11] Jin-yi Cai and Lane A. Hemachandra. On the power of parity polynomial time. In Burkhard Monien and Robert Cori, editors, STACS, volume 349 of Lecture Notes in Computer Science, pages 229–239. Springer, 1989. doi:10.1007/BFB0028987.
[12] Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci., 329(1-3):315–323, 2004. doi:10.1016/J.TCS.2004.08.008.
[13] M. Dyer and C. Greenhill. The complexity of counting graph homomorphisms. Random Structures and Algorithms, 17:260–289, 2000. doi:10.1002/1098-2418(200010/12)17:3/4\%3C260::AID-RSA5\%3E3.0.CO;2-W.
[14] Martin Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem. SIAM J. on Comp, 42(3):1245–1274, 2013. doi:10.1137/100811258.
[15] John Faben. The complexity of counting solutions to generalised satisfiability problems modulo $k$ , 2008. arXiv:0809.1836.
[16] John Faben and Mark Jerrum. The complexity of parity graph homomorphism: an initial investigation. arXiv preprint arXiv:1309.4033, 2013. arXiv:1309.4033.
[17] Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput., 28(1):57–104, 1998. doi:10.1137/S0097539794266766.
[18] Jacob Focke, Leslie Ann Goldberg, Marc Roth, and Stanislav Zivný. Counting homomorphisms to $k_{4}$ -minor-free graphs, modulo 2. In Dániel Marx, editor, SODA, pages 2303–2314. SIAM, 2021. doi:10.1137/1.9781611976465.137.
[19] Andreas Göbel, Leslie Ann Goldberg, and David Richerby. Counting homomorphisms to square-free graphs, modulo 2. ACM Transactions on Computation Theory (TOCT), 8(3):1–29, 2016. doi:10.1145/2898441.
[20] Andreas Göbel, J. A. Gregor Lagodzinski, and Karen Seidel. Counting homomorphisms to trees modulo a prime. In MFCS, volume 117, pages 49:1–49:13, 2018. doi:10.4230/LIPICS.MFCS.2018.49.
[21] Heng Guo, Sangxia Huang, Pinyan Lu, and Mingji Xia. The Complexity of Weighted Boolean $\#$ CSP Modulo k. In STACS), volume 9, pages 249–260, 2011. doi:10.4230/LIPICS.STACS.2011.249.
[22] Andreas Göbel, Leslie Ann Goldberg, and David Richerby. The complexity of counting homomorphisms to cactus graphs modulo 2. ACM Trans on Comp Th, 6(4):1–29, 2014. doi:10.1145/2635825.
[23] J. Hagemann and A. Mitschke. On $n$ -permutable congruences. Algebra Universalis, 3:8–12, 1973.
[24] Richard Hammack, Wilfried Imrich, and Sandi Klavzar. Handbook of Product Graphs, Second Edition. CRC Press, Inc., USA, 2nd edition, 2011.
[25] Ulrich Hertrampf. Relations among mod-classes. Theor. Comput. Sci., 74(3):325–328, 1990. doi:10.1016/0304-3975(90)90081-R.
[26] Peter Jeavons. On the algebraic structure of combinatorial problems. Theoretical Computer Science, 200(1-2):185–204, 1998. doi:10.1016/S0304-3975(97)00230-2.
[27] Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput., 22(5):1087–1116, 1993. doi:10.1137/0222066.
[28] Amirhossein Kazeminia and Andrei A Bulatov. Counting homomorphisms modulo a prime number. In MFCS. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019.
[29] Amirhossein Kazeminia and Andrei A. Bulatov. Modular counting csp: Reductions and algorithms, 2025. arXiv:2501.04224.
[30] Phokion G Kolaitis. Constraint satisfaction, complexity, and logic. In Hellenic Conference on Artificial Intelligence, pages 1–2. Springer, 2004. doi:10.1007/978-3-540-24674-9_1.
[31] J. A. Gregor Lagodzinski, Andreas Göbel, Katrin Casel, and Tobias Friedrich. On counting (quantum-)graph homomorphisms in finite fields of prime order. CoRR, abs/2011.04827, 2021. arXiv:2011.04827.
[32] E.H. Lieb and A.D. Sokal. A general Lee-Yang theorem for one-component and multicomponent ferromagnets. Communications in Mathematical Physics, 80(2):153–179, 1981.
[33] L. Valiant. The complexity of computing the permanent. Theoretical Computing Science, 8:189–201, 1979. doi:10.1016/0304-3975(79)90044-6.
[34] L. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410–421, 1979. doi:10.1137/0208032.
[35] Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. J. ACM, 67(5):30:1–30:78, 2020. doi:10.1145/3402029.

[bib.bib1] [1] Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and how to use them. In Dagstuhl Follow-Ups, volume 7. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/DFU.VOL7.15301.1.

[bib.bib2] [2] Alexander I. Barvinok. Combinatorics and Complexity of Partition Functions, volume 30 of Algorithms and combinatorics. Springer, 2016. doi:10.1007/978-3-319-51829-9.

[bib.bib3] [3] Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. J. ACM, 60(5):34:1–34:41, 2013. doi:10.1145/2528400.

[bib.bib4] [4] Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In Chris Umans, editor, FOCS, pages 319–330, 2017. doi:10.1109/FOCS.2017.37.

[bib.bib5] [5] Andrei A. Bulatov and Víctor Dalmau. A simple algorithm for Mal’tsev constraints. SIAM J. Comput., 36(1):16–27, 2006. doi:10.1137/050628957.

[bib.bib6] [6] Andrei A. Bulatov and Víctor Dalmau. Towards a dichotomy theorem for the counting constraint satisfaction problem. Information and Computation, 205(5):651–678, 2007. doi:10.1016/J.IC.2006.09.005.

[bib.bib7] [7] Andrei A. Bulatov and Martin Grohe. The complexity of partition functions. Theor. Comput. Sci., 348(2-3):148–186, 2005. doi:10.1016/J.TCS.2005.09.011.

[bib.bib8] [8] Andrei A. Bulatov, Peter Jeavons, and Andrei A. Krokhin. Classifying the complexity of constraints using finite algebras. SIAM J. Comput., 34(3):720–742, 2005. doi:10.1137/S0097539700376676.

[bib.bib9] [9] Andrei A. Bulatov and Amirhossein Kazeminia. Complexity classification of counting graph homomorphisms modulo a prime number. In STOC, pages 1024–1037. ACM, 2022. doi:10.1145/3519935.3520075.

[bib.bib10] [10] Jin-Yi Cai and Xi Chen. Complexity of counting CSP with complex weights. J. ACM, 64(3), June 2017. doi:10.1145/2822891.

[bib.bib11] [11] Jin-yi Cai and Lane A. Hemachandra. On the power of parity polynomial time. In Burkhard Monien and Robert Cori, editors, STACS, volume 349 of Lecture Notes in Computer Science, pages 229–239. Springer, 1989. doi:10.1007/BFB0028987.

[bib.bib12] [12] Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci., 329(1-3):315–323, 2004. doi:10.1016/J.TCS.2004.08.008.

[bib.bib13] [13] M. Dyer and C. Greenhill. The complexity of counting graph homomorphisms. Random Structures and Algorithms, 17:260–289, 2000. doi:10.1002/1098-2418(200010/12)17:3/4\%3C260::AID-RSA5\%3E3.0.CO;2-W.

[bib.bib14] [14] Martin Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem. SIAM J. on Comp, 42(3):1245–1274, 2013. doi:10.1137/100811258.

[bib.bib15] [15] John Faben. The complexity of counting solutions to generalised satisfiability problems modulo $k$ , 2008. arXiv:0809.1836.

[bib.bib16] [16] John Faben and Mark Jerrum. The complexity of parity graph homomorphism: an initial investigation. arXiv preprint arXiv:1309.4033, 2013. arXiv:1309.4033.

[bib.bib17] [17] Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput., 28(1):57–104, 1998. doi:10.1137/S0097539794266766.

[bib.bib18] [18] Jacob Focke, Leslie Ann Goldberg, Marc Roth, and Stanislav Zivný. Counting homomorphisms to $k_{4}$ -minor-free graphs, modulo 2. In Dániel Marx, editor, SODA, pages 2303–2314. SIAM, 2021. doi:10.1137/1.9781611976465.137.

[bib.bib19] [19] Andreas Göbel, Leslie Ann Goldberg, and David Richerby. Counting homomorphisms to square-free graphs, modulo 2. ACM Transactions on Computation Theory (TOCT), 8(3):1–29, 2016. doi:10.1145/2898441.

[bib.bib20] [20] Andreas Göbel, J. A. Gregor Lagodzinski, and Karen Seidel. Counting homomorphisms to trees modulo a prime. In MFCS, volume 117, pages 49:1–49:13, 2018. doi:10.4230/LIPICS.MFCS.2018.49.

[bib.bib21] [21] Heng Guo, Sangxia Huang, Pinyan Lu, and Mingji Xia. The Complexity of Weighted Boolean $\#$ CSP Modulo k. In STACS), volume 9, pages 249–260, 2011. doi:10.4230/LIPICS.STACS.2011.249.

[bib.bib22] [22] Andreas Göbel, Leslie Ann Goldberg, and David Richerby. The complexity of counting homomorphisms to cactus graphs modulo 2. ACM Trans on Comp Th, 6(4):1–29, 2014. doi:10.1145/2635825.

[bib.bib23] [23] J. Hagemann and A. Mitschke. On $n$ -permutable congruences. Algebra Universalis, 3:8–12, 1973.

[bib.bib24] [24] Richard Hammack, Wilfried Imrich, and Sandi Klavzar. Handbook of Product Graphs, Second Edition. CRC Press, Inc., USA, 2nd edition, 2011.

[bib.bib25] [25] Ulrich Hertrampf. Relations among mod-classes. Theor. Comput. Sci., 74(3):325–328, 1990. doi:10.1016/0304-3975(90)90081-R.

[bib.bib26] [26] Peter Jeavons. On the algebraic structure of combinatorial problems. Theoretical Computer Science, 200(1-2):185–204, 1998. doi:10.1016/S0304-3975(97)00230-2.

[bib.bib27] [27] Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput., 22(5):1087–1116, 1993. doi:10.1137/0222066.

[bib.bib28] [28] Amirhossein Kazeminia and Andrei A Bulatov. Counting homomorphisms modulo a prime number. In MFCS. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019.

[bib.bib29] [29] Amirhossein Kazeminia and Andrei A. Bulatov. Modular counting csp: Reductions and algorithms, 2025. arXiv:2501.04224.

[bib.bib30] [30] Phokion G Kolaitis. Constraint satisfaction, complexity, and logic. In Hellenic Conference on Artificial Intelligence, pages 1–2. Springer, 2004. doi:10.1007/978-3-540-24674-9_1.

[bib.bib31] [31] J. A. Gregor Lagodzinski, Andreas Göbel, Katrin Casel, and Tobias Friedrich. On counting (quantum-)graph homomorphisms in finite fields of prime order. CoRR, abs/2011.04827, 2021. arXiv:2011.04827.

[bib.bib32] [32] E.H. Lieb and A.D. Sokal. A general Lee-Yang theorem for one-component and multicomponent ferromagnets. Communications in Mathematical Physics, 80(2):153–179, 1981.

[bib.bib33] [33] L. Valiant. The complexity of computing the permanent. Theoretical Computing Science, 8:189–201, 1979. doi:10.1016/0304-3975(79)90044-6.

[bib.bib34] [34] L. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410–421, 1979. doi:10.1137/0208032.

[bib.bib35] [35] Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. J. ACM, 67(5):30:1–30:78, 2020. doi:10.1145/3402029.

Modular Counting CSP: Reductions and Algorithms

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Homomorphisms and the Constraint Satisfaction Problem.

Counting CSP.

Modular Counting.

Lemma 1 ([9, 16]).

The existing results on modular counting.

Theorem 2 ([9]).

Our Results.

Theorem 3.

Theorem 4.

2 Preliminaries

2.1 Multi-Sorted Sets and Relational Structures

Proposition 5.

2.2 Expansion of relational structures

Lemma 6 ([9]).

Theorem 7 ([9]).

Theorem 8.

Lemma 9 ([9]).

2.3 Modular Expansion of Relational Structures

Theorem 10.

3 Structural Properties for Counting

3.1 Rectangularity, Permutability, and Friends

𝒑-Rectangularity.

𝒑-Balancedness.

𝒑-Permutability.

Example 11.

4 Rigitity and Multi-sorted Structures

Example 12.

Lemma 13 ([17, 30]).

Proposition 14.

5 An Algorithm for Parity

Theorem 15.

Frames and Witness Functions.

Lemma 16 (Folklore).

Proposition 17 ([5, 14]).

Overview of the algorithm.

Finding a frame for 𝗣𝗔𝗥𝓡⁢(𝐱,𝒚).

6 Hardness and Automorphisms of Direct Products of Structures

Example 18.

Proposition 19.

7 Binarization

Theorem 20.

References

$𝒑$ -Rectangularity.

$𝒑$ -Balancedness.

$𝒑$ -Permutability.

Finding a frame for $\mathsf{PAR}_{\mathcal{R}}(\mathbf{x},y)$ .