Vertex Cycle Cover on:
[Wikipedia]
[Google]
[Amazon]
In
p.378, 379
citing .
In mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, a vertex cycle cover (commonly called simply cycle cover) of a graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discret ...
''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 ...
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 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 theoretical 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 p ...
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 with edges and vertices , a perfect matching in is a subset of , such that every vertex in is adjacent to exact ...
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 theoretical 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 p ...
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 with edges and vertices , a perfect matching in is a subset of , such that every vertex in is adjacent to exact ...
. However, adding the condition that each cycle should have length at least 3 makes the problem NP-hard
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
.
Properties and applications
Permanent
The permanent 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. It is an important tool in ...
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 (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...
. This fact is used in a simplified proof
Proof most often refers to:
* Proof (truth), argument or sufficient evidence for the truth of a proposition
* Alcohol proof, a measure of an alcoholic drink's strength
Proof may also refer to:
Mathematics and formal logic
* Formal proof, a co ...
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 areNP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
. The problems are not in complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...
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 a ...
. 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, a collection of cycles covering all edges of ''G''References
{{reflist NP-complete problems Computational problems in graph theory