In mathematics, a vertex cycle cover (commonly called simply cycle cover) of a graph G is a set of cycles which are subgraphs of G and contain all vertices of G.
Contents
If the cycles of the cover have no vertices in common, the cover is called vertex-disjoint or sometimes simply disjoint cycle cover. In this case the set of the cycles constitutes a spanning subgraph of G. A disjoint cycle cover of an undirected graph (if it exists) can be found in polynomial time by transforming the problem into a problem of finding a perfect matching in a larger graph.
If the cycles of the cover have no edges in common, the cover is called edge-disjoint or simply disjoint cycle cover.
Similar definitions may be introduced for digraphs, in terms of directed cycles.
Permanent
The permanent of a (0,1)-matrix is equal to the number of cycle covers of a directed graph with this adjacency matrix. This fact is used in a simplified proof of the fact that computation of the permanent is #P-complete.
Minimal disjoint cycle covers
The problems of finding a vertex disjoint and edge disjoint cycle covers with minimal number of cycles are NP-complete. The problems are not in complexity class APX. The variants for digraphs are not in APX either.