10
$\begingroup$

Problem: Give a linear-time algorithm to find an odd-length (directed) cycle in a directed graph. (Exercise 3.21 of Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.)

The related post@cs.stackexchange asks for the existence of an odd-length directed cycle in a digraph, which is solved by the following theorem@algs4.cs.princeton.edu.

Theorem: A directed graph has an odd-length directed cycle if and only if one (or more) of its strong components is non-bipartite (when treated as an undirected graph).

Thus, we can assume that the digraph is strongly connected.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
10
$\begingroup$

Let $G$ be strongly connected. Run BFS (!) from an arbitrary vertex $s$. BFS creates a leveled tree where level of a vertex $v$ is it's directed distance from $s$. If while running BFS you have never seen an edge $(u,v)$ that goes between levels of the same parity then $G$ is bipartite. The parity of the level of $u$ defines the partition that $u$ belongs to. Note that since every vertex is reachable from $s$, BFS will explore all the edges, so all of the edges would be going between the two blocks of the partition. Otherwise, you find an edge $(u,v)$ that goes between levels of the same parity. Suppose level of $u$ is even and level of $v$ is even. Then run DFS (or BFS) from $v$ to get a path to $s$. If this path is of even length then you get an odd directed cycle $s \rightsquigarrow u \rightarrow v \rightsquigarrow s$. If this path is of odd length then you get an odd directed cycle $s \rightsquigarrow v \rightsquigarrow s$. Analogous thing holds when level of $u$ is odd and level of $v$ is odd. Since this algorithm simply does 2 runs of BFS/DFS, it runs in linear time.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Thanks. This solution sounds very promising except that how to deal with the possibly repeated vertices in the obtained cycle. Consider the graph: $s = S \to A \to B \to C \to D \to E$ plus edges $D \to B$ and $E \to S$. $\endgroup$
    – hengxin
    May 20, 2016 at 8:35
  • 4
    $\begingroup$ The question does not ask for a simple cycle. In any case, once you have an arbitrary cycle of odd length, it's easy to find a simple cycle of odd length in linear time. Just traverse the cycle and see if the current vertex has already appeared. If it has, compute the length of the simple sub-cycle created by this vertex (can be done in $O(1)$ time by keeping track of the distance traveled in the cycle to reach a given vertex). If the sub-cycle is of odd length, return this subcycle, otherwise cut it out of your cycle (can be done in $O(1)$ time by reordering pointers), and continue. $\endgroup$
    – Denis Pankratov
    May 20, 2016 at 17:51
0
$\begingroup$

There actually is the answer to your question on a page you have linked: algs4.cs.princeton.edu: Directed Graphs. It's under Creative Problems (41.) and the trick is that you can construct a directed odd-length cycle from an undirected odd-length cycle in a strongly connected component.

  1. Odd-length directed cycle. Design a linear-time algorithm to determine whether a digraph has an odd-length directed cycle.

Solution. We claim that a digraph G has an odd-length directed cycle if and only if one (or more) of its strong components is nonbipartite (when treated as an undirected graph).

If the digraph G has an odd-length directed cycle, then this cycle will be entirely contained in one of the strong components. When the strong component is treated as an undirected graph, the odd-length directed cycle becomes an odd-length cycle. Recall that an undirected graph is bipartite if and only if it has no odd-length cycle.

Suppose a strong component of G is nonbipartite (when treated as an undirected graph). This means that there is an odd-length cycle C in the strong component, ignoring direction. If C is a directed cycle, then we are done. Otherwise, if an edge v->w is pointing in the "wrong" direction, we can replace it with an odd-length path that is pointing in the opposite direction (which preserves the parity of the number of edges in the cycle). To see how, note that there exists a directed path P from w to v because v and w are in the same strong component. If P has odd length, then we replace edge v->w by P; if P has even length, then this path P combined with v->w is an odd-length cycle.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I tend to treat this as a mathematical proof of the existence of an odd-length cycle instead of an algorithm to find one. Could you please explain how this proof can be translated into a linear time algorithm? $\endgroup$
    – hengxin
    May 17, 2016 at 13:33
  • $\begingroup$ Just as it is stated. Treat the graph as undirected, do the algorithm do check for bipartiteness. If it is bipartite, you are done, as no odd-length cycle exists. Otherwise, you will find an odd-length undirected cycle when you find two neighbouring nodes of the same color. Track back to the way you came until that node, these are your nodes in the undirected cycle. Then reconsider this cycle with directed edges. Either it already is a directed cycle, you're done. Otherwise, construct a cycle as described in the last paragraph by starting from a node adjacent to a "wrongly" directed edge. $\endgroup$
    – Philip Becker
    May 17, 2016 at 13:44
  • 2
    $\begingroup$ I think the difficulty in making this approach output an odd cycle is that you might need to fix more than one edge in your undirected odd cycle, in which case the running time becomes an issue. Using BFS (as I described in my answer) avoids this problem by identifying a single pair of vertices that needs to be fixed. $\endgroup$
    – Denis Pankratov
    May 17, 2016 at 20:56
  • 1
    $\begingroup$ Another issue that should be dealt with carefully is to avoid repeating vertices when concatenating those paths $P$s. $\endgroup$
    – hengxin
    May 18, 2016 at 1:28

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.