3

Here I have a directed graph G. I need to to determine whether there exists a set of vertex-disjoint cycles so that each vertex belongs to a cycle.

I'm not sure if this can be done in polynomial time or if its NP-Complete? Can anyone atleast point me in the right direction?

jtaylor
  • 45
  • 6

1 Answers1

5

Split each vertex into an "in" vertex and an "out" vertex. Then a vertex-disjoint cycle cover corresponds to a perfect matching on this graph. You can find out the answer to your question as fast as you can find perfect matchings (i.e. polynomial time)

Hunter
  • 51
  • 1
  • 2
  • can you give an example? – bubakazouba May 31 '16 at 01:02
  • Nice solution. The idea beneath this idea is that we must assign to each node exactly one other node (the one it will point to if we leave only disjoint cycles). As an example, take the graph [0->1, 1->2, 2->1, 2->3], and let's call 0A the "output side of 0" and 0A the "input side of 0". We can then build a new graph [0A->1B, 1A->2B, 2A->1B, 2A->3B], which is bipartite. To draw it, put A nodes at the left and B nodes at the right. Next, apply a matching algorithm to see if there's a perfect matching. – Carlos Pinzón Jun 15 '18 at 23:44