Boiling down to counting Eulerian trails

First of all, let us boil this problem down to a graph theory problem.
A natural interpretation would be like constructing \(16\)-vertex graph labeled \((0,0,0,0), \dots\), and \((1,1,1,1)\), with appropriate edges, and count paths that visits vertex \((i,j,k,l)\) \(X_{i,j,k,l}\) times. However, it seems that this problem does not have an efficient way to solve, requiring exponential time with respect to the sum of degrees.
Instead, let us consider the following graph \(G\) with eight vertices and \(N\) edges:

• Label vertices with \((0, 0, 0), \dots\), and \((1, 1, 1)\).
• For each \((i,j,k,l)\), add \(X_{i,j,k,l}\) edges from \((i, j, k)\) to \((j, k, l)\)

Then one can assert that a sequence that satisfies the condition corresponds one-by-one to a path that passes through all the edges on the graph. In other words, the given problem is boiled down to counting the number of Eulerian trails on a directed graph.

By fixing the starting and ending vertex, counting Eulerian trails is boiled down to counting Eulerian circuits, so it is sufficient to count the number of Eulerian circuits fast. In the next chapter, we describe how to count them in polynomial time with respect to the number of vertices.

Counting the number of Eulerian circuits on a directed grpah

Let \(G\) be a directed graph, possibly with multiple edges and self loops. All edges of \(G\) can be distinguished.
\(G\) has an Eulerian circuits if and only if \(G\) is connected and every vertex has the same indegree and outdegree. Such a graph is called an Eulerian graph. We suppose that \(G\) is an Eulerian graph. Then \(G\) satisfies the following theorem:

BEST theorem

The number of Eulerian circuits on a Eulerian graph \(G\) equals:

\[c(G, v) \cdot \prod_{w \in V} (\mathrm{outdeg}(w) - 1)!,\]

where \(c(G, v)\) is the number of directed spanning trees (spanning trees where every edge point toward the root) rooted at vertex \(v\) (actually, \(c(G,v)\) is independent of \(v\), so \(v\) can be taken arbitrarily), \(V\) is the vertex set of \(G\), and \(\mathrm{outdeg}(w)\) is the outdegree of vertex \(w\).

(Proof) Fix an edge \(e\) going from \(v\), regarding that every Eulerian circuits starts with \(e\).
Take an Eulerian circuit \(C\). For vertex \(w\) (\(w \neq v\)), let \(e_w\) be the last edge used to leave \(w\) in \(C\); then \(T = \lbrace e_w \vert w \neq v \rbrace\) is a directed spanning tree.

• If \(T\) is not a directed spanning tree, then \(T\) has a cycle (a closed trail that may have repeated edges). But by the condition of \(e_w\), if two edges \(e_1\) and \(e_2\) in \(T\) satisfies \((e_1\text{'s head}) = (e_2\text{'s tail})\), then it turns out that \(e_1\) was used before \(e_2\), which is a contradiction.

Next, let \(E'\) be the set of edges obtained by removing \(e\) and all \(e_w\) from the edge set \(E\) of \(G\), and let \(P_i\) be the sequence of edges in \(E'\) whose tail is \(i\), arranged in the order where the Eulerian circuit visits. By definition, one can uniquely obtain \(T\) and \(P_1, P_2, \dots, P_{|V|}\) from \(T\).

Conversely, suppose that \(T\) and \(P_1, P_2, \dots, P_{|V|}\) are arbitrarily chosen. Then one can obtain an Eulerian circuit \(C\) by traversing edges by the following rule: “let \(i\) be the current vertex. If \(P_i\) has an unused edge, use the frontmost one; otherwise, use the one in \(T\).”

• Suppose that the construction of an Eulerian circuit fails. It means that while traversing edges by the procedure, you are stuck because no more outgoing edge is available on a vertex — which in fact turns out to be \(v\) (for any other vertices, indegree equals outdegree, so it never happens that no more outgoing edge is available). It also turns out that you run out of edges going from or to \(v\), as the indegree and outdegree of \(v\) are equal. By removing the traversed edges from \(G\), the graph is decomposed into one or more Eulerian graphs that does not contain \(v\) and some isolated points. Take an Eulerian graph, denoting it by \(G'\). Then, by the rule of choosing edges, all edges in \(T\) going from a vertex in \(G'\) must be contained in \(G'\). Consequently, \(T\) does not contain an edge from a vertex in \(G'\) from another not in \(G'\), which is consistent with the assumption that \(T\) is a directed spanning tree rooted at \(v\).

Therefore, we can construct a bijection between \(C\) and \(T, P_1, P_2, \dots, P_{|V|}\), so the number of \(C\) coincides with the number of \(T, P_1, P_2, \dots, P_{|V|}\), which is what we want. (End of proof)

This proof also shows that the number \(c(G, v)\) of directed spanning trees rooted at \(v\) on an Eulerian graph is independent of \(v\).
Moreover, after removing self loops, \(c(G, v)\) can be boiled down to a determinant just as counting ordinary spanning trees by the following theorem:

Directed matrix-tree theorem

Let \(G\) be a directed graph without a self loop. Let us define the directed Laplacian matrix \(L(G)\) by

\[L_{u,v} = \begin{cases} -(\text{the number of edge from }u\text{ to }v) & \text{if }u \neq v \\ \mathrm{outdeg}(u) & \text{otherwise}. \end{cases} \]

Then it holds that

\[c(G, v) = \det L_v(G),\]

where, \(L_v(G)\) is the matrix obtained by removing the \(v\)-th row and \(v\)-th column from \(L(G)\).

(Proof) We show it indutively. If \(G\) has two vertices, one can actually construct the directed Laplacian matrix and compute the determinant.
Suppose that \(G\) has three or more vertices. Choose a vertex \(u \neq v\) and an edge \(e\) going from \(u\). If the outdegree of \(u\) is \(1\), then one can assert that \(\det L_v(G) = \det L_v(G')\), where \(G'\) is the graph obtained by contracting \(e\) in \(G\) (by a careful deformation of the determinant; details omitted).
Suppose that the outdegree of \(u\) is \(2\) or greater. Let \(G_1\) be the graph obtained by removing \(e\) from \(G\), and \(G_2\) be one obtained by removing all edges going from \(u\), expect for \(e\), from \(G\).

\[c(G, v) = c(G_1, v) + c(G_2, v) = \det L_v(G_1) + \det L_v(G_2).\]

Comparing \(L_v(G_1)\) and \(L_v(G_2)\), all rows but the \(u\)-th are equal, and the sum of the \(u\)-th rows of \(L_v(G_1)\) and \(L_v(G_2)\) equals that of the \(u\)-th row of \(L_v(G)\). Therefore,

\[\det L_v(G_1) + \det L_v(G_2) = \det L_v(G).\]

Thus, it is boiled down to matrix-tree theorem for a graph with less edges than \(G\), which completes the proof by induction. (End of proof)

Using this theorem, counting Eulerian circuits can be done in polynomial time with respect to the number of vertices. Hence, the original problem can be solved using this algorithm. (The original problem does not distinguish multiple edges, but it can be handled by dividing by factorials to identify them.)
The computational complexity is about \(\mathrm{O}(B^4 + N)\) (where the number of vertices in the graph \(B = 8\)) (where computing the determinant in \(\mathrm{O}(B^3)\) times occur at most \(B\) times), which is fast enough.