# Counting Euler Tours in Undirected Bounded Treewidth Graphs

Nikhil Balaji  Chennai Mathematical Institute, Chennai, India.
<EMAIL_ADDRESS>Indian Institute of Technology, Bombay, India.
<EMAIL_ADDRESS>Samir Datta  Chennai Mathematical Institute, Chennai,
India<EMAIL_ADDRESS>Venkatesh Ganesan  Birla Institute of
Technology and Science - Pilani, India<EMAIL_ADDRESS>
###### Abstract

We show that counting Euler tours in undirected bounded tree-width graphs is
tractable even in parallel - by proving a
$\mbox{{\sf\\#SAC}${}^{1}$}\subseteq\mbox{{\sf NC}${}^{2}$}\subseteq\mbox{{\sf
P}}$ upper bound. This is in stark contrast to #P-completeness of the same
problem in general graphs.

Our main technical contribution is to show how (an instance of) dynamic
programming on bounded _clique-width_ graphs can be performed efficiently in
parallel. Thus we show that the sequential result of Espelage, Gurski and
Wanke [16] for efficiently computing Hamiltonian paths in bounded clique-width
graphs can be adapted in the parallel setting to count the number of
Hamiltonian paths which in turn is a tool for counting the number of Euler
tours in bounded tree-width graphs. Our technique also yields parallel
algorithms for counting longest paths and bipartite perfect matchings in
bounded-clique width graphs.

While establishing that counting Euler tours in bounded tree-width graphs can
be computed by non-uniform monotone arithmetic circuits of polynomial degree
(which characterize #SAC1) is relatively easy, establishing a uniform #SAC1
bound needs a careful use of polynomial interpolation.

##  1 Introduction

An Euler tour of a graph is a closed walk on the graph that traverses every
edge in the graph exactly once. Given a graph, deciding if there is an Euler
tour of the graph is quite simple. Indeed, the famous Königsberg bridge
problem that founded graph theory is a question about the existence of an
Euler tour using each of these bridges exactly once. Euler settled this
question in the negative and in the process gave a necessary and sufficient
condition for a graph to be Eulerian (A connected graph is Eulerian if and
only if all the vertices are of even degree). This gives a simple algorithm to
check if a graph is Eulerian.

An equally natural question is to ask for the number of distinct Euler tours
in a graph. For the case of directed graphs, the BEST theorem due to De
Bruijn, Ehrenfest, Smith and Tutte gives an exact formula that gives the
number of Euler tours in a directed graph [1, 25] which yields a polynomial
time algorithm via a determinant computation. For undirected graphs, no such
closed form expression is known and the computational problem is #P-complete
[7]. In fact, the problem is #P-complete even when restricted to $4$-regular
planar graphs [18]. So exactly computing the number of Euler tours is not in
polynomial time unless $\mbox{{\sf\\#P}}=\mbox{{\sf P}}$.

In this paper, we are concerned with the problem of counting Euler tours on
graphs of bounded treewidth. Many problems which are NP-hard for general
graphs, can be solved in polynomial time on bounded treewidth graphs. Indeed,
a result of Courcelle [11] asserts that any graph property that is expressible
in Monadic Second Order logic (with edge quantifiers) can be solved in linear
time on bounded treewidth graphs. Elberfeld et al. [15] adapt the theorem of
Courcelle in the parallel setting and prove a L bound. However, Eulerianity is
provably not ${\sf MSO}$ -expressible [14] and hence the approaches mentioned
above are not directly applicable in our context.

Our strategy to count Euler tours is as follows: Given a bounded treewidth
graph $G$, we count the number of Euler tours of $G$ by counting the number of
Hamiltonian tours of the line graph of $G$, $L(G)$. In general, there is no
bijection between these two quantities, but we show that $G$ can be modified
to obtain $G^{\prime}$ ($tw(G^{\prime})\leq tw(G)+3$) such that $G$,
$G^{\prime}$ have the same number of Eulerian tours, which equals the number
of Hamiltonian tours of $L(G^{\prime})$. Henceforth, we will be primarily
interested in line graphs of bounded treewidth graphs. It is known that such
graphs are of bounded clique-width [24]

We base our proof on a proof that the decision version of Hamiltonicity is
polynomial time computable in bounded clique-width graphs [16]. We prove that
this algorithm can be parallelised and extended to the counting version. Next,
we show that for line graphs of bounded tree-width graphs which form the
family of interest, the clique-width expression can be inferred from the
corresponding tree decomposition. The tree decomposition itself is obtainable
by the L-version of Bodlaender’s theorem [15].

Our main tool in establishing a uniform NC-bound for counting Hamiltonian
cycles on bounded clique-width graphs hinges on _polynomial interpolation_.
While polynomial interpolation has been used successfully to compute various
graph polynomials [23], our use is somewhat indirect and subtle: it is used by
the uniformity machine to populate a table whose entries do not depend on the
input bounded clique-width expression but only the number of vertices in the
corresponding graph and the clique-width. We then build a monotone arithmetic
circuit that uses the clique-width expression of the graph and entries from
this table to count the number of Hamiltonian cycles in the clique-width
bounded graph. We then observe that since the number of distinct Hamiltonian
tours of a graph is at most exponential in the number of vertices of the
graph, and the circuit is monotone, the formal degree of the circuit must be a
polynomial in the size of the input graph. This allows us to use a result from
circuit complexity [2] to yield an upper bound of #SAC1 on the complexity of
counting Euler tours on bounded treewidth graphs.

Our techniques also yield a parallel upper bound on the problems of counting
longest paths/cycles and counting bipartite matchings in bounded clique-width
graphs. These are well known problems (and #P-complete in general graphs) but
their (counting) complexity has not been investigated in bounded clique-width
graphs. While [13] studies the problem of counting longest paths and perfect
matchings in bounded _tree-width DAGs_ , we improve the results by resolving
the problems for bounded _clique-width graphs_ at the cost of replacing the L
bound by a #SAC1 bound where we know that $\mbox{{\sf L}}\
\subseteq\mbox{{\sf\\#SAC}${}^{1}$}\ \subseteq\mbox{{\sf NC}${}^{2}$}\
\subseteq\mbox{{\sf P}}$ 111Note that #SAC1 is a function class and when we
say $\mbox{{\sf\\#SAC}${}^{1}$}\ \subseteq\mbox{{\sf NC}${}^{2}$}$, what we
actually mean is that any bit of the #SAC1 function family of interest is
computable by a NC2 circuit family.

###  1.1 Previous Work

Chebolu, Cryan, Martin have given a polynomial time algorithm for counting
Euler tours in undirected series-parallel graphs [8] and they have claimed to
extend it to a polynomial time algorithm [9] for the counting Euler tours in
bounded tree-width graphs. We would like to point out that the only
incomplete, unrefereed manuscript available publicly [9] sketches an algorithm
that does dynamic programming directly on the tree-decomposition. Since we
show how to obtain the line graph of the bounded tree-width graph efficiently
in parallel and then work on this bounded clique-width graph - our approach is
fundamentally different from that of [8, 9]. Another difference is that their
algorithm is not designed to be parallelisable.

Also notice that in a precursor to this paper [4], using totally different
techniques (basically applications of the Logspace version of Courcelle’s
theorem [15]) it was claimed that the number of Euler tours in bounded tree-
width directed and undirected graphs can be counted in Logspace but the
approach had a serious flaw in the undirected version. Later versions [5, 6]
of the paper claim the result only for directed graphs. This work proves a
slightly weaker version of the result - the upper bound being #SAC1 rather
than Logspace.

Given that counting Hamiltonian cycles on bounded clique-width graphs will
suffice for our purposes, one result that is directly relevant is that of
Flarup and Lyaudet [17]: They study the expressive power of Perfect Matching
and Hamiltonian polynomials of graphs of bounded clique-width and show that
they can simulate arithmetic polynomials, and are themselves contained in VP.
This yields a GapSAC1 bound (implicit) for counting Hamiltonian cycles in
bounded clique-width graphs right away. There are two aspects in which the
work of [17] differs from our work: Firstly, even though their techniques are
also inspired from [16] like ours, they work with a slightly different notion
of clique-width namely $W-m-\mbox{clique-width}$222These are weighted versions
of clique-width and are used to produce weighted graphs. [17] motivate this
variant of clique-width by observing that since $K_{n}$ has clique-width $2$,
most graph polynomials are VNP-complete for bounded clique-width graphs..
Secondly, in the case of counting Euler tours, from a straight-forward
application of [17] the best upper bound that can be obtained from the circuit
families constructed in [17] is non-uniform GapSAC1, whereas we get an upper
bound of Logspace-uniform333In an earlier version of this paper, we had
erroneously claimed a GapL upper bound for counting Euler tours. As pointed
out to us by Ramprasad Saptharishi, there is a rather serious gap with this
approach. #SAC1.

There is some similarity that this work bears with that of Makowsky et al.
[23], in that both involve polynomial interpolation to count witnesses for a
graph theory problem. The similarity is somewhat superficial because we use
interpolation to obtain numbers _independent_ of the input graph while they
interpolate to compute a graph polynomial that crucially depends on the graph.
The choice of graph theory problems is also quite different. In particular,
[23] does not address the Hamiltonian cycle problem.

###  1.2 Our Results

This is the main theorem of this work:

###### Theorem 1

#Hamiltonian Cycles (or Paths) for bounded clique-width graphs is in #SAC1.
Consequently, #Euler Tours for bounded tree-width graphs is also in #SAC1.

As a bonus we also get the following :

###### Theorem 2

The following counts can be obtained in #SAC1 for bounded clique-width graphs
(given a bounded clique-width expression for the graph):

  1. 1.

#Hamiltonian Cycles

  2. 2.

#Longest Paths/Cycles

  3. 3.

#Cycle Covers

  4. 4.

#Perfect Matchings (for bipartite graphs)

###  1.3 Overview of Algorithm

Every Euler tour in a graph yields a Hamiltonian cycle in its line graph.
Though this map is not bijective we show that we can make it so by altering
the input graph slightly. It is well known [20] that the line graphs of
bounded tree-width graphs have bounded clique-width. We show how to obtain a
bounded clique-width decomposition for the line graph of a bounded tree-width
graph in Logspace using the Logspace version of Courcelle’s Theorem [15] by
first obtaining a bounded tree-width decomposition via a Logspace version of
Bodlaender’s theorem [15].

Our main algorithm replaces the sequential procedure from [16] to decide if a
bounded clique-width graph has a Hamiltonian path. Instead, it computes the
number of Hamiltonian cycles. The procedure uses elementary counting coupled
with polynomial interpolation to compute some matrices which are independent
of the input graph depending only on its size. The matrices are then combined
with vectors maintaining counts, along the structure tree of the clique-
decomposition. A degree bound for the monotone arithmetic circuit then
suffices to prove the #SAC1 bound.

###  1.4 Organization

The rest of the paper is organized as follows: In Section 2, we introduce some
definitions and results that will be helpful in understanding the rest of the
paper. Section 3 shows how to obtain a clique-width expression for the line
graph of a bounded treewidth graph in Logspace. Section 4 presents a #SAC1
implementation of our algorithm to count the number of Hamiltonian tours in
graphs of bounded clique-width. We conclude with some unresolved questions
related to this work in Section 5.

##  2 Preliminaries

######  Definition 3 (Line Graph)

For an undirected graph $G=(V,E)$, the line graph of $G$ denoted
$L(G)=(L_{V},L_{E})$ is the graph where $L_{V}=E$ and $(e_{i},e_{j})\in L_{E}$
if and only if there exists a vertex $v\in V$ such that both $e_{i}$ and
$e_{j}$ are incident on $v$.

######  Definition 4 (Treewidth)

Given an undirected graph $G=(V_{G},E_{G})$ a tree decomposition of $G$ is a
tree $T=(V_{T},E_{T})$(the vertices in $V_{T}\subseteq 2^{V_{G}}$ are called
bags), such that

  1. 1.

Every vertex $v\in V_{G}$ is present in at least one bag, i.e., $\cup_{X\in
V_{T}}X=V_{G}$.

  2. 2.

If $v\in V_{G}$ is present in bags $X_{i},X_{j}\in V_{T}$, then $v$ is present
in every bag $X_{k}$ in the unique path between $X_{i}$ and $X_{j}$ in the
tree $T$.

  3. 3.

For every edge $(u,v)\in E_{G}$, there is a bag $X_{r}\in V_{T}$ such that
$u,v\in X_{r}$.

The width of a tree decomposition is $\max_{X\in V_{T}}(|X|-1)$. The treewidth
of a graph is the minimum width over all possible tree decomposition of the
graph.

######  Definition 5 (NLC-width)

Let $k$ be a positive integer. The class $NLC_{k}$ of labeled graphs
$G=(V,E,lab_{G})$ where $lab_{G}:V\to[k]$, is recursively defined as follows:

  1. 1.

The single vertex graph labeled by a label $a$, $\bullet_{a}$ for $a\in[k]$ is
in $NLC_{k}$.

  2. 2.

Let $G=(V_{G},E_{G},lab_{G})\in NLC_{k}$ and $H=(V_{H},E_{H},lab_{H})\in
NLC_{k}$ be two vertex-disjoint labeled graphs and $S\subseteq[k]^{2}$, then
$G\times_{S}H=(V^{\prime},E^{\prime},lab^{\prime})\in NLC_{k}$, where
$V^{\prime}=V_{G}\cup V_{H}$ and

$E^{\prime}=E_{G}\cup E_{H}\cup\\{(u,v)|u\in V_{G},v\in
V_{H},(lab_{G}(u),lab_{H}(v))\in S\\}$

and for all $u\in V^{\prime}$,

$lab^{\prime}(u)=\begin{cases}lab_{G}(u),&\text{if}\ u\in V_{G}\\\
lab_{H}(u),&\text{if}\ u\in V_{H}\end{cases}$

  3. 3.

Let $G=(V_{G},E_{G},lab)\in NLC_{k}$ and $R:[k]\to[k]$ be a function, then
$\circ_{R}(G):=(V_{G},E_{G},lab^{\prime})$ defined by
$lab^{\prime}(u)=R(lab(u))$ for all $u\in V_{G}$ is in $NLC_{k}$.

The NLC-width444NLC stands for _Node Label Controlled_ , has its origins in
graph grammars, was defined by Wanke [28] of a labeled graph $G$ is the least
integer $k$ such that $G\in NLC_{k}$. An expression $Y$ built with
$\bullet_{a},\times_{S},\circ_{R}$, for integers $a\in[k]$, $S\in[k]^{2}$ and
$R:[k]\to[k]$ is called a NLC-width $k$ expression. The graph defined by
expression $Y$ is denoted by $val(Y)$.

######  Definition 6 (Clique Width)

Let $k$ be a positive integer. The class $CW_{k}$ of labeled graphs
$G=(V,E,lab_{G})$ where $lab_{G}:V\to[k]$ is recursively defined as follows:

  1. 1.

The single vertex graph labeled by a label $a$, $\bullet_{a}$ for $a\in[k]$ is
in $CW_{k}$.

  2. 2.

Let $G=(V_{G},E_{G},lab_{G})\in CW_{k}$ and $H=(V_{H},E_{H},lab_{H})\in
CW_{k}$ be two vertex-disjoint labeled graphs. Then $G\oplus
H=(V^{\prime},E^{\prime},lab^{\prime})\in CW_{k}$, where $V^{\prime}=V_{G}\cup
V_{H}$ and $E^{\prime}=E_{G}\cup E_{H}$ and for all $u\in V^{\prime}$

$lab^{\prime}(u)=\begin{cases}lab_{G}(u),&\text{if}\ u\in V_{G}\\\
lab_{H}(u),&\text{if}\ u\in V_{H}\end{cases}$

  3. 3.

Let $a,b$ be distinct positive integers and $G=(V_{G},E_{G},lab)\in CW_{k}$ be
a labeled graph. Then,

    1. (a)

$\rho_{a\to b}(G):=(V_{G},E_{G},lab^{\prime})\in CW_{k}$ where for all $u\in
V_{G}$

$lab^{\prime}(u)=\begin{cases}lab_{G}(u),&\text{if}\ lab_{G}(u)\neq a\\\
b,&\text{if}\ lab_{G}(u)=a\end{cases}$

    2. (b)

$\eta_{a,b}(G):=(V_{G},E^{\prime},lab_{G})\in CW_{k}$ where,

$E^{\prime}=E_{G}\cup\\{(u,v)|u,v\in V_{G},lab(u)=a,lab(v)=b\\}$

The clique-width of a labeled graph $G$ is the least integer $k$ such that
$G\in CW_{k}$. An expression $X$ built with $\bullet_{a},\oplus,\rho_{a\to
b},\eta_{a,b}$ for integers $a,b\in[k]$ is called a clique-width $k$
expression. By $val(X)$, we denote the graph defined by expression $X$.

######  Definition 7 (Chordal graph, Chordal completion)

A graph is said to be chordal if every cycle with at least $4$ vertices always
contains a chord. A chordal completion of a graph $G$ is a chordal graph with
the same vertex set as $G$ which contains all edges of $G$.

######  Definition 8 (Perfect Elimination Ordering, Elimination Tree [19])

Let $G=(V,E)$ be a graph and $o=(v_{1},v_{2},\ldots,v_{n})$ be an ordering of
the vertices of $G$. Let $N^{-}(G,o,i)$ and $N^{+}(G,o,i)$ for $i=1,\ldots,n$
be the set of neighbors $v_{j}$ of vertex $v_{i}$ with $j<i$ and $j>i$
respectively.

$\displaystyle N^{-}(G,o,i)$ $\displaystyle=$
$\displaystyle\\{v_{j}|(v_{i},v_{j})\in E\mbox{\ and\ }j<i\\}$ $\displaystyle
N^{+}(G,o,i)$ $\displaystyle=$ $\displaystyle\\{v_{j}|(v_{i},v_{j})\in
E\mbox{\ and\ }j>i\\}$

The vertex order $o$ is said to be a Perfect Elimination Ordering (PEO) if for
all $i\in[n]$, $N^{+}(G,o,i)$ induces a complete subgraph of $G$. The
structure of $G$ can then be characterized by a tree $T(G,o)=(V_{T},E_{T})$
defined as follows:

$\displaystyle V_{T}$ $\displaystyle=$ $\displaystyle V$ $\displaystyle E_{T}$
$\displaystyle=$ $\displaystyle\\{(v_{i},v_{j})\in E|i<j\mbox{\ and\ }\forall
j^{\prime},i<j^{\prime}<j,(v_{i},v_{j^{\prime}})\notin E\\}$

Such a $T(G,o)$ is called the Elimination Tree associated with the graph $G$.

For more information on Chordal graphs and PEO, we refer the reader to
Golumbic’s book [19].

######  Definition 9 (Cycle Cover)

A cycle cover ${\cal C}$ of $G=(V,E)$ is a set of vertex-disjoint cycles that
cover the vertices of $G$. I.e., $\mbox{${\cal
C}$}=\\{C_{1},C_{2},\ldots,C_{k}\\}$, where
$V(C_{i})=\\{c_{i_{1}},\ldots,c_{i_{r(i)}}\\}\subseteq V$ such that
$(c_{i_{1}},c_{i_{2}})$, $(c_{i_{2}},c_{i_{3}})$, $\ldots$,
$(c_{i_{r(i)-1}},c_{i_{r(i)}})$, $(c_{i_{r(i)}},c_{i_{1}})\in
E(C_{i})\subseteq E$ and $\uplus_{i=1}^{k}V(C_{i})=V$. The least numbered
vertex $h_{i}\in V(C_{i})$, is called the head of the cycle.

######  Definition 10 (#SAC1)

#SAC1 is the class of functions from $\\{0,1\\}^{n}$ to nonnegative integers
computed by polynomial-size logarithmic-depth, semi unbounded arithmetic
circuits555Note that such circuits have degree that is at most a polynomial in
the number of input variables., using $+$ (unbounded fan-in) and $\times$
gates (fan-in $2$) and the constants $0$ and $1$.

For further background on circuit complexity, we refer the reader to [27].

######  Proposition 11 ([2, 26])

Any function $f:\\{0,1\\}^{n}\to R$, where $R$ is a semi-ring, computed by
arithmetic circuits of size $s$ and degree $d$ can be computed by semi-
unbounded arithmetic circuits of size $\mbox{{\sf poly}}(s,d)$ and depth
$O(\log{d})$. In particular, all functions computed by polynomial sized
circuits of polynomial degree are exactly those in #SAC1.

######  Fact 1 (Kronecker substitution [12])

Let $P(x_{1},x_{2},\ldots,x_{n})$ be a multivariate polynomial of degree $d$.
We replace every occurence of variable $x_{i}$ by $x^{d^{i}}$. This yields an
unique univariate polynomial $Q(x)$ of degree at most $d^{O(n)}$ such that $P$
can be efficiently recovered from the knowledge of coefficients of $Q$. When
the number of variables is a constant, the degree of the multivariate
polynomial and the univariate polynomial are polynomially related.

##  3 From Euler Tours to Hamiltonian cycles

It is possible to construct a graph $G$ such that $G$ has no Eulerian tours,
but $L(G)$ has a Hamiltonian cycle666Indeed, there is a $2$-connected graph –
$K_{4}$ with one of the edges removed – which is non-Eulerian but its line
graph is Hamiltonian.. Proposition 12 gives necessary and sufficient
conditions for when a line graph of a given graph is Hamiltonian.

######  Proposition 12 ([21])

$L(G)$ is Hamiltonian if and only if $G$ has a closed trail that contains at
least one end point of every edge.

Given a graph $G$, we want to construct a graph $G^{\prime}$ such that every
closed trail in $G^{\prime}$ that contains at least one end point of every
edge is exactly an Eulerian tour of $G^{\prime}$. The following Lemma
guarantees exactly this:

###### Lemma 13

Given an undirected graph $G$, construct a graph
$G^{\prime}=(V^{\prime},E^{\prime})$ from $G$ as follows: Replace every edge
$e=(u,v)$ of $G$ by path of length three. Then $G$ and $G^{\prime}$ have the
same number of Eulerian tours and the Eulerian tours of $G^{\prime}$ are in
bijection with the Hamiltonian tours of $L(G^{\prime})$.

#### Proof:

Recall that $G^{\prime}=(V^{\prime},E^{\prime})$ is obtained from $G$ as
follows: Replace every edge $e=(u,v)$ of $G$ by path of length three, namely
$(u,x_{e}),(x_{e},y_{e})$, $(y_{e},v)$. For a graph $G$, let $\mathcal{E}_{G}$
and $\mathcal{H}_{G}$ denote the set of Euler Tours and Hamiltonian tours of
$G$ respectively. We claim the following:

Consider the map $h:E(G^{\prime})^{m}\to V(L(G^{\prime}))^{m}$ (where
$m=|E(G^{\prime})|$), defined by $h:ET\mapsto HT$. Here $ET=\langle
e_{1},e_{2},\ldots,e_{m}\rangle$ is an edge sequence of $G^{\prime}$ with
$e_{1}$ being the least edge under an arbitrary but fixed ordering of the
edges of $G^{\prime}$; $HT=\langle
v_{e_{1}},v_{e_{2}},\ldots,v_{e_{m}}\rangle$ is the corresponding vertex
sequence of $L(G^{\prime})$ (where we associate the edge $e\in E(G)$ with
vertex $v_{e}\in V(L(G))$). Then the proof is completed by invoking Lemma 14
to show that $h$ is the desired bijection with its domain restricted to the
set of Euler tours. $\square$

###### Lemma 14

We have the following properties of the map $h$:

  1. 1.

If $ET\neq ET^{\prime}$ then $h(ET)\neq h(ET^{\prime})$

  2. 2.

$h(ET)$ is defined for every Euler tour $ET$

  3. 3.

$HT=h(ET)$ is a Hamiltonian cycle for an Euler tour $ET$

  4. 4.

If $HT$ is a Hamiltonian cycle in $L(G^{\prime})$ then there exists an Euler
tour $ET$ in $G^{\prime}$ such that $h(ET)=HT$

#### Proof:

(of Lemma 14)

  1. 1.

Obvious from definitions of $h,L(G^{\prime})$.

  2. 2.

Obvious from definition of $h$.

  3. 3.

If $e,e^{\prime}$ are consecutive edges in $ET$, then they must share a vertex
since $ET$ is an Euler tour and hence $v_{e},v_{e^{\prime}}$ must be adjacent
in $L(G^{\prime})$. Also since $ET$ is a permutation of all the edges of
$G^{\prime}$, therefore $h(ET)$ is a permutation of all the vertices of
$L(G^{\prime})$.

  4. 4.

From the way $G^{\prime}$ is obtained from $G$, if
$v_{e_{i-1}},v_{e_{i}},v_{e_{i+1}}$ are successive vertices on an arbitrary
Hamiltonian Tour $HT$ of $L(G^{\prime})$, then $e_{i-1},e_{i},e_{i+1}$ cannot
all be incident on a vertex $u\in V(G)\cap V(G^{\prime})$. For, suppose they
were, then there exist distinct vertices $a,b,c\in V(G)\cap V(G^{\prime})$,
such that $e_{i-1},e_{i},e_{i+1}$ are subdivision edges of the edges
$e^{\prime}=(u,a),e^{\prime\prime}=(u,b),e^{\prime\prime\prime}=(u,c)$. But
then it is easy to see that the edge
$(x_{e^{\prime\prime}},y_{e^{\prime\prime}})$ – the middle subdivision edge of
$e^{\prime\prime}$ – cannot be traversed in $ET$. This is since
$e_{i}=(u,x_{e^{\prime\prime}})$, one of its only two neighbours is not used
to traverse it.

This implies that if $HT=v_{e_{1}},v_{e_{2}}\ldots,$ then $e_{1},e_{2},\dots$
is an Euler Tour of $G^{\prime}$. Indeed, a Hamiltonian path in
$L(G^{\prime})$ is a permutation of the vertices $v_{e}$’s of $L(G^{\prime})$,
thus induces a permutation of the edges of $G^{\prime}$. But a sequence
$e_{1},\ldots,e_{m}$ is an Euler tour iff for every $i$ the vertex incident on
edges $e_{i-1},e_{i}$ and the vertex incident on edges $e_{i},e_{i+1}$ are
distinct (and form the two endpoints of $e_{i}$) – which follows from the
previous paragraph, completing the proof.

$\square$

Notice that $G$ is a minor of $G^{\prime}$, and the tree decomposition of
$G^{\prime}$ can be obtained from that of $G$ by locally adding to each bag
containing an edge $e$ of $G$, the extra vertices and edges of the path of
length three. Hence, the following is immediate:

###### Proposition 15

$G$ has bounded treewidth iff $G^{\prime}$ has bounded treewidth.

######  Proposition 16 ([20])

If $G$ is of treewidth $k$, then $L(G)$ has clique-width $f(k)=2k+2$.

######  Proposition 17 ([15])

Given a bounded treewidth graph $G$, a balanced tree decomposition777A tree
decomposition of a graph is said to be balanced if the tree underlying the
decomposition is balanced of $G$ is obtainable in L.

We first need the Perfect Elimination Ordering(PEO) of the vertices of the
graph. It is known that a graph has a PEO if and only if it is chordal. Since
we can do a chordal completion of a bounded treewidth graph (while preserving
treewidth), such an ordering of the vertices always exists. Recently Arvind et
al. gave a Logspace procedure for obtaining a PEO in $k$-trees (which are
maximal treewidth-$k$ graphs). We adapt this for graphs that are chordal
completions of bounded treewidth graphs:

######  Lemma 18 (Adapted from [3])

Given a balanced tree decomposition of a bounded treewidth graph $G$, a
Perfect Elimination Ordering and the corresponding elimination tree of a
chordal completion of $G$, which is a balanced binary tree of depth
$O(\log{n})$, can be computed in L.

#### Proof:

We first do a chordal completion of $G$ by adding edges to every bag in the
tree decomposition to ensure that each bag contains a simplicial vertex (it
could contain more than one, but at most $k$ since the treewidth is at most
$k$). Now, we can find a partition of the vertex set of $G$ –
$V(G)=R_{0}\mathbin{\dot{\cup}}R_{1}\mathbin{\dot{\cup}}\ldots\mathbin{\dot{\cup}}R_{l}$
as follows: First, pick one simplicial vertex from each bag in the tree
decomposition and make the layer $R_{0}$. If these are more than one
simplicial vertex in a bag, these are added to the sublayers of $R_{0}$, of
which there could be at most $k$ many of them which we call $R_{0j}$ for
$j\in[k]$ (once a vertex is picked this way, it is removed from the bag).
Since the graph is chordal, this process results in a chordal graph again, and
we now do the same process iteratively, and call the sets of simplicial
vertices so obtained, $R_{1},R_{2},\ldots,R_{l}$, each of which have
appropriate sublayers whenever there are more than one simplicial vertex in
the bag (and we will exhaust all the vertices in the process). Note that this
process can go on for at most $l=O(\log{n})$ steps, which is the diameter of
the graph (This is because we started with a balanced binary tree
decomposition of height $O(\log{n})$ and since every bag is a clique after the
chordal completion, the distance between any two nodes in this tree
decomposition is $O(\log{n})$.

Now we claim that if we order $R_{01},\ldots,R_{lk}$ in the reverse order and
within each of these $R_{i}$, we order the vertices arbitrarily, we obtain a
PEO of the graph. This follows straight away from the definition of a PEO and
the construction of the $R_{i}$’s.

Recall that an elimination tree for a graph $G=(V,E)$ and PEO
$o=(v_{1},v_{2},\ldots,v_{n})$ is $T(G,o)=(V_{T},E_{T})$ and is defined as:

$\displaystyle V_{T}$ $\displaystyle=$ $\displaystyle V$ $\displaystyle E_{T}$
$\displaystyle=$ $\displaystyle\\{(v_{i},v_{j})\in E|i<j\mbox{\ and\ }\forall
j^{\prime},i<j^{\prime}<j,(v_{i},v_{j^{\prime}})\notin E\\}$

$T(G,o)$ is a tree because every vertex $v_{i}$, $i<n$ is adjacent to exactly
one vertex $v_{j}$ with $j>i$. We can now construct the elimination tree from
our PEO obtained from the $R_{i}$’s. Note that every vertex in the elimination
tree has at most $k$ children which happens when a bag has $k$ vertices all of
which are simplicial, (they are present one each in each of the sublayers
$R_{ij}$, $j\in[k]$ of $R_{i}$). Hence we can construct an elimination tree of
diameter at most $O(\log{n})$ in Logspace. $\square$

######  Lemma 19 (Adapted from [20])

Given the tree decomposition of a graph $G$ along with a elimination tree, the
clique-width expression $X$ of $L(G)$ is obtainable in L. The parse tree of
this clique-width expression has height at most $O(\log{n})$

We show in the subsequent Lemma that the method in [20] is amenable to a
Logspace implementation when provided with a PEO of the vertices of the graph.

######  Lemma 20 (Adapted from [20])

The NLC-width of the line graph $L(G)$ of a graph $G$ of treewidth $k$ is at
most $k+2$ and such a NLC-width expression is obtainable in L.

Gurski and Wanke [20] observe that it is sufficient to look at $G$ that are
$k$-trees here because the line graph of every subgraph of $G$ then is an
induced subgraph of the line graph of $G$ and the class $NLC_{k}$ is closed
under taking induced subgraphs for every $k\geq 1$ (See Theorem 4 in [20]).
Our method involves dealing with bounded treewidth graphs that are chordal,
which are a strict superclass of $k$-trees and we observe that the property
mentioned above still holds in this case.

#### Proof:

(of Lemma 20) Given an undirected graph $G=(V,E)$, let
$o=(v_{1},v_{2},\ldots,v_{n})$ be the PEO of the vertices of $G$. The
structure of $G$ can then be characterized by the PEO tree $T(G,o)$. Let
$col:V_{G}\to[k+1]$ be a $(k+1)$-coloring of $G$ with $col(v_{i})\neq
col(v_{j})$ for all $(v_{i},v_{j})\notin E$. Let
$N^{-}(T(G,o),o,i)=\\{v_{j_{1}},v_{j_{2}},\ldots,v_{j_{m}}\\}$ (defined by the
tree $T(G,o)$) and $N^{+}(G,o,i)=\\{v_{l_{1}},\ldots,v_{l_{r}}\\}$ (defined by
the graph $G$). For $i=1,\ldots,n$, an NLC-width $(k+2)$ expression is
recursively defined as follows:

  1. 1.

If $m=1$, then $Y_{i}=X_{j_{1}}$. If $m>1$, then let

$Y_{i}=X_{j_{1}}\times_{I}\ldots\times_{I}X_{j_{m}}$

where $I=\\{(s,s)|s\in[k+1]\\}$. The graph $val(Y_{i})$ is the disjoint union
of graphs $val(X_{j_{1}}),\ldots,val(X_{j_{m}})$ where vertices with the same
label in different graphs are connected by an edge. Note that the relation $I$
uses only the labels $1,\ldots,(k+1)$. The label $(k+2)$ is exclusively for
vertices that will not be connected with other vertices in any further
composition step.

  2. 2.

If $r>0$, then let $Z_{i}$ denote a $NLC$ $(k+1)$-width expression that
defines a complete graph with $r$ vertices labeled by
$col(v_{l_{1}}),\ldots,col(v_{l_{r}})$. Here $r\leq k$ labels are distinct and
do not include the color $col(v_{i})$ of $v_{i}$.

  3. 3.

Now we define

$X_{i}=\begin{cases}\circ_{R}(Y_{i}\times_{S}Z_{i})&\text{if}\ m>0\
\text{and}\ r>0\\\ Z_{i}&\text{if}\ m=0\ \text{and}\ r>0\\\
\circ_{R}(Y_{i})&\text{if}\ m>0\ \text{and}\ r=0\end{cases}$

where,

$S=\\{(s,s)|s\in[k+1]-col\\{(v_{i})\\}\\}\cup\\{(col(v_{i}),s)|s\in[k+1]\\}$

and

$R(s)=\begin{cases}s&\text{if}\ s\neq col(v_{i})\\\ (k+2)&\text{if}\
s=col(v_{i})\end{cases}$

We refer the reader to [20] for a proof of correctness of the observation the
$NLC$-width $(k+2)$ expression $X_{n}$ defines the line graph of $G$. To see
that the NLC width expression $X_{n}$ is obtainable in L, we argue as follows:

  1. 1.

We obtain the tree decomposition of the graph $G$ in L via [15].

  2. 2.

Using Lemm 18, we can obtain the PEO of $G$ and also construct the Elimination
tree $T(G,o)$ in L.

  3. 3.

From $T(G,o)$ and $G$, we can obtain $m$ and $r$ and subsequently, each
element of $N^{+}(G,o,i)$ and $N^{-}(T(G,o),o,i)$ in L.

  4. 4.

We can compute the $(k+1)$-coloring of $G$, $col:V_{G}\to[k+1]$ in L via [15]
(Proof of Lemma 4.1).

We build the NLC width expression for the line graph of $G$ from the
elimination tree $T(G,o)$. The NLC width expression $X_{i}$ is defined for
each vertex of $T(G,o)$. This however depends only on $N^{-}(T(G,o),o,i)$ and
$N^{+}(G,o,i)$ which can be obtained in L. Along with the fact that tree
traversal via DFS is in L [10], we can obtain the NLC width expression for the
line graph of $G$ in L: We can represent the PEO tree using an expression
involving ’(’ and ’)’. Note that such an expression can be output by a
Logspace transducer. This gives the structure of our NLC width expression, and
now we can fill in this expression using the NLC width operations. This only
involves local computations: for example at a node $v_{i}$ of the tree, we
compute in Logspace $N^{-}(T(G,o),o,i),m$ and $N^{+}(G,o,i),r$ and get the
appropriate expressions based on the values of $m,r$ as given in item 3 of the
NLC width expression above. Since we build the NLC width expression over the
balanced elimination tree of constant arity and depth $O(\log{n})$ via Lemma
18 and every node in the elimination tree had atmost $k$ children, the parse
tree of the NLC width expression is also of height $O(\log{n})$. $\square$

###### Proposition 21

Given a graph $G$ of NLC-width at most $k$ by an NLC-width expression $Y$, we
can obtain the clique-width expression $X$ of $G$, where $|X|\leq 2k+2$ in L.

#### Proof:

For the NLC width-$(k+2)$ expression $X_{i}$ defined above, there is an
equivalent clique width $(2k+2)$ expression $X_{i}^{\prime}$. We prove by
induction on $i$: For $i=1$, there is a clique width-$(k+1)$ expression
$X_{1}^{\prime}$ because $val(X_{1})$ is just a graph on at most $k$ vertices
with labels from the set $[k+1]$. For $i>1$, an equivalent clique width
expression $Y_{i}^{\prime}$ for
$Y_{i}=X_{j_{1}}\times_{I}\ldots\times_{I}X_{j_{m}}$ is obtained from the
clique width expressions for $X_{j_{1}}^{\prime},\ldots X_{j_{m}}^{\prime}$
and $k$ auxiliary labels. This is because for $t=1,\ldots,m$, the vertices of
every $val(X_{j_{t}})$ are labeled by $k+1$ labels from $[k+2]$. Label
$col(u_{j_{t}})\in[k+1]$ is not used by the vertices of
$val(X_{j_{t}}^{\prime})$ and label $k+2$ is not involved in any edge
creation. The clique width expression $X_{i}^{\prime}$ for
$X_{i}=\circ_{R}(Y_{i}\times_{S}Z_{i})$ can finally be defined by clique width
expression for $Y_{i}$ and $k$ auxiliary labels because $val(Z_{i})$ has at
most $k$ vertices. Since all these changes are local, we can the convert the
NLC width $k+2$ expression to a clique width $2k+2$ expression by replacing
the corresponding subexpressions for NLC width by the ones for clique width,
to obtain the line graph of a bounded treewidth graph of treewidth at most $k$
in Logspace. $\square$

To sum up, these are the main preprocessing steps:

  1. 1.

Obtain a balanced binary tree decomposition of the input treewidth $k$ graph
$G$ in Logspace via Proposition 17 [15].

  2. 2.

Obtain the tree decomposition of $G^{\prime}$ (as required by Proposition 12
and specified by Lemma 13) from the tree decomposition of $G$.

  3. 3.

Perform a chordal completion of $G^{\prime}$ by adding edges to every bag.

  4. 4.

Obtain a PEO tree of $G^{\prime}$ of height $O(\log{n})$, where every vertex
has at most $k$ children via Lemma 18.

  5. 5.

Construct a NLC width $(k+2)$ expression for $L(G^{\prime})$ via Lemma 20

  6. 6.

From the NLC width $(k+2)$ expression, construct a clique-width $(2k+2)$
expression for $L(G^{\prime})$ via Proposition 21 (The surplus edges added
during the chordal completion are removed at this step).

##  4 The $\\#\mathsf{SAC}^{1}$ upper bound

Let $X$ be the clique-width $k$ expression for a labeled graph $G=(V,E,lab)$
such that $G$ is $\mbox{val}(X)$ and let $|V|=n$. Let $G$ be of clique-width
$k$. Hence by Definition 6, $G$ can be constructed from the graph with $n$
isolated labeled vertices, using at most $k$ labels. Notice that $X$ can be
viewed as a tree (we will refer to this as the parse tree of the clique-width
expression) with the $n$ isolated labeled vertices at the leaves and every
internal node is labeled with one of the operations
$o=\\{\bullet_{i},\oplus,\eta_{i,j},\rho_{i\to j}:i,j\in[k]\wedge i\neq j\\}$
To each internal vertex of the tree, we can associate a graph (possibly
disconnected) which is a subgraph of $G$, and at the root of the tree, we get
$G$ itself. The size of the tree is polynomial in $n$ and $k$. Our objective
in this section will be to count the number of Hamiltonian cycles in $G$, when
provided with the clique-width expression $X$. We will count along the parse
tree of the clique-width expression.

To this end, we call a subset of edges $E^{\prime}\subseteq E$ path-cycle
covers, if in the subgraph $G^{\prime}=(V,E^{\prime},lab)$ every vertex in
$G^{\prime}$ has degree at most $2$. To every such $G^{\prime}$, we associate
a multiset $M$ consisting of multisets $\langle lab(v_{1}),lab(v_{r})\rangle$
one each for every path/cycle $p=v_{1},\ldots,v_{r}$, $r\geq 1$, in
$G^{\prime}$, where $v_{1},v_{r}$ have degree at most $1$ in $G^{\prime}$ if
they exist ($p$ being a cycle otherwise). Let $F(X)$ be the set of all
multisets $M$ for all such subsets $E^{\prime}\subseteq E$.

Let $K$ be the set of all possible labels of the end points, in the labeled
graph produced at the output of each node in the parse tree. We refer to
elements of $K$ as _types_. Note that every $M$ consists of at most $|K|$
distinct _types_ and $F(X)$ has at most ${(n+1)}^{|K|}$ distinct multisets
each with at most $n$ multisets of size $2$. Here $K=K_{0}\uplus K_{1}\uplus
K_{2}$ is the set of distinct _types_ where $K_{2}$ accounts for types of the
form $\langle i,j\rangle$ (for $i\neq j$) corresponds to paths whose end
points are $i$ and $j$; $K_{0}$ for the empty type $\langle\rangle=\emptyset$
corresponds to a _cycle_ ; $K_{1}$ for types of the form $\langle i,i\rangle$
which could be either paths whose end points are both labeled $i$, or isolated
vertices with the label $i$. Observe that, $|K_{2}|=\binom{k}{2}$, $K_{1}=2k$
and $K_{0}=1$, where we distinguish between the cases of single isolated
vertex of label $i$ and multiple vertex paths with end points labeled $i$ for
technical reasons, leading to the extra factor of $2$. Our notation is
consistent with [16] in all cases except for the empty type, since in [16]
cycles are not permitted.

Our objective is to count the number of path-cycle covers, $\\#X[M]$,
corresponding to a multiset $M$ in the graph $val(X)$. In particular,

$\sum_{i,j\in[K]}{\\#X[M_{i,j}]}$

where $M_{i,j}=\langle\langle i,j\rangle\rangle$ is a multiset containing a
single type $\langle i,j\rangle$, yields the number of Hamiltonian paths with
end points coloured $i,j$ in $val(X)$. We denote by $\\#X$ the vector indexed
by $M$ and hence has ${(n+1)}^{K}$ entries where $\\#X[M]$ (where
$M\in[0,n]^{K}$) stores the count of the number of path/cycle covers of type
specified by $M$ in the graph $val(X)$. Let $C_{o}$ be a
${(n+1)}^{K}\times{(n+1)}^{K}$ matrix which for each pair of multisets
$M,M^{\prime}$ denotes the number of ways to form $M^{\prime}$ from $M$ under
an operation $o\in\\{\eta_{i,j},\rho_{i\to j}:i,j\in[k]\wedge i\neq j\\}$.
$C_{o}$ is defined uniquely for the two kinds of operations $\eta,\rho$ and is
independent of the input graph $\mbox{val}(X)$.

Then the following is an easy consequence of the definitions:

###### Proposition 22

The value of $\\#X$ is given by:

  1. 1.

if $X=\bullet_{i}$ then if $M=\langle\langle i,i\rangle\rangle$ then
$\\#X[M]=1$; else $\\#X[M]=0$.

  2. 2.

else if $X=X_{1}\oplus X_{2}$ then

$\\#X[M]=\sum_{M^{\prime}\in[0,n]^{K}:M^{\prime}\subseteq
M}{\\#X_{1}[M^{\prime}]\\#X_{2}[M\setminus M^{\prime}]}$

  3. 3.

else if $X=\rho_{i\to j}(X_{1})$ then $(C_{\rho_{i\to j}})^{T}\\#X_{1}$

  4. 4.

else $X=\eta_{i,j}(X_{1})$ then $(C_{\eta_{i,j}})^{T}\\#X_{1}$

#### Proof:

The first item is immediate. For the second, notice that each multiset of
types $M$ in the disjoint union of two graphs is formed by picking multisets
$M^{\prime},M^{\prime\prime}$ from the two graphs respectively and taking
their multi-union. Thus the number of distinct ways to form $M$ is obtained by
considering all possible decompositions of $M$ into sets
$M^{\prime},M^{\prime\prime}$ one from each graph. Since, this is a
decomposition $M^{\prime\prime}=M\setminus M^{\prime}$, the correctness of the
second item follows.

For the third and the fourth items, notice that we have a matrix $C$ such that
$C[M,M^{\prime}]$ is the number of ways to convert a multiset $M$ to a
multiset $M^{\prime}$. Thus the number of ways to form $M^{\prime}$ is to take
the product of $\\#X[M]C[M,M^{\prime}]$ and add up the products over all $M$.
This is the stated form in matrix notation. $\square$ Proposition 22 enables
us to prove the #SAC1 upper bound:

###### Lemma 23

For a bounded clique-width expression $X$, for every multiset of types, $M$,
the value $\\#X[M]$ of the number of path-cycle covers at any node along the
parse tree of the clique-width expression can be computed in #SAC0 where the
inputs to the #SAC0 circuit are entries of the matrix $C_{o}$ for
$o\in\\{\bullet_{i},\oplus,\eta_{i,j},\rho_{i\to j}:i,j\in[k]\wedge i\neq
j\\}$. The number of path-cycle covers in the input graph can hence be counted
in #SAC1.

#### Proof:

(of Lemma 23) We will use Proposition 22 for every node in the clique-width
decomposition $X$ to compute $\\#X[M]$ for every $M\in[0,n]^{K}$. For this we
will need the various matrices $C_{\rho_{i\to j}}$ (constructed in Proposition
24) and $C_{\eta_{i,j}}$ (constructed in Lemma 25). The correctness of this
circuit is clear from Proposition 22.

Next, we need to argue that the number of path-cycle covers in a bounded
clique-width graph is a function in #SAC1. We construct our #SAC1 circuit by
combining the #SAC0 circuits for every node in the parse tree as given by
Proposition 22. Notice that the resulting circuit is monotone (there are no
subtractions) and the value at every gate is at most a polynomial (in $n$)
many bits – this is because the number of path-cycle covers of an $n$-vertex
simple graph is at most an exponential function of $n$, which is representable
by $\mbox{{\sf poly}}(n)$ many bits. Thus the degree 888The degree of a
circuit is defined inductively as follows: All input variables (here these
correspond to the vertices/ edges in the graph) and constants have degree $1$.
The degree of a $\times$-gate is the sum of the degree of its children. The
degree of a $+$-gate is the maximum of the degrees of its children. of our
circuit must also be polynomial in $n$. The circuit obtained thus is of
arbitrary ($\mbox{{\sf poly}}(n)$) depth (since the parse tree is not
necessarily balanced), and hence a naive evaluation of such a circuit is in P.
However, by Proposition 11 this circuit can be depth-reduced to yield an upper
bound of $\mbox{{\sf\\#SAC}${}^{1}$}\ \subseteq\mbox{{\sf
NC}${}^{2}$}\subseteq\mbox{{\sf P}}\cap\mathsf{DSPACE}(\log^{2}{n})$.
$\square$

We now turn to the proof of our main Theorem 1

#### Proof:

(of Theorem 1) To count Euler tours on bounded treewidth graphs, we can count
Hamiltonian cycles in the line graph (via Lemma 13). Here we need to compute
the quantity $\\#X[\langle\emptyset\rangle]$ (since the empty multiset
represents a cycle, the path-cycle cover consisting of a single cycle must be
a Hamiltonian cycle itself). This follows from Lemma 23. $\square$

#### Proof:

(of Theorem 2) Hamiltonian cycles can be counted in #SAC1 by Lemma 23. Longest
Cycles (Paths) can be counted by considering multisets which consist of a
single cycle (respectively, path) and the minimum number of isolated vertices
respectively. To see this observe that for every cycle (respectively, path)
$C$ in the graph there is a multiset consisting of a single empty type
(respectively, non-empty type) and $|V(G)|-|V(C)|$ isolated vertices
respectively.

Counting cycle covers is equally simple. We just need to add up the counts for
multisets consisting only of empty types. This, is of course because an empty
type represents a cycle.

Perfect Matchings in bipartite graphs can therefore be counted by counting the
cycle covers in a biadjacency matrix. $\square$

###  4.1 Computing $C_{\rho_{i\to j}}$ and $C_{\eta_{i,j}}$

It is easy to compute $C_{\rho_{i\to j}}$ by the following,

###### Proposition 24

$C(\rho_{i\to j})$ is a $\\{0,1\\}$-matrix such that the entry corresponding
to $M_{1},M_{2}$ is equal to $1$ iff $\rho_{i\to j}(M_{1})=M_{2}$ (it is $0$
otherwise).

Let $W_{\vec{\alpha}}(t^{\prime})$ denote the number of ways to form one
path/cycle of type $t^{\prime}\in K$, given a multiset of paths/cycles
consisting of $\vec{\alpha}(t)$ paths/cycles for every type $t\in K$.

Next, we show how to compute $C_{\eta_{i,j}}$:

###### Lemma 25

There is a Logspace Turing machine that takes input
$W_{\vec{\alpha}}(t^{\prime})$ for every
$\vec{\alpha}\in[0,n]^{|K|},t^{\prime}\in K$ and outputs the entries of the
matrix $C_{\eta_{i,j}}$.

#### Proof:

We show that each entry can be computed in $\mathsf{DLOGTIME}$-uniform TC0
which is contained in L (see e.g. Vollmer [27]). Our main tool in this lemma
is an application of polynomial interpolation.

Notice that the rows/columns of the matrix $C$ are indexed by multisets of
_types_. Here a _type_ is an element from $K$. Therefore any such multiset can
be described by a vector $\vec{\alpha}$ of length $|K|$. Here each entry of
the vector represents the number of paths/cycles with that type inside the
multiset.

In the following we will consistently make use of the notation,
${\vec{z}}^{{\vec{a}}}$ to denote: $\prod_{i\in I}{z_{i}^{a_{i}}}$, where $I$
is the index set for both $\vec{z},\vec{a}$.

We have the following:

###### Lemma 26

$C[M,M^{\prime}]$ is the coefficient of
$\vec{x}^{\vec{c^{\prime}}}\vec{y}^{\vec{c}}$ in the following polynomial
$p_{\vec{c^{\prime}},\vec{c}}(\vec{x},\vec{y})$:

$\prod_{t,t^{\prime}\in
K}{\prod_{\vec{\alpha}\in[0,n]^{|K|}}{\sum_{\vec{d}_{\vec{\alpha}}}{\left(W_{\vec{\alpha}}(t^{\prime})x_{t^{\prime}}y_{t^{\prime}}^{\alpha(t)}\right)}}^{d_{\vec{\alpha}}(t^{\prime})}}$

To fix the notation we reiterate (items $1,2,3,4$ were defined previously and
we introduce some new notation in items $5,6,7,8,9$):

  1. 1.

$K$ is the set of types, where $|K|=\binom{k}{2}+2k+1$.

  2. 2.

$t,t^{\prime}\in K$ are types in the input, output multiset (respectively
$M,M^{\prime}$).

  3. 3.

A _allocation_ , $\alpha(t)\in[0,n]$ is the number of path-cycle covers of
type $t\in K$.

  4. 4.

$\vec{\alpha}\in[0,n]^{|K|}$ is a possible allocation vector indexed by $K$ in
which each entry is $\alpha(t)$.

  5. 5.

${d}_{\vec{\alpha}}(t^{\prime})\in[0,n]$ is the number of paths of type
$t^{\prime}$ formed from each allocation of type $\vec{\alpha}$.

  6. 6.

$\vec{d}_{\vec{\alpha}}\in[0,n]^{|K|}$ is a vector indexed by $K$ in which
each entry is one of ${d}_{\vec{\alpha}}(t^{\prime})$.

  7. 7.

$W_{\vec{\alpha}}(t^{\prime})$ is the number of ways to form a single
path/cycle of type $t^{\prime}$ from an allocation vector $\vec{\alpha}$.

  8. 8.

$\vec{W}_{\vec{\alpha}}$ is the vector indexed by $K$ in which each entry is
one of $W_{\vec{\alpha}}(t^{\prime})$.

  9. 9.

$\vec{c},\vec{c^{\prime}}\in[0,n]^{|K|}$ are vectors indicating number of
paths/cycles in $M,M^{\prime}$ respectively.

To see that Lemma 25 follows from Lemma 26 we use Kronecker substitution (see
Fact 1) to convert the multivariate polynomial
$p_{\vec{c^{\prime}},\vec{c}}(\vec{x},\vec{y})$ with $2|K|$ variables to a
univariate polynomial. Then we use Lagrange interpolation to find the
coefficient of an arbitrary term - in particular, the term corresponding to
$\vec{x}^{\vec{c^{\prime}}}\vec{y}^{\vec{c}}$ in TC0 (see e.g. Corollary 6.5
in [22]). $\square$

#### Proof:

(of Lemma 26) Consider the following expression:

$\sum_{\vec{d}\in\mathbf{D}}{\prod_{t^{\prime}\in
K}{\prod_{\vec{\alpha}\in[0,n]^{|K|}}{{W_{\vec{\alpha}}(t^{\prime})}^{d_{\vec{\alpha}}(t^{\prime})}}}}$
(1)

where the sum is taken over $\mathbf{D}\subseteq[0,n]^{|K|}$ consisting of all
$\vec{d}$’s satisfying:

$\displaystyle\forall
t^{\prime},\sum_{\vec{\alpha}\in[0,n]^{|K|}}{d_{\vec{\alpha}(t^{\prime})}}$
$\displaystyle=$ $\displaystyle c^{\prime}(t^{\prime})$ (2)
$\displaystyle\forall t,\sum_{\vec{\alpha}\in[0,n]^{|K|}}{\sum_{t^{\prime}\in
K}{{\alpha}(t){d_{\vec{\alpha}}}(t^{\prime})}}$ $\displaystyle=$
$\displaystyle{c}(t)$ (3)

###### Claim 27

$C[M,M^{\prime}]$ equals Expression (1).

#### Proof:

(of Claim) The Condition 2 above asserts that the number of paths/cycles of
type $t^{\prime}$ present in $M^{\prime}$ equals the sum over all
$\vec{\alpha}$ of the number of paths/cycles of type $t^{\prime}$ using
resources described by $\vec{\alpha}$; the Condition 3 is essentially a
conservation of resource equation for every type $t$ saying that all the
resources present in $M$ are used one way or the other in $M^{\prime}$.

Let $P,P^{\prime}$ be path-cycle covers represented by $M,M^{\prime}$
respectively such that we can obtain $P^{\prime}$ from $P$, i.e., $P^{\prime}$
is one possible path-cycle cover that can be obtained by an $\eta_{i,j}$
operation on $P$. This transformation is described by a unique $\vec{d}$. Then
the pair contributes precisely one to $C[M,M^{\prime}]$. On the other hand
$\\{P,P^{\prime}\\}$ satisfies (2),(3) so contributes exactly one to the
summand corresponding to the unique $\vec{d}$ in Expression 1. Since the pair
$P,P^{\prime}$ corresponds to a unique $\vec{d}$ and contributes exactly one,
the remaining summands would evaluate to zero. This can be explained by
observing that for all $\vec{d^{\prime}}\neq\vec{d}$, the number of paths of
type $t$ in $\vec{d^{\prime}}$ is not equal to the corresponding number in
$\vec{d}$ for atleast one $t$. Hence, they would contribute nothing to pair
$P,P^{\prime}$. $\square$

To complete the proof notice that the coefficient of
$\vec{x}^{\vec{c^{\prime}}}\vec{y}^{\vec{c}}$ is precisely expression 1 under
the conditions 2, 3. Now, we explain the reasoning behind expression 1. We
have $d_{\vec{\alpha}}(t^{\prime})$ paths of type $t^{\prime}$, each of which
can be formed in $W_{\vec{\alpha}}(t^{\prime})$ ways. Note that each of these
$d_{\vec{\alpha}}(t^{\prime})$ paths are formed from different $\vec{\alpha}$
(though the values of each of these $d_{\vec{\alpha}}(t^{\prime})$ vectors
$\vec{\alpha}$ is the same, they are inherently different as they are composed
of mutually exclusive vertex sets) and we consider each valid set of
$d_{\vec{\alpha}}(t^{\prime})$ vectors $\vec{\alpha}$, exactly once. Hence, we
multiply with ${W_{\vec{\alpha}}(t^{\prime})}^{d_{\vec{\alpha}}(t^{\prime})}$
to get the final count. $\square$

###  4.2 Calculation of ${W}_{\vec{\alpha}}(t^{\prime})$

${W}_{\vec{\alpha}}(t^{\prime})$ denotes the number of ways to form exactly
one type $t^{\prime}\in K$ in $M^{\prime}$ given a multiset of types
consisting of $\vec{\alpha}(t)$ types for every type $t\in K$ in $M$. For
simplicity of notation, let $t=\langle i,j\rangle\in K$ be a type and let
$\beta(i)=\alpha(\langle i,i\rangle)+\alpha^{(=0)}(\langle i,i\rangle)$ be the
total number of multisets of type $\langle i,i\rangle$, where $\alpha(\langle
i,i\rangle)$ (respectively $\alpha^{(=0)}(\langle i,i\rangle)$) denote paths
(respectively single nodes) labeled $\langle i,i\rangle$ in $\vec{\alpha}$.
Note that this distinction is not necessary for types where the end points
have different labels.

###### Lemma 28

For an operation $\eta_{i_{0},j_{0}}$ in the clique-width expression and for
any type $t^{\prime}=\langle i,j\rangle$, ${W}_{\vec{\alpha}}(t^{\prime})$ is
given by

${W}_{\vec{\alpha}}(\langle i,j\rangle)={[\\![{\langle
i,j\rangle}]\\!]}_{\vec{\alpha}}{W}_{\vec{\alpha}}$

where,

${W}_{\vec{\alpha}}=\binom{\alpha(\langle
i_{0},j_{0}\rangle)+\beta(i_{0})+\beta(j_{0})}{\alpha(\langle
i_{0},j_{0}\rangle)}\alpha(\langle
i_{0},j_{0}\rangle)!\beta(i_{0})!\beta(j_{0})!2^{\alpha(\langle
i_{0},i_{0}\rangle)+\alpha(\langle j_{0},j_{0}\rangle)}$

and, ${[\\![{\langle i,j\rangle}]\\!]}_{\vec{\alpha}}$ is given by 999In this
section, the notation $[\\![S]\\!]$ represents the Boolean value of the
statement $S$. ${[\\![t]\\!]}_{\vec{\alpha}}$ represents a Boolean valued
normalizing factor associated with the type $t$ under the allocation vector
$\vec{\alpha}$., 101010We adopt a convention in which types $t^{\prime}$
(other than the type $\langle i_{0},j_{0}\rangle$) not explicitly included in
the expressions have an allocation $\alpha_{t^{\prime}}$ equalling zero.

  * •

${[\\![{\langle a,b\rangle}]\\!]}_{\vec{\alpha}}=[\\![\beta(a)=\beta(b)]\\!]$

  * •

${[\\![{\langle
a,a\rangle}^{(=0)}]\\!]}_{\vec{\alpha}}={[\\![\alpha^{(=0)}_{a,a}=1\wedge\alpha(\langle
a,b\rangle)=0]\\!]}$

  * •

${[\\![{\langle
a,a\rangle}]\\!]}_{\vec{\alpha}}=[\\![\beta(a)=\beta(b)+1]\\!]$

  * •

${[\\![{\langle i,a\rangle}]\\!]}_{\vec{\alpha}}=[\\![(\alpha(\langle
i,a\rangle)=1\wedge\beta(a)=\beta(b))\vee(\alpha(\langle
i,b\rangle)=1\wedge\beta(a)=\beta(b)+1)]\\!]$

  * •

${[\\![{\langle i,j\rangle}]\\!]}_{\vec{\alpha}}=[\\![(\alpha(\langle
i,a\rangle)=1\wedge\alpha(\langle
a,j\rangle)=1\wedge\beta(a)=\beta(b)+1)\vee(\alpha(\langle
i,a\rangle)=1\wedge\alpha(\langle b,j\rangle)=1\wedge\beta(a)=\beta(b))]\\!]$

  * •

${[\\![{\langle i,i\rangle}]\\!]}_{\vec{\alpha}}=[\\![(\alpha(\langle
i,a\rangle)=2\wedge\beta(a)=\beta(b)+1)\vee(\alpha(\langle
i,a\rangle)=1\wedge\alpha(\langle i,b\rangle)=1\wedge\beta(a)=\beta(b))]\\!]$

  * •

${[\\![{\langle\emptyset\rangle}]\\!]}_{\vec{\alpha}}=[\\![\beta(a)=\beta(b)]\\!]$

where, $\\{a,b\\}=\\{i_{0},j_{0}\\}$ in some order.

#### Proof:

(of Lemma 28) Let’s look at ${W}_{\vec{\alpha}}(\langle a,a\rangle)$ in
detail. The ${W}_{\vec{\alpha}}(t)$ for all the other types $t$ are computed
similarly. Type $\langle a,a\rangle$ can be formed from the alternating
sequence of types $\langle a,a\rangle,\langle b,b\rangle,\langle
a,a\rangle\ldots\langle a,a\rangle$ interleaved with some (possibly zero)
$\langle a,b\rangle$ types. Thus, the equality $\beta(a)=\beta(b)+1$ should
hold while $\alpha(\langle a,b\rangle)$ can be any arbitrary non-negative
integer. When $\alpha(\langle a,b\rangle)=0$, the condition $\alpha(\langle
a,a\rangle)\geq 1\vee\alpha(\langle a,a\rangle)^{(=0)}>1$ should hold to
ensure that we are not considering the type $(\langle a,a\rangle)^{(=0)}$.

The number of ways of interspersing $\alpha(\langle a,b\rangle)$ types among
$\beta(a)+\beta(b)$ types is

$\binom{\alpha(\langle a,b\rangle)+\beta(a)+\beta(b)}{\alpha(\langle
a,b\rangle)}$

We can do this for all permutations of the $\langle a,b\rangle,\langle
a,a\rangle$ and $\langle b,b\rangle$ types hence we multiply by:
$\alpha(\langle a,b\rangle)!\beta(a)!\beta(b)!.$ Finally, we can flip the
orientation of paths of types $\langle a,a\rangle$ and $\langle b,b\rangle$ as
they are equivalent respectively to their flipped orientations. Note that
single nodes cannot be flipped. The proof is therefore completed by
multiplying with: $2^{\alpha(\langle a,a\rangle)+\alpha(\langle b,b\rangle)}.$
Lastly, a boundary case occurs when $\alpha(\langle a,b\rangle)=0$ where every
path can be flipped. Here, it is easy to see that in considering every
permutation of types while accounting for flips, we end up counting each path
twice (including its reverse). Hence, in this case we divide by $2$. $\square$

##  5 Conclusion and Open Ends

  * •

Can the #SAC1 bound be improved, to say, GapL or Logspace?

  * •

How far can the Euler tour result be extended? To bounded clique-width graphs?
Chordal graphs?

  * •

Can the determinant of bounded clique-width adjacency matrices be computed in
better than #SAC1? (it is known to be L-hard even for bounded tree-width
graphs from [6]).

##### Acknowledgements

We would like to thank K. Narayan Kumar, Aniket Mane, M. Praveen and Prakash
Saivasan for illuminating discussions regarding this paper. We would like to
thank Eric Allender, Vikraman Arvind, Nutan Limaye, Meena Mahajan, Pierre
McKenzie, Partha Mukhopadhyay, Ramprasad Saptharishi, Srikanth Srinivasan and
V.Vinay for reading a follow-up work that resulted from this paper and for
their comments, from which we discovered an error in a previous version of
this paper.Thanks are also due to anonymous referees for several comments that
helped improve the content and presentation of the paper. This work is
partially funded by a grant from the Infosys Foundation.

## References

  * [1] van T Aardenne-Ehrenfest and NG de Bruijn.  Circuits and trees in oriented linear graphs.  Simon Stevin: Wis-en Natuurkundig Tijdschrift, 28:203, 1951.
  * [2] Eric Allender, Jia Jiao, Meena Mahajan, and V. Vinay.  Non-commutative arithmetic circuits: Depth reduction and size lower bounds.  Theor. Comput. Sci., 209(1-2):47–86, 1998.
  * [3] Vikraman Arvind, Bireswar Das, Johannes Köbler, and Sebastian Kuhnert.  The isomorphism problem for k-trees is complete for logspace.  Information and Computation, 217:1–11, 2012.
  * [4] Nikhil Balaji and Samir Datta.  Tree-width and logspace: Determinants and counting Euler tours.  CoRR, abs/1312.7468, 2013.
  * [5] Nikhil Balaji and Samir Datta.  Bounded treewidth and space-efficient linear algebra.  CoRR, abs/1412.2470, 2014.
  * [6] Nikhil Balaji and Samir Datta.  Bounded treewidth and space-efficient linear algebra.  In Theory and Applications of Models of Computation, pages 297–308. Springer, 2015.
  * [7] Graham Brightwell and Peter Winkler.  Counting Eulerian circuits is #p-complete.  In ALENEX/ANALCO, pages 259–262, 2005.
  * [8] Prasad Chebolu, Mary Cryan, and Russell Martin.  Exact counting of Euler tours for generalized series-parallel graphs.  J. Discrete Algorithms, 10:110–122, 2012.
  * [9] Prasad Chebolu, Mary Cryan, and Russell Martin.  Exact counting of Euler tours for graphs of bounded treewidth.  CoRR, abs/1310.0185, 2013.
  * [10] Stephen A. Cook and Pierre McKenzie.  Problems complete for deterministic logarithmic space.  J. Algorithms, 8(3):385–394, 1987.
  * [11] Bruno Courcelle.  The monadic second-order logic of graphs. i. recognizable sets of finite graphs.  Information and computation, 85(1):12–75, 1990.
  * [12] David Cox, John Little, and Donal O’shea.  Ideals, varieties, and algorithms, volume 3.  Springer, 1992.
  * [13] B. Das, S. Datta, and P. Nimbhorkar.  Log-space algorithms for paths and matchings in k-trees.  Theory Comput. Syst., 53(4):669–689, 2013.
  * [14] Heinz-Dieter Ebbinghaus and Jörg Flum.  Finite model theory.  Perspectives in Mathematical Logic. Springer, 1995.
  * [15] Michael Elberfeld, Andreas Jakoby, and Till Tantau.  Logspace versions of the theorems of Bodlaender and Courcelle.  In FOCS, pages 143–152, 2010.
  * [16] Wolfgang Espelage, Frank Gurski, and Egon Wanke.  How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time.  In WG, pages 117–128. Springer, 2001.
  * [17] Uffe Flarup and Laurent Lyaudet.  On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth.  Theory of Computing Systems, 46(4):761–791, 2010.
  * [18] Qi Ge and Daniel Štefankovič.  The complexity of counting Eulerian tours in 4-regular graphs.  Algorithmica, 63(3):588–601, 2012.
  * [19] Martin Charles Golumbic.  Algorithmic graph theory and perfect graphs, volume 57.  Elsevier, 2004.
  * [20] Frank Gurski and Egon Wanke.  Line graphs of bounded clique-width.  Discrete Mathematics, 307(22):2734–2754, 2007.
  * [21] Frank Harary and C St JA Nash-Williams.  On Eulerian and Hamiltonian graphs and line graphs.  Canadian Mathematical Bulletin, 8:701–709, 1965.
  * [22] W. Hesse, E. Allender, and D.A.M. Barrington.  Uniform constant-depth threshold circuits for division and iterated multiplication.  Journal of Computer and System Sciences, 65:695–716, 2002.
  * [23] J. A. Makowsky, U. Rotics, I. Averbouch, and B. Godlin.  Computing graph polynomials on graphs of bounded clique-width.  In WG, pages 191–204, 2006.
  * [24] Sang-il Oum and Paul D. Seymour.  Approximating clique-width and branch-width.  J. Comb. Theory, Ser. B, 96(4):514–528, 2006.
  * [25] WT Tutte and CAB Smith.  On unicursal paths in a network of degree 4.  The American Mathematical Monthly, 48(4):233–237, 1941.
  * [26] V. Vinay.  Counting auxiliary pushdown automata.  In Structure in Complexity Theory, pages 270–284, 1991.
  * [27] Heribert Vollmer.  Introduction to circuit complexity - a uniform approach.  Texts in theoretical computer science. Springer, 1999.
  * [28] Egon Wanke.  k-nlc graphs and polynomial algorithms.  Discrete Applied Mathematics, 54(2):251–266, 1994.