3
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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))$.) $\endgroup$ – Lorenzo May 12 at 1:35
  • 1
    $\begingroup$ 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))$. $\endgroup$ – M. kanté May 13 at 9:35
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I thought that FPT meant specifically that the time was bounded by something like $f( tw) p(n)$, where $p$ is a polynomial and $tw$ is the tree width and n is the number of vertices, but asking the problem to be in $P$ for graphs of bounded tree width could include time bounds of the form $n^{tw}$. It seems like Courcelle's theorem says that there is an algorithm with time bound of the form $f(tw) p(n)$, so the problem was after all FPT, but $f$ is astronomical. Do you know if there are more practical algorithms for counting simple cycles for graphs of bounded tree width ? $\endgroup$ – Lorenzo May 12 at 1:38
  • $\begingroup$ f() is only required to a computation function in the definition of FPT. Better bounds may be achievable, but it requires more detailed analysis of its structures. $\endgroup$ – Rupei Xu May 12 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.