<p>For any $k$ there is a fairly simple $f(k)n^{\lceil k/2 \rceil+3}$ time algorithm by <a href="http://www.math.ias.edu/files/Vassilevska%20Subgraphs.pdf">Vassilevska Williams and Williams</a>.
The asymptotically fastest exact algorithm known AFAIK is <a href="http://arxiv.org/abs/1306.4111">Björklund, Kaski, and Kowalik</a>.</p>

CC BY-SA 3.0
2013-10-25T07:03:18.893Z
2013-10-25T07:11:17.823Z
2013-10-25T07:11:17.823Z
Andreas Björklund
<p>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.</p>

CC BY-SA 3.0
2013-10-24T09:42:12.277Z
2013-10-24T09:42:12.277Z
Michael Lampis
<p>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. </p>

<p>For $3 \leq k \leq 7$, one can count the $k$-cycles in $O(V^\omega)$ time, where $\omega &lt; 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$.</p>

<hr>

<p>[1] <a href="http://www-i7.informatik.rwth-aachen.de/~grohe/pub/flugro04b.pdf">Flum, Jörg, and Martin Grohe. "The parameterized complexity of counting problems." SIAM Journal on Computing 33.4 (2004): 892-922.</a></p>

<p>[2] <a href="http://perso.ens-lyon.fr/eric.thierry/Graphes2009/ayz97.pdf">Alon, Noga, Raphael Yuster, and Uri Zwick. "Finding and counting given length cycles." Algorithmica 17.3 (1997): 209-223.</a></p>

CC BY-SA 3.0
2013-10-24T08:43:08.097Z
2013-10-24T09:00:56.123Z
2013-10-24T09:00:56.123Z
Juho
<p>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.</p>

<graph-theory><graph-algorithms>
Finding number of cycles of length $k$ in a graph
Kumar
# Finding number of cycles of length $k$ in a graph

(Asked by: username_0 on 2013-10-24)

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.

**Tags:** graph-theory, graph-algorithms


---

## 3 answers

### Answer by username_3 on 2013-10-24. Score: 11 | Accepted answer

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.](http://www-i7.informatik.rwth-aachen.de/~grohe/pub/flugro04b.pdf)

[2] [Alon, Noga, Raphael Yuster, and Uri Zwick. "Finding and counting given length cycles." Algorithmica 17.3 (1997): 209-223.](http://perso.ens-lyon.fr/eric.thierry/Graphes2009/ayz97.pdf)


---

### Answer by username_2 on 2013-10-24. Score: 10

As username_3 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 by username_1 on 2013-10-25. Score: 8

For any $k$ there is a fairly simple $f(k)n^{\lceil k/2 \rceil+3}$ time algorithm by [Vassilevska Williams and Williams](http://www.math.ias.edu/files/Vassilevska%20Subgraphs.pdf).
The asymptotically fastest exact algorithm known AFAIK is [Björklund, Kaski, and Kowalik](http://arxiv.org/abs/1306.4111).


---

