Eulerian Orientations and Hadamard Codes:
A Novel Connection via Counting

The notion of Eulerian orientations arises from the historically notable Seven Bridges of Königsberg problem, whose solution by Euler in 1736 [14] is considered to be the first result of graph theory. Given an undirected graph $G$, an Eulerian orientation of $G$ is an assignment of a direction to each edge of $G$ such that at each vertex $v$, the number of incoming edges is equal to the number of outgoing edges. A connected graph has an Eulerian orientation, called an Eulerian graph if and only if every vertex has even degree. This is the well-known Euler’s theorem, whose first complete proof was given back in the 1800s [3]. In terms of computational complexity, Euler’s theorem implies that the decision problem of Eulerian orientations of a graph is polynomial-time solvable (tractable). While for the counting problem, Mihail and Winkler showed that counting the number of Eulerian orientations of an undirected graph is #P-complete in 1996 [18], more than one hundred years later after Euler’s theorem. However, the counting problem becomes tractable when certain particular restrictions are imposed on edges. An intriguing example of such tractable problems comes from computing the partition function of the six-vertex model [19, 22, 20], one of the most intensively studied models in statistical physics. In this example, the graphs are 4 regular graphs and on each vertex exactly one edge incident to it is restricted to take the direction coming into the vertex. Then counting the number of Eulerian orientations obeying restrictions on these edges is proved to be tractable [7].

In this paper, we further study the counting restricted Eulerian orientations (#EO) problem, defined by constraint functions placed at each vertex that represent restrictions on edges incident to the vertex. We consider for which class of constraint functions, the #EO problem is tractable. Before we formally define the problem and describe our results, we first take a detour to another classical notion in coding theory, the Hadamard code. The Hadamard code is an error-correcting code used for error detection and correction when transmitting messages over very noisy or unreliable channels. Because of its plentiful mathematical properties, the Hadamard code is not only used in coding and communication, but also intensely studied in various areas of mathematics and theoretical computer science. However, it is not known how the Hadamard code can be related to Eulerian orientations, and particularly, how it can be used to carve out tractable classes for the #EO problem. Quite surprisingly, in this paper, we establish a novel connection between these two well-studied mathematical notions. We present new tractable classes for the #EO problem and a corresponding algorithm based on a chain reaction. These classes are defined inductively and the base levels of them, defined as kernels are characterized perfectly by the Hadamard code (or more precisely, the balanced Hadamard code).

Now we formally define the #EO problem. A 0-1 valued constraint function (or a signature) $f$ of arity $n$ is a map ${\mathbb{Z}}_2^n\to \{0,1\}$. The support of $f$ is $𝒮(f)=\{\alpha \in {\mathbb{Z}}_2^n|f(\alpha )=1\}$. A signature $f$ of arity $2n$ is an Eulerian orientation (EO) signature if for every $\alpha \in 𝒮(f)$, wt$(\alpha )=n$. The problem #EO($ℱ$) specified by a set $ℱ$ of EO signatures is defined as follows. The input is a graph $G$ where each vertex $v$ of $G$ is associated with some function $f_v$ from $ℱ$. The incident edges to $v$ are totally ordered and correspond to input variables to $f_v$. Each edge has two ends, and an orientation of the edge is denoted by assigning 0 to the head and 1 to the tail. Thus, locally at every vertex $v$, a $0$ represents an incoming edge and a $1$ represents an outgoing edge. An Eulerian orientation corresponds to an assignment to each edge ($01$ or $10$) where the numbers of 0’s and 1’s at each $v$ are equal. Then, the local constraint function $f_v$ takes value $1$ if the restriction imposed by $f_v$ are satisfied by the local assignment on edges incident to $v$. Otherwise, $f_v=0$. Since every $f_v$ is an EO signature, it takes value $1$ only if the numbers of input 0’s and 1’s are equal. Thus, only Eulerian orientations can contribute value $1$. An Eulerian orientation contributes value $1$ if $f_v=1$ for every vertex $v$. The #EO problem outputs the number of Eulerian orientations contributing value $1$.

The #EO problem has an intrinsic significance in counting problems. In [5], the framework of #EO problems is formally introduced and is showed to be expressive enough to encompass all Boolean counting constraint satisfaction problems (#CSP) [12, 13, 4, 10] with arbitrary constraint functions that are not necessarily supported on half weighted inputs, although the #EO problem itself requires all constraint functions to be supported on half weighted inputs. Also, the #EO problem encompasses many natural problems from statistical physics and combinatorics, such as the partition function of the six-vertex model and the evaluation of the Tutte polynomial at the point $(3,3)$ [15]. Cai, Fu and Xia proved a complexity classification of the partition function of the six-vertex model on general 4-regular graphs [7].

Besides these interesting concrete problems expressible as #EO problems, the study of the #EO framework plays a crucial role in a broader picture, the complexity classification program for a much more expressive counting framework, the Holant problem. Significant progress has been made in the complexity classification of Holant problems [9, 8, 1, 11, 2, 16, 6], and a full complexity dichotomy for all real-valued Holant problems is achieved [21]. This dichotomy is crucially based on a complexity dichotomy for the #EO problem [5] with complex-valued signatures assuming a physical symmetry called arrow reversal symmetry (ARS) since under a suitable holographic transformation, the ARS property corresponds to precisely real-valued signatures. In this paper, we consider the 0-1 valued #EO problem without assuming ARS, which may serve as a building block for the ultimate classification for all complex-valued Holant problems. For this problem, we give new tractable classes that are not covered by all the previously known tractable classes for Holant problems.

We use $a(f)$ to denote the arity of $f$, and $A(f)=\{1,2,\mathrm{\dots },a(f)\}$ to denote the indices of variables of $f$. We use ${\delta }_1$ and ${\delta }_0$ to denote the unary signatures where $𝒮({\delta }_1)=\{1\}$ and $𝒮({\delta }_0)=\{0\}$ respectively. Pinning the $i$-th variable of $f$ to $0$ gives the signature $f(x_1,\mathrm{\dots },x_{i-1},0,x_{i+1},\mathrm{\dots },x_n)$ of arity $n-1$, denoted by $f_i^0$. Similarly, we define $f_i^1$. Let $f$ and $g$ be two signatures of support size $n$ and $m$ respectively. Suppose $𝒮(f)=\{{\alpha }_1,{\alpha }_2,\mathrm{\dots },{\alpha }_n\}$ and $𝒮(g)=\{{\beta }_1,{\beta }_2,\mathrm{\dots },{\beta }_m\}$. Then the tensor product $f\otimes g$ of $f$ and $g$ is the signature where $𝒮(f\otimes g)=\{{\alpha }_i{\beta }_j|1\le i\le n,1\le j\le m\}$. Note that when we take a tensor product of the functions, the variables need not be in the same order of the product. A nonzero signature $g$ is a factor of $f$, denoted by $g\mid f$, if there is a signature $h$ such that $f=g\otimes h$ or there is a constant $\lambda$ such that $f=\lambda \cdot g$. Otherwise, $g$ is not factor of $f$, denoted by $g\nmid f$. In the following, we first state the definition of affine signatures, which are known to be tractable for the #EO problem. Then we give the new tractable classes.

For example, the 4-ary signature $f$ in Example 2 is an ${\delta }_1$-affine signature. Note that ${𝒟}_1$ (or ${𝒟}_0$) does not encompass $𝒜$, since an affine signature may not have a ${\delta }_1$ (or ${\delta }_0$) factor. Thus, our tractable classes are $𝒜\cup {𝒟}_1$ and $𝒜\cup {𝒟}_0$, rather than ${𝒟}_1$ and ${𝒟}_0$.

The tractability result is established via a chain reaction algorithm, in which the presence of a ${\delta }_1$ or ${\delta }_0$ signature plays a role similar to a neutron in a nuclear chain reaction which initializes the reaction and generates a new neutron (a ${\delta }_1$ or ${\delta }_0$ signature respectively) by propagation which makes the chain reaction continue. Eventually, the chain reaction terminates when a stable state (a tractable instance of $\mathrm{\#}\mathrm{EO}(𝒜)$) is reached.

Although the reaction algorithm works for ${\delta }_1$-affine signatures or ${\delta }_0$-affine signatures alone, it does not work when both of them appear. This is because when both ${\delta }_1$-affine signatures and ${\delta }_0$-affine signatures appear, by connecting ${\delta }_1$ and ${\delta }_0$ using $\ne$, both of them are killed by each other and no new ${\delta }_1$ or ${\delta }_0$ are generated. Thus, the chain reaction is unsustainable. This is somewhat similar to the phenomenon of electron–positron annihilation in nuclear physics. In fact, we can show that the #EO problem is #P-hard when they both appear.

Since the classes ${𝒟}_1$ and ${𝒟}_0$ are defined inductively, it is not an easy task to get explicit expressions for them in a form similar to other known tractable classes for counting problems such as affine signatures. Note that the tractability of ${𝒟}_1$ or ${𝒟}_0$ is obtained by eventually reducing the problem into a problem where all signatures are affine signatures. Thus, we focus on ${\delta }_1$-affine (or ${\delta }_0$-affine) signatures from which by pinning an arbitrary variable to $0$ (or $1$ respectively), we always get an affine signature. In other words, these ${\delta }_1$-affine (or ${\delta }_0$-affine) signatures are at the first level of the inductive hierarchy. We define them as kernels.

A main technical contribution of the paper is a complete characterization of ${\delta }_1$-affine and ${\delta }_0$-affine kernels using the Hadamard code. The Hadamard code refers to the code based on Sylvester’s construction of Hadamard matrices. A Hadamard matrix $H_n$ is a square matrix of size $n$ such that all its entries are in $\{1,-1\}$ and $H_n{H}_n^T=n{I}_n$. Sylvester’s construction gives Hadamard matrices $H_{2^k}$ of size $2^k$ for all $k\ge 0$, where and $H_{2^0}=1$. The Hadamard code ${\mathscr{H}}_{2^k}^1$ derived from the Hadamard matrices $H_{2^k}$ by Sylvester’s construction is a code over the binary alphabet $\{0,1\}$ of which the $2^k$ codewords are rows of $H_{2^k}$ where the entry $1$ of $H_{2^k}$ is mapped to $1$ and the entry $-1$ is mapped to $0$. Symmetrically, we can also get the Hadamard code ${\mathscr{H}}_{2^k}^0$ by mapping the $1$ entry to $0$ and $-1$ to $1$. Note that ${\mathscr{H}}_{2^k}^1$ contains an all-$1$ codeword and ${\mathscr{H}}_{2^k}^0$ contains an all-$0$ codeword. We call the former the 1-Hadamard code and the latter the 0-Hadamard code. In standard coding theory notation for block codes, ${\mathscr{H}}_{2^k}^1$ and ${\mathscr{H}}_{2^k}^0$ are $[2^k,k,2^{k-1}]$-code, which is a binary linear code having block length $2^k$, message length $k$, and minimum Hamming distance $2^k/2$. By removing the all-$1$ codeword from ${\mathscr{H}}_{2^k}^1$, we get a balanced code, i.e., each codeword has Hamming weight $2^{k-1}$, half of its block length. We call it the balanced 1-Hadamard code, denoted by ${\mathscr{H}}_{2^k}^{1\mathrm{b}}$. Symmetrically, we can get the balanced 0-Hadamard code, denoted by ${\mathscr{H}}_{2^k}^{0\mathrm{b}}$. A binary code ${𝒞}_n$ of block length $n$ can be viewed equivalently as a 0-1 valued constraint function $f$ of arity $n$ by taking the support $𝒮(f)=\{\alpha \in {\mathbb{Z}}_2^n|f(\alpha )\ne 0\}$ to be ${𝒞}_n$. An $m$-multiple of the code ${𝒞}_n$ is a code of block length $nm$, each codeword of which is obtained from a codeword $\alpha$ of ${𝒞}_n$ by taking the concatenation of $m$ copies of $\alpha$.

Due to the existence of newly discovered non-trivial tractable classes corresponding to the Hadamard code in the #EO problem without assuming ARS, the complexity classification for the complex-valued Holant problem is much more challenging. It’s hard to imagine how many more tractable classes with remarkable properties are yet to be discovered. The results in this paper are a tiny step towards an ambitious goal. Very recently, independent of this work, Meng, Wang and Xia discover new larger tractable classes for the #EO problem [17]. In addition, we note that the presented result in this paper is not the first time that a tractable class for counting problems is found to be related to coding theory. Even in the classification of real-valued Holant problems, a tractable family called local affine [11] was already discovered using the well-known Hamming code. Are there other interesting tractable classes for counting problems that can be carved out with the help of coding theory? In the other direction, it is also worth pursuing whether these new tractability results for counting problems can be applied back to coding theory? We leave the questions in both directions for further study.

The paper is organized as follows. In Section 2, we give some definitions and notations. In Section 3, we give a chain reaction algorithm which establishes the tractability result (Theorem 5) for ${\delta }_1$-affine and ${\delta }_0$-affine signatures. In Section 4, we prove the characterization theorem (Theorem 8) for ${\delta }_1$-affine and ${\delta }_0$-affine kernels. In Section 5, we prove the hardness result Theorem 6. In fact, the proof of the hardness result highly depends on the characterization of ${\delta }_1$-affine and ${\delta }_0$-affine kernels. Omitted proofs can be founded in the full version.

A 0-1 valued signature is determined by its support $𝒮(f)$. In the paper, we use $f$ and $𝒮(f)$ interchangeably. We can also view $𝒮(f)$ as a binary code of block length $a(f)$ where each $\alpha \in 𝒮(f)$ is a codeword. We say $𝒮(f)$ (or equivalently $f$) has a constant Hamming weight $\mathrm{\ell }$ if $\mathrm{wt}(\alpha )=\mathrm{\ell }$ for every $\alpha \in 𝒮(f)$. For simplicity, we say $f$ is $\mathrm{\ell }$-weighted or constant-weighted in general. The following fact can be easily checked. Any factor of a constant-weighted signature is still constant-weighted. If a vertex $v$ in a graph is labeled by a signature $f=g\otimes h$, we can replace the vertex $v$ by two vertices $v_1$ and $v_2$ and label $v_1$ with the factor $g$ and $v_2$ with $h$, respectively. The incident edges of $v$ become incident edges of $v_1$ and $v_2$ respectively according to the partition of variables of $f$ in the tensor product of $g$ and $h$. This does not affect the evaluation of the instance. We represent $f$ or $𝒮(f)$ by a matrix which lists all vectors in $𝒮(f)$ by its rows. All matrices that are equal up to a permutation of rows and columns represent the same signature. Normally, the columns indexing variables are ordered from the smallest index to the largest, and are omitted for convenience when the context is clear. For example, the signature $f=\{1100,1010,1001\}$ can be written as .

For $i\in A(f)$, we use ${\mathrm{\#}}_i^0(f)$ and ${\mathrm{\#}}_i^1(f)$ to denote the number of $0$s and $1$s respectively in the $i$-th column of $𝒮(f)$. The complement of a signature $f$, denoted by $\overline{f}$ is the signature with the support $𝒮(\overline{f})=\{\alpha \in {\mathbb{Z}}_2^n|\overline{\alpha }\in 𝒮(f)\}$ where $\overline{\alpha }$ is the standard complement of $\alpha$, i.e., $\overline{\alpha }\oplus \alpha ={\overrightarrow{0}}^n$. Let $\widehat{f}(x_1,x_2,\mathrm{\dots },x_n)=x_1{x}_2\mathrm{\dots }{x}_n\oplus f(x_1,x_2,\mathrm{\dots },x_n)$. Then, $𝒮(\widehat{f})=\{{\overrightarrow{1}}^n\}\mathrm{\Delta }𝒮(f)$. Similarly, let $\check{f}(x_1,x_2,\mathrm{\dots },x_n)=(1\oplus x_1)(1\oplus x_2)\mathrm{\dots }(1\oplus x_n)\oplus f(x_1,x_2,\mathrm{\dots },x_n)$. Then $𝒮(\check{f})=\{{\overrightarrow{0}}^n\}\mathrm{\Delta }𝒮(f)$. We use $\ne$ to denote the binary disequality signature $\{01,10\}$. Connecting ${\delta }_1$ with the $i$-th variable of $f$ using $\ne$ is equivalent to pinning the $i$-th variable of $f$ to $0$, which gives the signature $f_i^0$. Extracting the $i$-th variable of $f$ to $0$ gives the signature $(x_i\oplus 1)f(x_1,x_2,\mathrm{\dots },x_n)$ of arity $n$, denoted by $f^{x_i=0}$. Clearly $f^{x_i=0}={\delta }_0\otimes f_i^0$. Similarly we define $f_i^1$ and $f^{x_i=1}$. We use $f_{ij}^{ab}$ to denote the signature ${(f_i^a)}_j^b={(f_j^b)}_i^a$ for distinct $i,j\in A(f)$ and any $a,b\in {\mathbb{Z}}_2$. The signature $f^{x_i\ne x_j}$ is defined to be $f_{ij}^{01}+f_{ij}^{10}$ which can be obtained by connecting the $i$-th and $j$-th variables of $f$ using $\ne$. For a signature $f$, we define its $m$-multiple, denoted by $f_{\times m}$ to be the signature $𝒮(f_{\times m})=\{{\overrightarrow{\alpha }}^m\mid \alpha \in 𝒮(f)\}$ where ${\overrightarrow{\alpha }}^m\in {\mathbb{Z}}_2^{nm}$ is obtained from $\alpha$ by taking the concatenation of $m$ copies of $\alpha$.

Now we give some basic properties of affine signatures. Equivalently, $f$ is affine if and only if it satisfies the property that for any $\alpha ,\beta ,\gamma \in 𝒮(f)$, $\alpha \oplus \beta \oplus \gamma \in 𝒮(f)$. One can also check that affine signatures are closed under pinning, extracting, tensor product and factoring. Also, $f\in 𝒜$ if and only if $f_{\times m}\in 𝒜$ for any $m\in {\mathbb{Z}}_{+}$.

In the section, we show $\mathrm{\#}$EO$({𝒟}_1\cup 𝒜)$ and $\mathrm{\#}$EO$({𝒟}_0\cup 𝒜)$ are tractable by giving a chain reaction algorithm. We only consider $\mathrm{\#}$EO$({𝒟}_1\cup 𝒜)$, since the other case is symmetric. Given an instance $\mathrm{\Omega }$ of $\mathrm{\#}$EO$({𝒟}_1\cup 𝒜)$, we may assume that there is at least one vertex labelled by a ${\delta }_1$-affine signature $f$. Otherwise, all signatures in the instance are affine. Such an instance of $\mathrm{\#}$EO$(𝒜)$ is tractable.

Since $f$ is ${\delta }_1$-affine, consider a factor ${\delta }_1$ of $f$. This ${\delta }_1$ is connected to another variable of some signature (which may be $f$ itself) using ${\ne }_2$. Then, the connected variable is pinned to $0$. A key property that ensures our algorithm work is that after connecting ${\delta }_1$ to another variable no matter whether it is a variable of $f$ itself, an affine signature, or another ${\delta }_1$-affine signature, either the resulting signature is affine, or we can realize another ${\delta }_1$. In the later case, we call it a propagation step. After a propagation step, the new realized ${\delta }_1$ can be used to pin another variable to $0$. Thus, we get a chain reaction, and it terminates when an instance of $\mathrm{\#}$EO$(𝒜)$ is reached. Note that, after each propagation step, the number of edges (total variables) in the instance is reduced by $2$. Thus, the chain reaction terminates after at most $|E|/2$ many steps where $E$ is the edge set of the underlying graph in $\mathrm{\Omega }$.

In this section, we prove the main characterization theorem for ${\delta }_1$-affine and ${\delta }_0$-affine kernels using the Hadamard code. We first give an equivalent definition for the ${\delta }_1$-affine kernel. Note that in Definition 7 we require $h\notin 𝒜$, while in the following lemma we require ${\delta }_0\nmid h$.

Note that the signature $f_2$ in Example 2 is a ${\delta }_1$-affine kernel. Trivially, any EO signature of support size 3 with at least one ${\delta }_1$ factor and no ${\delta }_0$ factor is a ${\delta }_1$-affine kernel, since any signature obtained from it by pinning a variable to $0$ has a support of size $1$ or $2$, which is affine. We say $f\in K({𝒟}_1)$ (or $K({𝒟}_0)$) is a trivial kernel if $|𝒮(f)|=3$. Below, we prove the characterization theorem for non-trivial ${\delta }_1$-affine and ${\delta }_0$-affine kernels, which is essentially equivalent to Theorem 8.

We give a proof outline for this theorem. First, we prove ${\delta }_1$-affine kernels admit certain arities and support sizes by carefully counting the number of 0s and 1s in each column of their supports. More specifically, we prove a non-trivial ${\delta }_1$-affine kernel $f$ must have support size $2^k-1$ and arity $m{2}^k$, for some $m,k\in Z_{+},k\ge 3$ (Lemma 17). Then, we define basic ${\delta }_1$-affine kernels (Definition 18) of support size $2^k-1$ and arity $2^k$. We show every non-trivial ${\delta }_1$-affine kernel is a multiple of some non-trivial basic kernel (Lemma 19). Finally, we characterize the basic ${\delta }_1$-affine kernel by the balanced 1-Hadamard code ${\mathscr{H}}_{2^k}^{1b}$. We define a special affine signature called butterfly (Definition 20), serving as a bridge connecting basic kernels and balanced Hadamard codes. We show ${\mathscr{H}}_{2^k}^1$ (or ${\mathscr{H}}_{2^k}^0$) is just a half of butterfly (Lemma 24). We also define left and right wings of butterfly (Definition 21) by removing the all-0 (or all-1) row from a half of butterfly. Notice ${\mathscr{H}}_{2^k}^{0b}$ (or ${\mathscr{H}}_{2^k}^{1b}$) is obtained by removing the all-0 (or all-1) codeword from ${\mathscr{H}}_{2^k}^1$. Thus, wings of butterfly coincide with ${\mathscr{H}}_{2^k}^{0b}$ and ${\mathscr{H}}_{2^k}^{1b}$ (Lemma 24). Finally, we prove basic kernels are precisely wings of butterfly (Lemma 26 and Lemma 28). Therefore, basic kernels, balanced Hadamard codes and wings of butterfly are precisely the same things.

For example, the basic ${\delta }_1$-affine kernel of order 1 is $f_1={\delta }_1\otimes {\delta }_0$ and the basic ${\delta }_1$-affine kernel of order 2 is $f_2={\delta }_1\otimes \{(001),(010),(100)\}$.

Recall that the binary disequality signature $(\ne )$ is $\{10,01\}$. The symbol ”${\le }_T$” stands for Turing reduction.

First, we show that ${\delta }_1\otimes {\delta }_0$ is always realizable from an EO signature not satisfying ARS.

With the help of ${\delta }_1\otimes {\delta }_0$, we have the following reduction.

Next we will prove #EO$(f,g)$ is #P-hard if $f\in {𝒟}_1\backslash 𝒜$ and $g\in {𝒟}_0\backslash 𝒜$, which implies that #EO$({𝒟}_1\cup {𝒟}_0)$ is #P-hard. We first consider a basic case where $f$ and $g$ are basic ${\delta }_1$-affine and ${\delta }_0$-affine kernels of order $2$ respectively.