# Time complexity of an algorithm for finding a cycle of fixed length

I am considering the following algorithm for obtaining a cycle $$C_k$$ of fixed length $$k$$ in an undirected graph $$G$$. Assuming $$G$$ is in adjacency list form, say $$r \in G$$ is the root for a truncated DFS of $$G$$. In typical fashion, be sure to mark nodes which have been visited. Do not go beyond depth $$k-1$$. In this way, the (truncated) DFS finds all paths of length $$k-1$$ that start with $$r$$. Now, check that the last vertex in any such path is adjacent to $$r$$. If so, we have a path of length $$k$$ that starts an ends with $$r$$; i.e., a $$C_k$$.

Now for each $$v \in V$$, run the above procedure with $$v$$ as the root node.

Initially, I had supposed that all of the above runs in time $$O(|V|(|V| + |E|))$$, where $$O(|V| + |E|)$$ is the runtime of a complete DFS. Is this actually the case, or is the above modified DFS less efficient?

• The complexity analysis is fine, but the algorithm doesn't work. If every cycle in the graph has a chord you require luck to do the DFS in the right order. – Peter Taylor May 4 '19 at 5:57
• @PeterTaylor Ah, good point. Then for this algorithm to work we would not be permitted to mark, which makes it very inefficient, I think. Are you aware of any simple and reasonably efficient algorithms for this problem? – user95224 May 4 '19 at 6:02
• A quick search turns up theory.stanford.edu/~virgi/cs267/papers/cycles-ayz.pdf , which would be a starting point for a literature search. – Peter Taylor May 4 '19 at 7:35
• Thanks, I'll have a look. – user95224 May 4 '19 at 8:18