World's most popular travel blog for travel bloggers.

# Determining if a digraph has any vertex-disjoint cycle cover

, ,
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?

###### 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

#### Post a Comment

Let us know your responses and feedback