pabloskimg's blog

Find an odd-length cycle in an undirected graph?
By pabloskimg, history, 7 years ago, In English

Hi everyone,

I'm struggling to come up with a correct and efficient algorithm that is able to find an odd-length cycle in an undirected graph. Any odd-length cycle is fine. I already know that a graph has an odd-length cycle if and only if it's not bipartite, but the problem is that this only tells you whether there is an odd-length cycle or not, but it doesn't find you an actual cycle in case there is one. One possible approach I came up with is to run DFS and every time there is a back-edge check if the cycle formed by the back-edge has an odd length, but the problem with this strategy is that it would only test a subset of the cycles, but not all possible cycles (think of complex cycles using many back edges in complex ways). Does any one know how to solve this problem?

Thank you guys in advance.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Check the comments here. The graph is directed in this blog but you can have an undirected graph as input (for each edge u->v add v->u).

→ Reply
»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Run a single DFS from any node (actually, any node which is contained in the non-bipartite connected component) and assign colors as you go. The first time you find a back-edge connecting two vertices of the same color, just unwind the node stack between these two vertices.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    Oh wow, you are right! I didn't think about it like that, but it makes total sense. If you try to bicolorate a graph with DFS but this is non-bipartite, then eventually you will get a contradiction with a back-edge connecting two vertices of the same color, with the corresponding loop having an odd-length (otherwise the graph would be bipartite which is a contradiction). But actually this solution is equivalent to the approach I mentioned in my question above: to run DFS and check the length of the loop defined by each back-edge (say, if the back-edge connects u and v, check (depth[u] — depth[v]) % 2 == 0), which I was not sure about its correctness before but since its equivalent to the bicoloration approach then I have a theoretical foundation to trust it now :D

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      One way of unwinding the node stack can be by using the parent array which one usually use to restore the bfs or dfs tree?

      → Reply