Finding number of cycles of length $k$ in a graph

Question

We have $f(k) n^3$ time algorithm to determine whether a graph $G$ has a cycle of length exactly $k$. How can we find how many such $k$-cycles are present in $G$ using the same or any other algorithm.

Answer 1

When $k$ is part of the input, the problem of deciding if $G$ contains a simple cycle of length $k$ is NP-complete. For every fixed $k$, the problem can be solved in either $O(VE)$ time, or $O(V^\omega \log V)$ time. Flum and Grohe [1] showed that counting cycles and paths of length $k$ in both directed and undirected graphs, parameterized by $k$, is #W[1]-complete.

For $3 \leq k \leq 7$, one can count the $k$-cycles in $O(V^\omega)$ time, where $\omega < 2.376$ is the exponent of matrix multiplication. This is the result of Alon, Yuster and Zwick [2]. The paper also contains methods for finding simple cycles of length exactly $k$, where $k \geq 3$.

---

[1] Flum, Jörg, and Martin Grohe. "The parameterized complexity of counting problems." SIAM Journal on Computing 33.4 (2004): 892-922.

[2] Alon, Noga, Raphael Yuster, and Uri Zwick. "Finding and counting given length cycles." Algorithmica 17.3 (1997): 209-223.

Answer 2

As Juho pointed out, the problem is known to be #W[1]-complete by the work of Flum and Grohe. However, there does exist a randomized approximation scheme which runs in FPT time and returns an estimate which is a $(1+\epsilon)$ factor away from the correct solution with high probability. See "Approximation Algorithms for Some Parameterized Counting Problems", by Arvind and Raman, ISAAC 2002.

Answer 3

For any $k$ there is a fairly simple $f(k)n^{\lceil k/2 \rceil+3}$ time algorithm by Vassilevska Williams and Williams. The asymptotically fastest exact algorithm known AFAIK is Björklund, Kaski, and Kowalik.