Vertex cycle cover

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. 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 may be introduced for digraphs, in terms of directed cycles.

Properties and applications

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.[3]

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.[4]

See also

References

  1. ↑ Tutte, W. T. (1954), "A short proof of the factor theorem for finite graphs", Canadian Journal of Mathematics 6: 347–352, doi:10.4153/CJM-1954-033-3, MR 0063008.
  2. ↑ http://www.cs.cmu.edu/~avrim/451f13/recitation/rec1016.txt (problem 1)
  3. ↑ 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.
  4. ↑ Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties (1999) ISBN 3-540-65431-3 p.378, 379, citing Sahni, Sartaj; Gonzalez, Teofilo (1976), "P-complete approximation problems", Journal of the ACM 23 (3): 555–565, doi:10.1145/321958.321975, MR 0408313..
This article is issued from Wikipedia - version of the Sunday, January 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.