Question

Give a linear-time algorithm to find an odd-length cycle in a directed graph. (Hint: First solve this problem under the assumption that the graph is strongly connected.)

Answer 1

Let the graph be denoted as G. We can find out if has odd cycle in two ways.

Method 1:

Here we have to note that a directed graph has an odd-length directed cycle if and only if one (or more) of its strong components is non-bipartite.

Indirectly, if we can check whether the graph is bipartite, it means no odd cycle exists in graph. If it is not a bipartite graph it simply implies it can have odd cycle.

A graph is bipartite if and only if it is 2 colorable.

Algorithm steps:

1. Run DFS from an arbitrary node N.
2. Color the current vertex with the one different from its parent.
3. If you come across the previously colored vertex with the same color , then G is not bipartite and has odd cycle.
4. If you come across the previously colored vertex with different color, G has even length cycle.

Method 2:

In this method , we keep a track of all nodes visited.

Algorithm steps:

1. Run a BFS from an arbitrary node N.
2. Store all the nodes visited in a HashSet .
3. Check if the node is already exists in Hashset. If it exists go to step 4. Else go to step 5.
4. Coming across the same node means cycle exists. Find the length of the sub cycle by traversing again to keep track of distance traveled. If it is of even length ,go to step 5.
5. Repeat the process till either all the nodes in the graph are traversed or encountered a cycle.

Both the methods take the linear time complexity that O(n) since we are traversing the whole graph. n is number of nodes in G.