In
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, an edge 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 ...
is a set of
edge
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* Edge device, an entry point to a computer network
* Adobe Edge, a graphical development application
* Microsoft Edge, a web browser developed by ...
s such that every
vertex of the graph is an endpoint of at least one edge of the set.
In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, the minimum edge cover problem is the problem of finding an edge cover of minimum size. It is an
optimization problem
In mathematics, engineering, computer science and economics
Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goo ...
that belongs to the class of
covering problem
In combinatorics and computer science, covering problems are computational problems that ask whether a certain combinatorial structure 'covers' another, or how large the structure has to be to do that. Covering problems are minimization problems a ...
s and can be solved 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 ...
.
Definition
Formally, an edge cover of a graph is a set of edges such that each vertex in is incident with at least one edge in . The set is said to ''cover'' the vertices of . The following figure shows examples of edge coverings in two graphs (the set is marked with red).
:
A minimum edge covering is an edge covering of smallest possible size. The edge covering number is the size of a minimum edge covering. The following figure shows examples of minimum edge coverings (again, the set is marked with red).
:
Note that the figure on the right is not only an edge cover but also a
matching. In particular, it is 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 ...
: a matching in which every vertex is incident with exactly one edge in . A perfect matching (if it exists) is always a minimum edge covering.
Examples
* The set of all edges is an edge cover, assuming that there are no degree-0 vertices.
* The
complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory ...
has edge covering number .
Algorithms
A smallest edge cover 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 finding a
maximum matching and extending it greedily so that all vertices are covered.
[ In the following figure, a maximum matching is marked with red; the extra edges that were added to cover unmatched nodes are marked with blue. (The figure on the right shows a graph in which a maximum matching is 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 ...
; hence it already covers all vertices and no extra edges were needed.)
:
On the other hand, the related problem of finding a smallest vertex cover
In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.
In computer science, the problem of finding a minimum vertex cover is a classical optimizat ...
is an 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 ...
problem.[, p. 79, uses edge cover and vertex cover as one example of a pair of similar problems, one of which can be solved in polynomial time while the other one is NP-hard. See also p. 190.]
Looking at the image it already becomes obvious why, for a given minimum edge cover and maximum matching , letting and be the number of edges in and respectively, we have: . Indeed, contains a maximum matching, so the edges of can be decomposed between the edges of a maximum matching, covering vertices, and the other edges that each cover one other vertex. Thus, as covers all of the vertices, we have giving the desired equality.
See also
* Vertex cover
In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.
In computer science, the problem of finding a minimum vertex cover is a classical optimizat ...
* Set cover
The set cover problem is a classical question in combinatorics, computer science, operations research, and Computational complexity theory, complexity theory.
Given a Set (mathematics), set of elements (henceforth referred to as the Universe ( ...
– the edge cover problem is a special case of the set cover problem: the elements of the ''universe'' are vertices, and each ''subset'' covers exactly two elements.
Notes
References
*
* {{citation
, last1=Garey , first1=Michael R. , authorlink1=Michael R. Garey
, last2=Johnson , first2=David S. , authorlink2=David S. Johnson
, year = 1979
, title = Computers and Intractability: A Guide to the Theory of NP-Completeness
, publisher = W.H. Freeman
, isbn=0-7167-1045-5
.
Computational problems in graph theory
Polynomial-time problems
Covering problems