Is counting simple cycles in $P$ for graphs of bounded tree width?

Question

Motivation: Determining if a graph has a Hamiltonian cycle is $NP$-hard in general. However, determining if there is a Hamiltonian cycle is in polynomial time on graphs of bounded tree width, either via some algorithm involving separators + dynamic programming, or by expressing the existence of a Hamiltonian cycle in a form that fits into Courcelle's theorem.

Counting the number of Eulerian circuits on undirected graphs is $\# P $ complete, but according to this paper it is in $P$ on graphs with bounded tree width.

Counting the number of Hamiltonian cycles is $\#P$ complete, but according to theorem 4.3 of this paper, counting Hamiltonian cycles is in $P$ for graphs of bounded tree width.

Counting simple cycles is $\# P$ hard in general...

Question: Is counting the number of simple cycles in $P$ on graphs of bounded tree width?

Notes:

• My inclination is to look at the separators + dynamic programming algorithms to see if one of them can be modified, but I'm pretty sure that if one can be straightforwardly modified to count simple cycles, then someone has done that already.

• I do not see a way to express 'simple cycle' in $MSOL_2$ (the best I can do is express disjoint unions of simple cycles). I'm not sure if there is a version of Courcelle's theorem for counting the set of solutions to a monadic second order logic formula -- I just got a surface level understanding of this theorem from wikipedia.

• I found a simple dynamic programming style algorithm to count simple cycles on series parallel graph, but it does not generalize to bounded tree width graphs. I assume that this is well known and in the literature somewhere. (Here is the algorithm: Initialize all edge weights $w_a$ to be $1$. Initialize $S = 0$. Every time you replace 2 parallel edges with weights $w_e$ and $w_f$, with a new edge called $ef$, set $w_{ef} := w_e + w_f$ and $S := S + w_e w_f$. Every time you replace to series edges $e$ and $f$ with a new edge called $ef$, set $w_{ef} := w_e w_f$. Apply replacements until you have $K_2$. The value of $S$ at the end is the number of simple cycles, and the weight of the edge at the end is the number of simple $s$-$t$ paths.)

Answer 1

A simple cycle is a connected set where every vertex has degree 2. Then you have a formula SC(X) stating X (a set of edges) is a simple cycle. You can see many versions of Courcelle's theorem for listing and counting. You can refer to this book or this paper

Answer 2

Here are some comments that may be useful for others in a similar position to me when I asked this question a few months ago:

I'll give an explicit $MSO_2$ formula for simple cycles. This is adapted from the $MSO_2$ formula for Hamiltonian cycles from section $7.4.1$ of Parametrized Algorithms by Cygan et. al. Let $G = (V,E)$ be a graph.

For $X \subseteq E$, define: $$connE(X) := \forall_{Y \subseteq V} ( (\forall_{s \in Y} \exists_{e \in X} \text{inc}(s,e)) \wedge \\ [[\exists_{u, v \in V} \exists_{e' \in X} \wedge \text{inc}(e',v) \wedge u \in Y \wedge v \not \in Y] \to \exists_{e'' \in X} \exists_{u' \in Y, v' \not \in Y} \text{inc}(u',e'') \wedge \text{inc}(v',e'') ] ) $$

For a set of edges $X$, $connE(X)$ is true iff $X$ induces a connected subgraph. This asserts that there is no set of nodes $Y$ in $G[X]$ such they are the nodes of a non-trivial connected component of $G[X]$. (The first clause checks that $Y \subseteq G[X]$.)

For $v \in V$ and $X \subseteq E$, define: $$deg2(v,X) = \exists_{e_1, e_2 \in X} [ e_1 \not = e_2 \wedge \text{inc}(v,e_1) \wedge \text{inc}(v, e_2) \wedge ( \forall_{e_3 \in X} (e_3 \not = e_1 \wedge e_3 \not = e_2) \to \lnot ( \text{inc}(v, e_3) ) ] $$

That is, $deg2(v,X)$ is true iff $v$ is degree two in $G[X]$.

Finally, we define the $MSO_2$ formula: $$\phi(X) = connE(X) \wedge ( \forall_{v \in V} [ \exists_{e \in X} \text{inc}(e,v) \to \text{deg2}(v,X)]$$

$\phi(X)$ is true iff $X$ is the set of edges of a simple cycle of $G$.

---

The clearest formulation of Courcelle's theorem for counting that I found appears in this paper: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Specifically, one looks in Section 2.1 for definitions and at Theorem 32 for the statement. Indeed this theorem shows much more, in particular that for any edge weights $w$, the generating function $\sum_{ C \in SimpleCycles(G) } \prod_{e \in C} w(e)$ can be calculated FPT in the tree-width, assuming that arithmetic takes constant time.

A reference where one proof of such a theorem is clearly explained is this paper by Arnorg et al.

Section 4.2. of Flum and Grohe "Fixed Parameter Tractability" gives an useful overview of the logic background, but I read the first 6 chapters of "Mathematical Logic for Mathematicians" (Mileti) first, without which I would have floundered in understanding these concepts. I found the chapter "Extensions of First-Order Logic" in Ebbinghaus, Flum, Thomas to be a useful place to become sure about the meaning of second-order logic, which is treated only briefly in Flum and Grohe. Ebbinghaus, Flum, Thomas was also a useful resource for becoming more familiar with basic logic. Flum and Grohe provide a proof of Courcelle's theorem (for decision problems) as well.

Answer 3

You may get confused. P here actually means Fixed-parameter tractable. Counting the Hamiltonian cycles of a graph is fixed-parameter tractable when parameterized by the tree-width of the graph. You can learn more about the parameterized counting complexity in this paper https://people.csail.mit.edu/rrw/presentations/counting-k-paths.pdf

Daniel Marx gave an excellent plenary talk towards this topic in SODA 2019, you can check his website for slides.