Cheap and Secure Web Hosting Provider : See Now

Determining if a digraph has any vertex-disjoint cycle cover

, , No Comments
Problem Detail: 

Given a digraph, determine if the graph has any vertex-disjoint cycle cover.

I understand that the permanent of the adjacency matrix will give me the number of cycle covers for the graph, which is 0 if there are no cycle covers. But is it possible to check the above condition directly?

Asked By : Shadow
Answered By : Yuval Filmus

Your problem is answered in the Wikipedia article on vertex-disjoint cycle covers. According to the article, you can reduce this problem to that of finding whether a related graph contains a perfect matching. Details can be found in a paper of Tutte or in recitation notes of a course given by Avrim Blum.

As a comment, in the graph-theoretic literature a vertex-disjoint cycle cover is known as a 2-factor.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/67044

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback