USA: +1 725-224-8795 
Sign in
(Cycle cover 2-page limit – your solutions should fit on two sides of 1 page)
Your task is to give an algorithm which finds a cycle cover for a given graph or correctly reports that no cycle cover exists. An analysis of correctness along with the time and space complexity should also be included in your solution. You should base your algorithm on a reduction to bipartite matching. ( A cycle cover of a given directed graph G = (V, E) is a set of vertex-disjoint cycles that cover all the vertices. )
Solution guidelines For problems that require you to provide an algorithm, you must give the following:
1. a precise description of the algorithm in English and, if helpful, pseudocode,
2. a proof of correctness,
3. an analysis of running time and space.
Expert Answer
The problem is quite interesting,I am here describing the algortithm and the approach to the solution. The correctness of this algo can be checked via any example. Here goes:
First of all let’s transform the given directed graph G = (V,A) into a bipartite graph say B = ({V1,V2},E). Now for each vertex which belongs to the set of vertices, we create one vertex v1 ∈ V1 and one vertex v2 ∈ V2. Also, for each of the arc i.e. (u,v) ∈ A, we create the edge {u1,v2} ∈ set of edges.
Now each arc of our graph G has become an edge of the bipartite graph B. The direction of the arc in G is defined through the bipartition of vertices in B – V1 contains the tails of arcs and V2 contains their heads.
Now we claim that a disjoint-cycle cover for G exists if and only if B has a perfect matching. The reasoning follows that used in the proof of Berge’s theorem. If B has a perfect matching, then for each u1 ∈ V1, there is an edge matching it to some v2 ∈ V2; that edge corresponds to an arc (u,v) ∈ A. There
cannot be another selected edge including u1 (or v2) in the perfect matching, since that would give us two edges sharing an endpoint; in particular, this means that nothing in the matching can correspond to an arc (v,u). On the other hand, there must be an edge connecting v1 to something in V2, indicating the
selection of arc (v,…) and thus showing that each vertex v ∈V has indegree and outdegree 1 in the graph corresponding to the perfect matching. Since that is true of all vertices, the directed subgraph created by these edges is made of directed cycles and these cycles must be vertex-disjoint due to the nature of
a matching. This proves one half of the theorem, but the other half is now easy: if we have a disjoint cycle cover, then every vertex is covered and has exactly one incoming arc and one outgoing arc in the edge cover. Let v be such a vertex; because its indegree is one, there is some arc (u,v) ∈ A that is part of the cycle cover; and because its outdegree is 1, there is some arc (v,w) ∈ A that is also part of the cover.
To these two arcs correspond edges {u1,v2} and {v1,w2} in the bipartite graph, which, when selected, ensure that both copies v1 and v2 are matched. Hence a cover gives rise to a perfect matching.
This is a polynomial time algorithm, building the bipartite graph can be done in time O(V+E) and writing out the cycle cover C can be done in time O(E) because E is the upper bound for the size of M. By the analysis on the beginning of the task we can find the perfect matching with minimum weight in polynomial time, therefore the total algorithm is polynomial.
