3
$\begingroup$

I want to write an algorithm to find whether a directed circuit whose length is odd exists in a strongly connected digraph.

Can anyone help me how to proceed with this problem???

$\endgroup$
  • 2
    $\begingroup$ What do you need this for? What have you tried? $\endgroup$ – Raphael Sep 12 '12 at 21:57
7
$\begingroup$

Firstly:

König's Theorem (1936): A graph is 2-colorable iff it has no circuits of odd length.

www-math.ucdenver.edu

Also:

  • A graph is bipartite if and only if it does not contain an odd cycle.
  • A graph is bipartite if and only if it is 2-colorable, (i.e. its chromatic number is less than or equal to 2).

wikipedia

So we see we are looking for a 2-colorable graph, or a bipartite graph. These are all the same thing.

Edit:

A digraph 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).

algs4.cs.princeton.edu

Since your graph is strongly connected, we can treat it as an undirected graph and test for bipartiteness using the regular testing algorithms.

The wikipedia article gives an example algorithm to test bipartiteness using Breadth First Search. A presentation explaining the algorithm is available from The University of Maryland website.

$\endgroup$
  • 3
    $\begingroup$ To check whether a graph is bipartite start with two empty lists $L$ and $R$, add a vertex to $L$, add its adjacent vertices to $R$, and so on making sure that no vertex is in $L$ when it's about to be added to $R$ and vice-versa. $\endgroup$ – saadtaame Sep 12 '12 at 20:08
  • 1
    $\begingroup$ Copying content from other sites as extensively as you did is not very meaningful. You might want to put the answer in your own words, and reference the sites for attribution/validation. $\endgroup$ – Raphael Sep 12 '12 at 21:58
  • 3
    $\begingroup$ This does not answer the posted question, which is about directed graphs. There are non-bipartite directed graphs with no odd directed cycles; consider the graph with vertices x,y,z and directed edges x→y, x→z, y→z. $\endgroup$ – JeffE Sep 12 '12 at 22:18
  • $\begingroup$ @Raphael I took out the large quote, and referenced the algorithm instead. This should suffice because the OP asked how to proceed. $\endgroup$ – Realz Slaw Sep 12 '12 at 22:42
  • $\begingroup$ @JeffE Good comment. A strongly connected graph can be treated as undirected wrt bipartiteness testing. I updated my answer accordingly. $\endgroup$ – Realz Slaw Sep 12 '12 at 22:42
1
$\begingroup$

A strongly connected digraph is bipartite if and only if it has no directed cycle of odd length. (See Digrpah thm 2.2.1)

So you can decompose your digraph into strongly connected components (SCC). And for each SCC, run a depth-first-search to see if it is bipartite. If all SCCs are bipartite, then the whole digraph has no cycle of odd length. Otherwise it has one such cycle. This is a linear time algorithm.

$\endgroup$

Your Answer

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

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