Vertex cycle cover
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.
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.
If the cycles of the cover have no vertices in common, the cover is called vertex-disjoint or sometimes simply disjoint cycle cover. This is sometimes known as exact 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.[1][2]
If the cycles of the cover have no edges in common, the cover is called edge-disjoint or simply disjoint cycle cover.
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]
Properties and applications
Permanent
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. This fact is used in a simplified proof showing that computing the permanent is #P-complete.[5]
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.[6]
See also
- Edge cycle cover, a collection of cycles covering all edges of G
References
<templatestyles src="Reflist/styles.css" />
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1"..
- ↑ https://www.cs.cmu.edu/~avrim/451f13/recitation/rec1016.txt (problem 1)
- ↑ Garey and Johnson, Computers and intractability, GT13
- ↑ Ben-Dor, Amir and Halevi, Shai. (1993). "Zero-one permanent is #P-complete, a simpler proof". Proceedings of the 2nd Israel Symposium on the Theory and Computing Systems, 108-117.
- ↑ Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties (1999) Template:ISBN p.378, 379, citing Script error: No such module "citation/CS1"..
Script error: No such module "Check for unknown parameters".