patternMinor
Determining if a digraph has any vertex-disjoint cycle cover
Viewed 0 times
cycledeterminingdigraphvertexanyhasdisjointcover
Problem
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?
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?
Solution
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.
As a comment, in the graph-theoretic literature a vertex-disjoint cycle cover is known as a 2-factor.
Context
StackExchange Computer Science Q#67044, answer score: 3
Revisions (0)
No revisions yet.