9
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$

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.