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?

Improve this question
$\endgroup$
3
  • 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
    Commented May 4, 2019 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
    Commented May 4, 2019 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
    Commented May 4, 2019 at 7:35

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.