P-Time Algorithms for Typical #EO Problems
Abstract
In this article, we study the computational complexity of counting weighted Eulerian orientations, denoted as #EO. This problem is considered a pivotal scenario in the complexity classification for Holant, a counting framework of great significance. Our results consist of three parts. First, we prove a complexity dichotomy theorem for #EO defined by a set of binary and quaternary signatures, which generalizes the previous dichotomy for the six-vertex model. Second, we prove a dichotomy for #EO defined by a set of so-called pure signatures, which possess the closure property under gadget construction. Finally, we present a polynomial-time algorithm for #EO defined by specific rebalancing signatures, which extends the algorithm for pure signatures to a broader range of problems, including #EO defined by non-pure signatures such as . We also construct a signature that is not rebalancing, and whether is computable in polynomial time remains open.
Keywords and phrases:
Counting complexity, Eulerian orientation, Holant, #P-hardness, Dichotomy theoremCategory:
Track A: Algorithms, Complexity and GamesCopyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Theory of computation Problems, reductions and completenessAcknowledgements:
We sincerely thank Yicheng Pan for providing a simplified proof of a lemma in the full version.Funding:
All authors are supported by National Key R&D Program of China (2023YFA1009500), NSFC 61932002 and NSFC 62272448.Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele PuppisSeries and Publisher:

1 Introduction
In fields such as statistical physics, economics, machine learning, and combinatorics, the role of counting problems is becoming increasingly significant. Three well-founded frameworks have been put forth for the study of the complexity of counting problems: #GH, , and Holant. These frameworks are capable of expressing a wide range of natural counting problems and are of great significance in counting complexity. For example, counting vertex covers in a graph can be expressed in #GH, while counting perfect matchings is a Holant problem. The definitions of these frameworks are as follows; see [9, Section 1.2] and [16, section 2.1] for details. In this paper, we always restrict the variables in these counting problems to the Boolean domain, where each variable can only take values in , by default.
We begin by introducing some basic concepts. A Boolean variable takes values from a Boolean domain consisting of two symbols . Sometimes we treat it as , the finite field of size 2, to characterize special tractable classes.
A signature with variables is a mapping from to . The value of on an input is denoted as or . The set of all variables of is denoted by , and its size by .
Definition 1 (#GH).
A counting weighted graph homomorphisms problem parameterized by a binary signature is as the following: The input is a directed graph222In this article, graphs refer to multigraphs. It is always permissible for self-loops and parallel edges to be present. . The output is
Definition 2 ().
A counting constraint satisfaction problem parameterized by a set is as the following: The input is an instance of , which consists of a finite set of variables and a finite set of clauses. Each clause in contains a signature of arity and a sequence of variables of length from 333A variable can appear in the sequence more than one time.. The output is
Definition 3 (Holant).
A Holant problem parameterized by a set is as the following: The input is an signature grid over , denoted by . Here, is a graph and assigns a signature of arity to and a linear order to for each , where are the edges adjacent to . The output is the partition function of ,
The bipartite Holant problem is a Holant problem over the signature grid , where is a bipartite graph, and assigns signatures from to vertices in and signatures from to vertices in .
The framework of Holant is capable of expressing counting weighted graph homomorphisms (#GH) and counting constraint satisfaction problems (). Consequently, Holant is widely regarded as one of the most general and significant frameworks in counting complexity.
Significant progress has been made in the study of #GH [38, 35, 29, 6, 28, 33, 12, 11], [6, 8, 27, 5, 22, 31, 34, 4, 7, 30, 25, 13, 10], [19, 16, 43], and Holant [22, 23, 24, 21, 1, 26, 2, 37, 17, 42]. Moreover, the computational complexity of #GH and has been fully characterized by dichotomy theorems [12, 25]. In contrast, the complexity classification for Holant remains unresolved.
There have been several constructive attempts on Holant. A signature is said to be symmetric if all its values for inputs with the same number of 1’s are identical. A complete dichotomy is established when all signatures are symmetric [21]. When signatures are not restricted to be symmetric, a complete dichotomy has been proven for nonnegative-weighted signatures [37] and real-weighted signatures [42]. Additionally, dichotomies exist for several special forms of complex-weighted Holant, such as [24], [1], and [2], with some given auxiliary signatures.
Recently, counting weighted Eulerian orientation problems () have also attracted researchers’ attention, as real-weighted Holant can express problems defined by signatures with the ARS property [16] under a holographic transformation by , while complex-weighted Holant can express problems under the same transformation. The complexity classification for complex-weighted problems remains open, and therefore this article seeks a more generalized characterization of complexity.
1.1 Counting weighted Eulerian orientation
We first introduce the concept of . We use to denote the set of strings with fewer 1’s than 0’s. For example, since the number of 1’s (which is 2) is strictly less than the number of 0’s (which is 3). We similarly define , , , and . The support of a signature , denoted , is the set of all inputs for which is non-zero. If , we call an EO signature.
For any Eulerian graph , let denote all Eulerian orientations of . For a given orientation in , we assign to the head and to the tail of each edge. Therefore, a Eulerian orientation corresponds to an assignment to both ends of every edge, where for each vertex, the number of adjacent ends assigned equals those assigned .
Definition 4 ().
A problem parameterized by a signature set of EO signatures is as the following: The input is an EO-signature grid over , denoted by . Here, is a Eulerian graph and assigns a signature of arity to and a linear order to for each , where are the edges adjacent to . The output is the partition function of ,
Several complexity results have been established for . In [19], a complexity dichotomy was proved for a single complex-weighted quaternary signature, known as the six-vertex model dichotomy. This result was later extended to planar graphs in [18]. Furthermore, [16] established a complexity dichotomy for signatures satisfying the arrow reversal symmetry (ARS) property, a setting commonly assumed in physics.
There are two motivations for studying problems. First, specific forms of problems appear in many areas such as statistical physics and combinatorics. In statistical physics, both the ice-type model and the six-vertex model [41] are special cases of problems. The latter model, in particular, has emerged as a prominent focus within statistical physics and corresponds exactly to defined on 4-regular graphs. In combinatorics, the resolution of the Alternating Sign Matrix conjecture [3] and the evaluation of the Tutte polynomial at (3,3) [36] both relate to problems defined on specific graphs with particular signatures.
Second, we conjecture that resolving problems is essential for establishing the complete dichotomy for complex-weighted Holant problems. The significance of EO-signatures was first recognized in [21] during the study of vanishing signatures. Furthermore, [37] suggests that classifying problems may complement the tensor decomposition lemma for complex-weighted signatures. Most directly, [42] demonstrates that research on corresponding problems (defined by signatures with ARS property), initially conducted in [16], constitutes a crucial component of the proof for the real-weighted Holant dichotomy. Additionally, the eight-vertex model dichotomy presented in [15], where the problem is defined by a single quaternary signature whose support confined to , builds upon the six-vertex model dichotomy in [19]. We believe that some fundamental obstacles to establishing complete complexity classifications for complex-weighted Holant problems lie hidden within complex-weighted problems.
1.2 Our results
All results in this paper target and hold for complex-weighted by default. The study begins with analyzing low-arity signatures, a prevalent research focus in counting problems. This approach is justified because an EO signature with arity greater than 4 can generate various quaternary and binary signatures through gadget construction. Our first result is stated below, with its detailed version presented in Theorem 20.
Theorem 5.
Suppose is a finite set of EO signatures with arity less or equal than 4. Then is either polynomial time computable or #P-hard. The classification criterion is explicit.
To establish a complete complexity classification for problems, we build upon Theorem 5 as a foundation. We note that the tractable cases exhibit a more complex structure compared to those in the six-vertex model dichotomy.
Our second result concerns pure signatures. For a set of 01-strings with length , the affine span of is defined as the minimal affine subspace containing . Given a signature , we denote by the affine span of its support . Given the affine span of a signature ’s support, we call a pure-up (resp. pure-down) signature if it is contained in (resp. ).
Our investigation originates from a quaternary signature with . Its affine span motivates modifying to by assigning a nonzero value at input 1111. Building on [21]’s result that (since strings do not contribute to the partition function), we establish . This support augmentation technique fundamentally motivates our study of pure signatures. Notably, Theorem 6’s tractable cases generalize those in Theorem 5.
Theorem 6.
Suppose is a finite set of pure-up (pure-down) EO signatures. Then is either polynomial time computable or #P-hard. The classification criterion is explicit.
The detailed statement of Theorem 6 appear in Theorem 23. To achieve tractability, a condition called the type condition must be satisfied in Theorem 6. This condition also plays a crucial role in the subsequent algorithm. Additionally, we define a property called rebalancing. Intuitively, a signature is 0-rebalancing (or 1-rebalancing) if fixing some of its variables to 0 (respectively 1) naturally forces an equal number of variables to be fixed to 1 (respectively 0). When both the type condition and rebalancing condition are satisfied, a polynomial-time algorithm becomes applicable. We emphasize that this algorithm represents the most significant algorithmic contribution of this paper. Our third result is stated below, with a formal version in Theorem 25.
Theorem 7.
is polynomial time computable, if every is 0-rebalancing (or 1-rebalancing), and satisfies the type condition.
We note that very recently, and independently of our work, [43] proposed a polynomial-time algorithm for 01-weighted parameterized by consisting of -affine (resp. -affine) signatures and affine signatures, termed the chain reaction algorithm. Moreover, [43] establishes a novel connection between the base level of -affine and -affine signatures (the -affine and -affine kernels) and the Hadamard code, while proving #P-hardness when -affine and -affine signatures are mixed. Although these results do not constitute a complete dichotomy and primarily apply to 0-1 weighted signatures, they capture some of the significant components of our dichotomy and prove highly valuable, as demonstrated in this work.
Furthermore, building upon this article and utilizing our dichotomy for pure signatures [40], a complete dichotomy for complex-weighted has been established. However, this dichotomy is an versus #P dichotomy, indicating that problems are either in or #P-hard. While this dichotomy provides valuable insights and partially clarifies the complexity classification, it does not yield new polynomial-time algorithms for and consequently does not include our algorithm for rebalancing signatures.
1.3 Our methods
As presented in Section 1.2, this article contains three parts. In each part, our main objective is to characterize different classes of signature sets. Indeed, the principal difficulty lies in providing descriptions of tractable cases that are sufficiently precise to capture all tractable scenarios. Following this characterization, we separately prove both tractability and #P-hardness results.
In each part, we perform detailed characterizations of signature sets, including comprehensive classifications and rigorous examinations of their properties. Specifically, we focus on three key aspects: the closure property, the properties of the affine span, and signature reducibility.
We further summarize that each tractable case in this work must satisfy two requirements: the support requirement and the type requirement. The support requirement specifies that each signature’s support must possess a particular form. This specific form enables a receiving-sending mechanism that is necessary for implementing the corresponding algorithm. The type requirement states that after applying the receiving-sending mechanism to an instance, all resulting signatures must form a tractable case in . A detailed explanation appears in Section 3.
For the hardness results, we prove #P-hardness based on the dichotomies of both the six-vertex model and , primarily using the gadget construction method introduced in Section 2.3.
1.4 Organization
2 Preliminaries
2.1 Definitions and notations
For a -string , we use to denote the dual string of , which is obtained by flipping every bit of . For , we use to denote the number of ’s in . Under this notation we have:
A signature is called a signature (precisely an EO signature) if . The term “EO signature” was originally introduced in [16] as shorthand for Eulerian Orientation signature.
If , we call an signature. Other similar notations are defined analogously by replacing “” with “”, “”, or “” in both names and defining formulae.
We use to denote a symmetric signature of arity , where gives the evaluation for all input strings with Hamming weight .
By exchanging the values of the symbols in the Boolean domain, we obtain the dual signature . A signature is called self-dual if . The concepts of “dual” and “self-dual” can be naturally generalized to asymmetric signatures, sets of signatures, Boolean domain counting problems, and tractable classes in dichotomy theorems.
We use to denote the truth value of a logical statement . It takes values from , or equivalently the isomorphic integer set . For example, equals True (or 1) when , and False (or 0) otherwise. Thus both and represent the value of the binary function evaluated at .
Several sets of frequently used signatures are defined as follows. represents the unary signature , with its dual . The binary disequality signature is denoted by and serves as an example of self-dual signatures. We use to denote the set of equality signatures where , with denoting an arity- signature . In other words, evaluates to 1 when the input is all 0s or all 1s, and 0 otherwise.
A disequality signature of arity , denoted by , evaluates to 1 when , and 0 otherwise. We define as the set of all disequality signatures. Moreover, is closed under variable permutation. That is, for any , a signature that evaluates to 1 when (and 0 otherwise) is also considered a disequality signature.
An alternative definition states that a signature is a disequality signature if: (1) it is an EO signature of arity , (2) there exists such that , and (3) . The equivalence of these definitions can be readily verified. Similarly, a signature is called a generalized disequality signature (denoted by ) if the signature satisfies (1), (2) and (3’) , .
We use to denote tensor multiplication. When no ambiguity arises, we sometimes use to denote the signature set . We use and to respectively denote polynomial-time Turing reductions and equivalences.
2.2 Relationships between counting problems
We say a framework is more “general” than , denoted as , if each problem in can be transformed into a problem in in polynomial time. The relationship between the counting frameworks are concluded in the following lemma.
Lemma 8.
Furthermore, Holant constitutes a strictly more expressive framework than , as evidenced by the fact that while counting perfect matchings cannot be represented as a problem [20], it can be formulated as a Holant problem.
Lemma 9.
Lemma 10 ([16]).
.
Lemma 11 ([42]).
Lemma 12 ([16, Theorem 6.1]).
We now clarify the notation used in the preceding lemmas, which will also appear throughout this article. Here, , and denotes the signature set derived from via the holographic transformation defined by [44, 14].
While we omit both the formal definition of holographic transformations and the proof of this lemma since they are not central to our discussion, we strongly recommend readers consult [9][Section 1.3.2] for deeper understanding, as holographic transformations constitute a powerful technique in counting complexity theory.
Let be an EO signature of arity with variable set . For any pairing of , we define as the subset of corresponding to :
equivalently expressed as .
When , we call an signature relative to . If such a pairing exists, we call a pairwise opposite signature (identical to Definition 5.5 in [16]), or simply an signature.
For an signature with , we define (or ) as the set of arity- signatures satisfying:
Since allows swapping variables within pairs, we have .
The inverse mapping is defined for any arity- signature as:
where (or ) is clearly an signature with . Extending this to signature sets, we define .
The set contains and all signatures obtainable from by variable flips using binary disequality. This establishes an equivalence between and with free binary disequality. As established in [16], Lemma 12 comes from this observation and the complexity equivalence between and with free binary disequality.
2.3 Gadget construction and signature matrix
This subsection introduces two key concepts: gadget construction and signature matrices. Gadget construction serves as a fundamental reduction technique in complexity classification, while signature matrices offer an intuitive representation of signatures and reveal connections between gadget construction and matrix multiplication.
Given a signature set , an -gate resembles a signature grid from Definition 3, but with where represents vertices, denotes internal edges (each connecting two vertices) and denotes dangling edges (each connecting one vertex). An -gate essentially defines a signature whose variables correspond to edges in . For and , with edges in representing variables and edges in representing , the -gate’s signature satisfies:
where assigns values to dangling edge variables, extends with these assignments and denotes the signature at vertex .
We say is realizable from via gadget construction when is an -gate’s signature. Crucially, when is realizable from , [9, Lemma 1.3] establishes:
For problems, -gates have a modified definition. Since Lemma 10 shows , we add vertices to internal edges and treat the gadget as a standard Holant gate. Throughout this paper, -gates in contexts follow this definition unless stated otherwise.
Next, we introduce the matrix form of signatures, which provides an orderly way to enumerate all possible values of a signature. Let be an arbitrary signature mapping from to . First we fix an ordering of the variables as . The matrix form of (or signature matrix of [9]) with parameter is a matrix for some integer , where the values of determine the row index and the values of determine the column index. This matrix is denoted by . For convenience, we sometimes omit and write simply , or use the abbreviated form when no ambiguity arises. For signatures with even arity, we typically choose .
Example 13 (Signature matrix).
If is a binary signature and , then .
If is a quaternary signature, then
We now establish the connection between matrix multiplication and gadget construction. Consider two -gates and with arities and respectively, where and . By connecting a subset of their dangling edges - specifically pairing with for some positive integer , we construct a new -gate .
The resulting signature has variables . Through direct comparison of gadget computation and matrix multiplication, we obtain:
For problems, the only modification is that edges now represent instead of , yielding:
This relationship will be frequently employed in subsequent discussions without further explanation.
We highlight two special forms of gadget construction: self-loop and pinning. In problems, adding a self-loop to signature involves selecting two variables and and connecting them with an internal edge, yielding new signature . For , since the internal edge represents , we obtain:
This operation can be generalized using . Instead of directly connecting and , we introduce a new vertex assigned and connect and to its dangling edges. The two possible connection orders yield either: or .
Pinning represents the second key operation. While standard Holant and problems use or to fix variables, problems employ self-loops. For , pinning simultaneously fixes and , preserving the EO property. The resulting signature is denoted . Throughout this paper, “pinning signature” refers unambiguously to .
2.4 Two known dichotomies for #CSP and Six-vertex model
In this section, we introduce the dichotomies for and six-vertex model. We start from defining tractable classes and . Let be a -dimensional column vector over . Suppose is a matrix over . The function takes value 1 when , otherwise 0. In other words, describe an affine relation on variables .
Definition 14 ([25]).
We denote by the set of signatures which have the form , where , , , each is a 0-1 indicator function of the form , where is a -dimensional vector over , and the dot product is computed over .
Definition 15 ([25]).
We denote by the set of all signatures which can be expressed a product of unary signatures, binary equality signatures () and binary disequality signatures () (on not necessarily disjoint subsets of variables).
As in [9, chapter 3], and are closed under gadget construction. That is, if or , then all -gates are respectively in or . Now we state the dichotomy for from [25, Theorem 3.1].
Theorem 16 ([25]).
Suppose is a finite set of signatures mapping Boolean inputs to complex numbers. If or , then is computable in polynomial time. Otherwise, is #P-hard.
For EO signatures belonging to or , they satisfy the following properties.
Lemma 17 ([16, Lemma 5.7]).
If an EO signature has affine support, then is a pairwise opposite signature ( signature).
Lemma 18 ([16]).
(resp. ) if and only if (resp. ).
Now we introduce some definitions for the dichotomy for six-vertex model. is the set of all ternary signatures whose supports only contain strings of Hamming weight exactly 1. In other words, a quaternary EO signature , if and only if . is defined similarly, except that the Hamming weight of each support string is exactly 2. The dichotomy for six-vertex model is as follows.
Theorem 19 ([19]).
Let f be a quaternary EO signature, then is #P-hard except for the following cases:
a. (equivalently, and );
b. (equivalently, and );
c. ;
d. ;
in which cases is computable in polynomial time.
2.5 Insights from tractable cases
Starting from this section, this article presents a number of insights pertaining to the tractable cases within each dichotomy. The objective is to generalize these tractable cases at a high level of abstraction, although some statements may be informal. It is our hope that these generalized characteristics, derived from the tractable cases, will prove a valuable point of reference for future research.
In the dichotomy of , both and are self-dual signature sets. All signatures in and have affine supports, so having affine support is a necessary condition for tractability here, and we consider this condition as a support requirement. Informally speaking, there are two ways to reach tractability based on the support requirement, namely type and type requirements. The two steps explanation for the tractability part in Theorem 16, will be used as an important template in explaining the following results. We hope to exhibit an informal evolution process from the known tractable cases to the new tractable cases in this way.
In the dichotomy for six-vertex model, the support requirement is an union of two parts. The first part is that the support must be affine. Regardless of variable permutations, it is exactly an affine subspace of . This corresponds to the tractable cases a and b in Theorem 19.
The second part is that the support must be an subset of or its dual, . This requirement itself is enough for tractability. Noticing that if each signature in the instance satisfies that , then one of its variables is fixed to 1, say . Transmitted by , as well as the general binary disequality signatures in the instance, another edge of a signature will be fixed to 0. Then the valid part of , the set of strings that can appear in an assignment with non-zero evaluation, is of size at most two and meets the affine support requirement. We denote this process as the receiving-sending mechanism. This mechanism directly corresponds to the chain reaction algorithm in [43]. This process may repeat many rounds, until each signature collapses to . At each round, an opposite pair of variables is somehow fixed by this mechanism. And the process continues until the rest signatures in the whole instance are in . Hence, this more general support requirement, can force a signature in an instance to work exactly like some signature. The analysis of the dual case is similar.
3 New notations and our results
There are three parts of results in this paper, which are introduced in Subsection 3.1, 3.2, 3.3 respectively. In Subsection 3.4, we introduce two strange signatures, which serve as a motivation for some of our study. Finally in Subsection 3.5 we introduce the relations between these results.
3.1 A set of binary or quaternary signatures
The first part of our results generalizes six-vertex model to problems defined by a set of EO signatures of arity no more than 4. We define
can be seen as with the type requirement. Similarly, we define
The detailed version of Theorem 5 is as follows.
Theorem 20.
Suppose is a set of EO signatures with arity less than or equal to 4. Then is #P-hard unless one of the following conditions holds:
a. ;
b. ;
c. ;
d. ,
in which cases the problem can be computed in polynomial time.
We summarize current notations as the following tree. A specific example of the type requirement is also presented. When a set of signatures can meet all requirements on a path from the root to the four nodes at the bottom, the corresponding problem is tractable; otherwise the problem is #P-hard.
3.1.1 Insights from tractable cases
This dichotomy exhibits two dual support requirements represented by 444Each signature’s support must be a subset of either or . and . Tractability requires satisfying either support requirement along with either an -type or -type requirement.
A key distinction between Theorems 19 and 20 lies in the emergence of in the latter. It can be verified that:
-
For signatures, -type and -type requirements produce the first two tractable classes in Theorem 19;
-
signatures under -type requirements automatically satisfy -type conditions, explaining the third tractable case;
-
The dual case similarly generates the fourth tractable case.
Theorem 20 demonstrates the crucial divergence between -type and -type requirements when handling mixed signature sets.
3.1.2 Proof outline of hardness result
We say two signature sets mix (in ) if there exists such that and . We first prove 3 no-mixing lemmas, mainly through signature classification on support size and gadget construction, showing the following cases are #P-hard:
-
1.
and mix;
-
2.
and mix;
-
3.
and mix;
-
4.
and mix.
Suppose is a set of binary and quaternary EO signatures. Suppose the problem is not #P-hard. By Theorem 19, we can assume that .
As and do not mix, either or . Due to the dual property, it is sufficient to focus on the former case.
As and do not mix, either or . The former case is exactly tractable case a in Theorem 20. We focus on the latter case.
As and do not mix, either or . The former case is exactly tractable case b in Theorem 20, and the latter case is subsumed by tractable case a.
3.2 Pure signatures
In this section we focus on pure signatures, which can be seen as a generalization of the quaternary signatures in and .
Definition 21.
An EO signature is pure-up, if . A signature set is pure-up, if each signature in it is pure-up. Similarly, An EO signature is pure-down, if . A signature set is pure-down, if each signature in it is pure-down.
These two categories are collectively termed pure signatures.
We summarize current notations as the following tree.
In the following, we present the dichotomy of pure signatures and the corresponding definitions. It is worth noticing that in this section, pure-up signatures and pure-down signatures never mix in .
Definition 22.
Suppose is an arity EO signature and . is the restriction of to , which means when , , otherwise .
If for any pairing of Var, , then we say that is .
Similarly, if for any pairing of Var, , then is .
Theorem 23 (The dichotomy for pure-up EO signatures).
Suppose is a set of pure-up EO signatures. Then is #P-hard unless all signatures in are or all of them are , in which cases the problem can be computed in polynomial time.
3.2.1 Insights from tractable cases
We primarily analyze pure-up signatures, noting that pure-down signatures admit dual analysis through symmetric arguments. Key properties of pure-up signatures reveal that each either belongs to , or has at least one variable fixed to 1. These properties enable application of the active receiving-sending mechanism. Pure signatures thus induce a generalized support requirement with two dual cases (intersecting at the self-dual requirement), where tractability emerges through additional type or type requirements.
3.2.2 Proof outline of hardness result
For a pure signature of arity , it can be proved that for an arbitrary pairing of , where is an signature of arity . Such can be realized by adding self-loops, and (or ) if and only if (or ).
3.3 Rebalancing signatures
In this section, we define a property named for EO signatures.
Definition 24 (Rebalancing).
An EO signature of arity , is called 0-rebalancing(1-rebalancing respectively), when the following recursive conditions are met.
-
: No restriction.
-
: For any variable in , there exists a variable different from , such that for any , if ( respectively) then . Besides, the arity signature is 0-rebalancing( is 1-rebalancing respectively).
For completeness we view all nontrivial signatures of arity 0, which is a non-zero constant, as 0-rebalancing(1-rebalancing) signatures. For the case, is said to be the first level mapping of .
Tractability can also be obtained based on 0-rebalancing/1-rebalancing property.
Theorem 25.
If is composed of 0-rebalancing(1-rebalancing) signatures, or is composed of 0-rebalancing(1-rebalancing) signatures, then is polynomial-time computable.
Remark 26.
It can be verified that every signature satisfies both 0-rebalancing and 1-rebalancing conditions. All pure-up signatures are 0-rebalancing due to the following arguments. When a pure-up signature satisfies , it necessarily contains a factor. This factor induces a first-level mapping where all variables except map to , while can be any variable other than itself. This mapping process can be recursively applied until the signature is transformed into an signature, which remains 0-rebalancing. Through dual reasoning, all pure-down signatures satisfy 1-rebalancing.
3.3.1 Insights from the algorithm
This section extends the receiving-sending mechanism to rebalancing signatures. While the active receiving-sending mechanism for pure signatures requires initial () triggers, rebalancing signatures may lack such initial conditions. Nevertheless, by assuming fixed values for certain variables, the mechanism still functions through what we term the passive receiving-sending mechanism. Building on this modified mechanism, we develop a polynomial-time algorithm for problems defined by 0-rebalancing or 1-rebalancing signatures meeting -type or -type requirements.
Definition 24 for specifies two necessary conditions: the existence of mapping (first-level condition) and the recursive condition. Crucially, the first-level condition remains unconditional - the relationship between and persists even when other variables are fixed. This property enables identification of loops (rather than /-initiated paths) in the passive mechanism, while the recursive condition ensures the mechanism’s iterative applicability.
3.4 Two strange signatures
In this subsection we present the definition of and , which are considered as two important examples in our study. Some of our results are motivated by these signatures. We first introduce some notations to describe signatures with large arity and a sparse support.
For matrices and , we use to denote the matrix satisfying
(1) |
Informally speaking, is a concatenation of . We use to denote the matrix , which is a concatenation of copies of matrix . We also define the following matrices.
For a signature of arity , we use the support matrix to describe its support. A string is a support string of if and only if equals a row in . has the support matrix , has the support matrix and both of them are 0-1 weighted. Though the supports of them are sparse, they are not able to be captured by a number of existing algorithms and hardness results.
3.5 Relations between results
The first two parts collectively establish complete dichotomies for problems, incorporating both tractability and hardness results: the first for binary and quaternary signature sets, the second for pure-up/pure-down signature sets. The hardness results from the first part form the foundational basis for the hardness classification in complex-weighted , while those from the second part are equally pivotal for establishing the full dichotomy.
The third part focuses on defining the rebalancing property and presenting a polynomial-time algorithm for 0-rebalancing/1-rebalancing signatures with type requirements. Notably, this algorithm subsumes both previous algorithms through its innovative use of support requirements to emulate the property’s effects. The case of (defined in Section 3.4) exemplifies this generalization - although not a pure signature, its satisfaction of 0-rebalancing demonstrates our algorithm’s strictly broader applicability compared to the pure signatures’ algorithm.
We observe that although the results in [43] are restricted to 0-1 weighted problems, they nevertheless capture essential support requirements for signatures. Specifically, the pure property inherently implies the -affine property, and their chain reaction algorithm implements what we term the active receiving-sending mechanism.
The complex-weighted dichotomy in [40] adopts the notation for pure-up signatures and for pure-down signatures, where our Theorem 23 directly resolves “Case 3a” and “Case 4a”. Notably, the signatures and introduced in our work, whose non-trivial nature is evident from our analysis, provide concrete examples for “Case 3c”.
4 Conclusion
In this article, we prove two dichotomies for : one with restricted to binary and quaternary signatures, and another with restricted to pure signatures. We also present an algorithm for rebalancing signature sets satisfying or . A more detailed characterization of pure signatures and rebalancing signatures would be valuable, similar to what has been achieved for -affine kernels in [43]. Indeed, pure signatures clearly exhibit close connections to -affine signatures.
The pursuit of a complete dichotomy for remains an important research direction. Notably, the signature defined in Section 3.4 is neither pure nor rebalancing. The complexity of remains unresolved and presents significant interest. While some progress has been made, substantial challenges persist in addressing this problem.
Recent work [40] has established an versus #P dichotomy for complex-valued , which includes an interesting polynomial-time algorithm with a specific NP oracle for solving . This development has also prompted renewed investigation of Boolean constraint satisfaction problems [32]. Nevertheless, the polynomial-time computability of remains an open question, and the most general known polynomial-time algorithm for is still our rebalancing signature algorithm presented in this work.
References
- [1] Miriam Backens. A new Holant dichotomy inspired by quantum computation. arXiv preprint arXiv:1702.00767, 2017. arXiv:1702.00767.
- [2] Miriam Backens. A full dichotomy for Holantc, inspired by quantum computation. SIAM Journal on Computing, 50(6):1739–1799, 2021.
- [3] David M Bressoud. Proofs and confirmations: the story of the alternating-sign matrix conjecture. Cambridge University Press, 1999.
- [4] Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, and David Richerby. The complexity of weighted and unweighted #CSP. Journal of Computer and System Sciences, 78(2):681–688, 2012. doi:10.1016/j.jcss.2011.12.002.
- [5] Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, and David Richerby. The complexity of weighted Boolean #CSP with mixed signs. Theoretical Computer Science, 410(38-40):3949–3961, 2009. doi:10.1016/j.tcs.2009.06.003.
- [6] Andrei Bulatov and Martin Grohe. The complexity of partition functions. Theoretical Computer Science, 348(2-3):148–186, 2005. doi:10.1016/j.tcs.2005.09.011.
- [7] Andrei A Bulatov. The complexity of the counting constraint satisfaction problem. Journal of the ACM (JACM), 60(5):1–41, 2013. doi:10.1145/2528400.
- [8] 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.
- [9] Jin-Yi Cai and Xi Chen. Complexity dichotomies for counting problems: Volume 1, Boolean domain. Cambridge University Press, 2017.
- [10] Jin-Yi Cai and Xi Chen. Complexity of counting CSP with complex weights. Journal of the ACM (JACM), 64(3):1–39, 2017. doi:10.1145/2822891.
- [11] Jin-Yi Cai and Xi Chen. A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. computational complexity, 28:345–408, 2019. doi:10.1007/s00037-019-00184-5.
- [12] Jin-Yi Cai, Xi Chen, and Pinyan Lu. Graph homomorphisms with complex values: A dichotomy theorem. SIAM Journal on Computing, 42(3):924–1029, 2013. doi:10.1137/110840194.
- [13] Jin-Yi Cai, Xi Chen, and Pinyan Lu. Nonnegative weighted #CSP: an effective complexity dichotomy. SIAM Journal on Computing, 45(6):2177–2198, 2016. doi:10.1137/15M1032314.
- [14] Jin-Yi Cai and Vinay Choudhary. Valiant’s Holant theorem and matchgate tensors. Theoretical Computer Science, 384(1):22–32, 2007. doi:10.1016/j.tcs.2007.05.015.
- [15] Jin-Yi Cai and Zhiguo Fu. Complexity classification of the eight-vertex model. Information and Computation, 293:105064, 2023. doi:10.1016/j.ic.2023.105064.
- [16] Jin-Yi Cai, Zhiguo Fu, and Shuai Shao. Beyond #CSP: A dichotomy for counting weighted Eulerian orientations with ARS. Information and Computation, 275:104589, 2020. doi:10.1016/j.ic.2020.104589.
- [17] Jin-Yi Cai, Zhiguo Fu, and Shuai Shao. From Holant to quantum entanglement and back. arXiv preprint arXiv:2004.05706, 2020. arXiv:2004.05706.
- [18] Jin-Yi Cai, Zhiguo Fu, and Shuai Shao. New planar P-time computable six-vertex models and a complete complexity classification. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1535–1547. SIAM, 2021. doi:10.1137/1.9781611976465.93.
- [19] Jin-Yi Cai, Zhiguo Fu, and Mingji Xia. Complexity classification of the six-vertex model. Information and Computation, 259:130–141, 2018. doi:10.1016/j.ic.2018.01.003.
- [20] Jin-Yi Cai and Artem Govorov. Perfect matchings, rank of connection tensors and graph homomorphisms. Combinatorics, Probability and Computing, 31(2):268–303, 2022. doi:10.1017/S0963548321000286.
- [21] Jin-Yi Cai, Heng Guo, and Tyson Williams. A complete dichotomy rises from the capture of vanishing signatures. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 635–644, 2013.
- [22] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Holant problems and counting CSP. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 715–724, 2009. doi:10.1145/1536414.1536511.
- [23] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Computational complexity of Holant problems. SIAM Journal on Computing, 40(4):1101–1132, 2011. doi:10.1137/100814585.
- [24] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Dichotomy for Holant* problems of Boolean domain. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1714–1728. SIAM, 2011. doi:10.1137/1.9781611973082.132.
- [25] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. The complexity of complex weighted Boolean #CSP. Journal of Computer and System Sciences, 80(1):217–236, 2014. doi:10.1016/j.jcss.2013.07.003.
- [26] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Dichotomy for real problems. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1802–1821. SIAM, 2018. doi:10.1137/1.9781611975031.118.
- [27] Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. The complexity of weighted Boolean #CSP. SIAM Journal on Computing, 38(5):1970–1986, 2009. doi:10.1137/070690201.
- [28] Martin Dyer, Leslie Ann Goldberg, and Mike Paterson. On counting homomorphisms to directed acyclic graphs. Journal of the ACM (JACM), 54(6):27–es, 2007.
- [29] Martin Dyer and Catherine Greenhill. The complexity of counting graph homomorphisms. Random Structures & Algorithms, 17(3-4):260–289, 2000. doi:10.1002/1098-2418(200010/12)17:3/4\%3C260::AID-RSA5\%3E3.0.CO;2-W.
- [30] Martin Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem. SIAM Journal on Computing, 42(3):1245–1274, 2013. doi:10.1137/100811258.
- [31] Martin E Dyer and David M Richerby. On the complexity of #CSP. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 725–734, 2010. doi:10.1145/1806689.1806789.
- [32] Tomás Feder and Daniel Ford. Classification of bipartite Boolean constraint satisfaction through delta-matroid intersection. SIAM Journal on Discrete Mathematics, 20(2):372–394, 2006. doi:10.1137/S0895480104445009.
- [33] Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley. A complexity dichotomy for partition functions with mixed signs. SIAM Journal on Computing, 39(7):3336–3402, 2010. doi:10.1137/090757496.
- [34] Heng Guo, Sangxia Huang, Pinyan Lu, and Mingji Xia. The complexity of weighted Boolean #CSP modulo k. In STACS 2011, pages 249–260. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2011. doi:10.4230/LIPIcs.STACS.2011.249.
- [35] Pavol Hell and Jaroslav Nešetřil. On the complexity of H-coloring. Journal of Combinatorial Theory, Series B, 48(1):92–110, 1990. doi:10.1016/0095-8956(90)90132-J.
- [36] Michel Las Vergnas. On the evaluation at (3, 3) of the Tutte polynomial of a graph. Journal of Combinatorial Theory, Series B, 45(3):367–372, 1988. doi:10.1016/0095-8956(88)90079-2.
- [37] Jiabao Lin and Hanpin Wang. The complexity of Boolean Holant problems with nonnegative weights. SIAM Journal on Computing, 47(3):798–828, 2018. doi:10.1137/17M113304X.
- [38] László Lovász. Operations with structures. Acta Mathematica Hungarica, 18(3-4):321–328, 1967.
- [39] Boning Meng, Juqiu Wang, and Mingji Xia. P-time algorithms for typical #EO problems. arXiv preprint arXiv:2410.11557, 2024. doi:10.48550/arXiv.2410.11557.
- [40] Boning Meng, Juqiu Wang, and Mingji Xia. The versus #P dichotomy for #EO, 2025. doi:10.48550/arXiv.2502.02012.
- [41] Linus Pauling. The structure and entropy of ice and of other crystals with some randomness of atomic arrangement. Journal of the American Chemical Society, 57(12):2680–2684, 1935.
- [42] Shuai Shao and Jin-Yi Cai. A dichotomy for real Boolean Holant problems. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1091–1102. IEEE, 2020. doi:10.1109/FOCS46700.2020.00105.
- [43] Shuai Shao and Zhuxiao Tang. Eulerian orientations and Hadamard codes: A novel connection via counting. arXiv preprint arXiv:2411.02612, 2024. doi:10.48550/arXiv.2411.02612.
- [44] Leslie G Valiant. Holographic algorithms. SIAM Journal on Computing, 37(5):1565–1594, 2008. doi:10.1137/070682575.