(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. )


We can use DFS(Depth First Traversal) to find out the cycle cover of the given graph. Detection of the cycle can be done on the bases of given points:

1) If in a graph "back edge" is present then there will be a cycle cover. Here back edge is basically a edge that is from a node to itself again. Its also called the selfloop.
2) With the help of Depth first traversal, we can check for the back edges.
3) For the detection of the back edges its required to keep a track of vertices that are currently in the recurssion stack of the function for Depth First Traversal.
4) During the traversal if we reach the vertex that is already present in the recursion stack then it means that a cycle is present.
5) So we can say that the edge that basically connect current vertex in the recursion stack is called the back edge and thats the cause of cycle cover.
6) If during traversal no back edge is found then there is no cycle cover.