Vertex 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.

Similar definitions exist for digraphs, in terms of directed cycles.

Finding a vertex-disjoint cycle cover of a directed graph can also be performed in polynomial time by a similar reduction to perfect matching.

[3] However, adding the condition that each cycle should have length at least 3 makes the problem NP-hard.

[4] The permanent of a (0,1)-matrix is equal to the number of vertex-disjoint cycle covers of a directed graph with this adjacency matrix.

The top graph is vertex covered by 3 cycles, and the cycles share both vertices (vertex 3) and edges (edge between 4 and 6).

The middle graph is covered by 2 cycles, and while there is a vertex overlap (vertex 3), no edges are used twice, making the covering an edge-disjoint.

The bottom graph has a covering where no vertex or edge is shared between the cycles, making the covering both edge-disjoint and vertex-disjoint.