- reference-request graph-algorithms time-complexity counting-complexity treewidth
- Updated Tue, 07 Jun 2022 06:18:40 GMT

** 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.)

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

- +2 – 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))$.) — May 12, 2019 at 01:35
- +2 – 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))$. — May 13, 2019 at 09:35

External links referenced by this document:

- https://arxiv.org/pdf/1211.1505.pdf
- http://drops.dagstuhl.de/opus/volltexte/2015/5649/pdf/35.pdf
- 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
- https://www.sciencedirect.com/science/article/pii/S0166218X08003363?via=ihub

Local articles referenced by this article: