In mathematics, a vertex cycle cover (commonly called simply cycle cover) of a
graph ''G'' is a set of
cycle
Cycle, cycles, or cyclic may refer to:
Anthropology and social sciences
* Cyclic history, a theory of history
* Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr.
* Social cycle, various cycles in soc ...
s 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
Exact may refer to:
* Exaction, a concept in real property law
* ''Ex'Act'', 2016 studio album by Exo
* Schooner Exact, the ship which carried the founders of Seattle
Companies
* Exact (company), a Dutch software company
* Exact Change, an Ameri ...
vertex cycle cover. In this case the set of the cycles constitutes a
spanning subgraph
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
Symbols
A
B
...
of ''G''. A disjoint cycle cover of an undirected graph (if it exists) can be found in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
by transforming the problem into a problem of finding a
perfect matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
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 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
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
by a similar reduction to
perfect matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
. However, adding the condition that each cycle should have length at least 3 makes the problem
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
.
Properties and applications
Permanent
The
permanent
Permanent may refer to:
Art and entertainment
* ''Permanent'' (film), a 2017 American film
* ''Permanent'' (Joy Division album)
* "Permanent" (song), by David Cook
Other uses
* Permanent (mathematics), a concept in linear algebra
* Permanent (cy ...
of a
(0,1)-matrix
A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1) matrix is a matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets.
Matrix representati ...
is equal to the number of vertex-disjoint cycle covers of a
directed graph with this
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
. This fact is used in a simplified proof showing that computing 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
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
APX
In computational complexity theory, the class APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor ap ...
. The variants for digraphs are not in APX either.
[''Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties'' (1999)]
p.378, 379
citing .
See also
*
Edge cycle cover In mathematics, an edge cycle cover (sometimes called simply cycle cover) of a graph is a family of cycles which are subgraphs of ''G'' and contain all edges of ''G''.
If the cycles of the cover have no vertices in common, the cover is called ver ...
, a collection of cycles covering all edges of ''G''
References
{{reflist
NP-complete problems
Computational problems in graph theory