Vertex cycle cover
Encyclopedia
In mathematics, a vertex cycle cover (commonly called simply cycle cover) of a graph
G is a set of cycle
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. In this case the set of the cycles constitutes a spanning subgraph of G.
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.
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.
. The problems are not in complexity class
APX
. The variants for digraphs are not in APX either.
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
G is a set of cycle
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
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. In this case the set of the cycles constitutes a spanning subgraph of G.
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
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
, in terms of directed cycles.
Permanent
The permanentPermanent
The permanent of a square matrix in linear algebra, is a function of the matrix similar to the determinant. The permanent, as well as the determinant, is a polynomial in the entries of the matrix...
of a (0,1)-matrix is equal to the number of cycle covers of a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
with this adjacency matrix
Adjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
. This fact is used in a simplified proof of the fact that computation of 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-completeNP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
. The problems are not in complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
APX
APX
In complexity theory the class APX is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant...
. The variants for digraphs are not in APX either.