<p>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 <a href="https://www.cambridge.org/fr/academic/subjects/mathematics/logic-categories-and-sets/graph-structure-and-monadic-second-order-logic-language-theoretic-approach?format=HB&amp;isbn=9780521898331" rel="noreferrer">this book</a> or <a href="https://www.sciencedirect.com/science/article/pii/S0166218X08003363?via%3Dihub" rel="noreferrer">this paper</a></p>

CC BY-SA 4.0
2019-05-12T01:35:41.780Z
Thanks -- this answers my question. (For other readers: the relevant parts of the book are proposition 5.11 and theorem 6.56.) My impression is that the algorithm provided by Courcelle's theorem is impractical, in the sense that the dependency on the tree width grows astronomically fast. Do you know if there are more practical algorithms for counting simple cycles for graphs of bounded tree width? (E.g. with time bound $O(2^{O(tw)} p(n))$.)
Elle Najt
CC BY-SA 4.0
2019-05-13T09:35:18.957Z
I am not aware of any particular algorithm with running time $O(2^{tw}p(n))$. But, based on Courcelle's proof, I would not be surprised if it exists. Indeed, if you are able to construct a finite tree-automata of size $2^{O(tw)}$ for SC(X), then the Courcelle's construction will yield an algorithm with time complexity  $O(2^{tw}p(n))$.
M. kanté
CC BY-SA 4.0
2019-05-10T08:22:39.360Z
2019-05-10T08:22:39.360Z
M. kanté
<p>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:</p>

<p>I'll give an explicit <span class="math-container">$MSO_2$</span> formula for simple cycles. This is adapted from the <span class="math-container">$MSO_2$</span> formula for Hamiltonian cycles from section <span class="math-container">$7.4.1$</span> of Parametrized Algorithms by Cygan et. al. Let <span class="math-container">$G = (V,E)$</span> be a graph.</p>

<p>For <span class="math-container">$X \subseteq E$</span>, define: <span class="math-container">$$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'') ] ) $$</span></p>

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

<p>For <span class="math-container">$v \in V$</span> and <span class="math-container">$X \subseteq E$</span>, define: <span class="math-container">$$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) ) ] $$</span> </p>

<p>That is, <span class="math-container">$deg2(v,X)$</span> is true iff <span class="math-container">$v$</span> is degree two in <span class="math-container">$G[X]$</span>.</p>

<p>Finally, we define the <span class="math-container">$MSO_2$</span> formula: <span class="math-container">$$\phi(X) = connE(X) \wedge ( \forall_{v \in V} [ \exists_{e \in X} \text{inc}(e,v) \to \text{deg2}(v,X)]$$</span> </p>

<p><span class="math-container">$\phi(X)$</span> is true iff <span class="math-container">$X$</span> is the set of edges of a simple cycle of <span class="math-container">$G$</span>.</p>

<hr>

<p>The clearest formulation of Courcelle's theorem for counting that I found appears in this paper: <a href="http://www.labri.fr/perso/courcell/CoursMaster/CMR-Dam.pdf" rel="nofollow noreferrer">On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic</a>. 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 <span class="math-container">$w$</span>, the generating function <span class="math-container">$\sum_{ C \in SimpleCycles(G) } \prod_{e \in C} w(e)$</span> can be calculated FPT in the tree-width, assuming that arithmetic takes constant time.</p>

<p>A reference where one proof of such a theorem is clearly explained is <a href="https://www.sciencedirect.com/science/article/pii/019667749190006K" rel="nofollow noreferrer">this paper by Arnorg et al.</a></p>

<p>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 <a href="https://link.springer.com/chapter/10.1007/978-1-4757-2355-7_9" rel="nofollow noreferrer">Ebbinghaus, Flum, Thomas</a> to be a useful place to become sure about the meaning of second-order logic, which is treated only briefly in Flum and Grohe. <a href="https://link.springer.com/chapter/10.1007/978-1-4757-2355-7_9" rel="nofollow noreferrer">Ebbinghaus, Flum, Thomas</a> 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.</p>

CC BY-SA 4.0
2019-07-23T19:50:15.607Z
2019-07-27T19:49:51.697Z
2019-07-27T19:49:51.697Z
Elle Najt
<p><strong><em>Motivation:</em></strong>
Determining if a graph has a Hamiltonian cycle is <span class="math-container">$NP$</span>-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.</p>

<p>Counting the number of Eulerian circuits on undirected graphs is <span class="math-container">$\# P $</span> complete, but according <a href="http://drops.dagstuhl.de/opus/volltexte/2015/5649/pdf/35.pdf" rel="noreferrer">to this paper</a> it is in <span class="math-container">$P$</span> on graphs with bounded tree width.</p>

<p><a href="https://cstheory.stackexchange.com/questions/2396/counting-the-number-of-hamiltonian-cycles-in-cubic-hamiltonian-graphs">Counting the number of Hamiltonian cycles is <span class="math-container">$\#P$</span> complete</a>, but according to theorem 4.3 of <a href="https://arxiv.org/pdf/1211.1505.pdf" rel="noreferrer">this paper</a>, counting Hamiltonian cycles is in <span class="math-container">$P$</span> for graphs of bounded tree width.</p>

<p>Counting simple cycles is <span class="math-container">$\# P$</span> hard in general...</p>

<p><strong>Question:</strong> Is counting the number of simple cycles in <span class="math-container">$P$</span> on graphs of bounded tree width?</p>

<p><strong><em>Notes:</em></strong></p>

<ul>
<li><p>My inclination is to look at the separators + dynamic programming algorithms to see if one of them can be modified, but I'm <em>pretty</em> sure that if one can be straightforwardly modified to count simple cycles, then someone has done that already.</p></li>
<li><p>I do not see a way to express 'simple cycle' in <span class="math-container">$MSOL_2$</span> (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.</p></li>
<li><p>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 <span class="math-container">$w_a$</span> to be <span class="math-container">$1$</span>. Initialize <span class="math-container">$S = 0$</span>. Every time you replace 2 parallel edges with weights <span class="math-container">$w_e$</span> and <span class="math-container">$w_f$</span>, with a new edge called <span class="math-container">$ef$</span>, set <span class="math-container">$w_{ef} := w_e + w_f$</span> and <span class="math-container">$S := S + w_e w_f$</span>. Every time you replace to series edges <span class="math-container">$e$</span> and <span class="math-container">$f$</span> with a new edge called <span class="math-container">$ef$</span>, set <span class="math-container">$w_{ef} := w_e w_f$</span>. Apply replacements until you have <span class="math-container">$K_2$</span>. The value of <span class="math-container">$S$</span> at the end is the number of simple cycles, and the weight of the edge at the end is the number of simple <span class="math-container">$s$</span>-<span class="math-container">$t$</span> paths.) </p></li>
</ul>

<reference-request><graph-algorithms><time-complexity><counting-complexity><treewidth>
Is counting simple cycles in $P$ for graphs of bounded tree width?
Elle Najt
# Is counting simple cycles in $P$ for graphs of bounded tree width?

(Asked by: username_0 on 2019-05-09)

***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](http://drops.dagstuhl.de/opus/volltexte/2015/5649/pdf/35.pdf) it is in $P$ on graphs with bounded tree width.

[Counting the number of Hamiltonian cycles is $\#P$ complete](https://cstheory.stackexchange.com/questions/2396/counting-the-number-of-hamiltonian-cycles-in-cubic-hamiltonian-graphs), but according to theorem 4.3 of [this paper](https://arxiv.org/pdf/1211.1505.pdf), 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.)

**Tags:** reference-request, graph-algorithms, time-complexity, counting-complexity, treewidth


---

## 2 answers

### Answer by username_1 on 2019-05-10. Score: 8 | Accepted answer

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](https://www.cambridge.org/fr/academic/subjects/mathematics/logic-categories-and-sets/graph-structure-and-monadic-second-order-logic-language-theoretic-approach?format=HB&isbn=9780521898331) or [this paper](https://www.sciencedirect.com/science/article/pii/S0166218X08003363?via%3Dihub)

> **Comments:**
> **username_0**: Thanks -- this answers my question. (For other readers: the relevant parts of the book are proposition 5.11 and theorem 6.56.) My impression is that the algorithm provided by Courcelle's theorem is impractical, in the sense that the dependency on the tree width grows astronomically fast. Do you know if there are more practical algorithms for counting simple cycles for graphs of bounded tree width? (E.g. with time bound $O(2^{O(tw)} p(n))$.)  
> **username_1**: I am not aware of any particular algorithm with running time $O(2^{tw}p(n))$. But, based on Courcelle's proof, I would not be surprised if it exists. Indeed, if you are able to construct a finite tree-automata of size $2^{O(tw)}$ for SC(X), then the Courcelle's construction will yield an algorithm with time complexity  $O(2^{tw}p(n))$.  

---

### Answer by username_0 on 2019-07-23. Score: 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](http://www.labri.fr/perso/courcell/CoursMaster/CMR-Dam.pdf). 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.](https://www.sciencedirect.com/science/article/pii/019667749190006K)

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](https://link.springer.com/chapter/10.1007/978-1-4757-2355-7_9) 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](https://link.springer.com/chapter/10.1007/978-1-4757-2355-7_9) 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.


---

