1
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Taylor May 4 '19 at 5:57
  • $\begingroup$ @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? $\endgroup$ – user95224 May 4 '19 at 6:02
  • 1
    $\begingroup$ A quick search turns up theory.stanford.edu/~virgi/cs267/papers/cycles-ayz.pdf , which would be a starting point for a literature search. $\endgroup$ – Peter Taylor May 4 '19 at 7:35
  • $\begingroup$ Thanks, I'll have a look. $\endgroup$ – user95224 May 4 '19 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.