4
$\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$
8
$\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$
  • 1
    $\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 Najt 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
2
$\begingroup$

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.

$\endgroup$
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 Najt 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.