graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, 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 discre ...

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 b ...

s such that every

vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet *Vertex (computer graphics), a data structure that describes the position ...

of the graph is incident to at least one edge of the set. In

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...

, the minimum edge cover problem is the problem of finding an edge cover of minimum size. It is an

optimization problem In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables ...

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 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 ...

Definition

Formally, an edge cover of a graph ''G'' is a set of edges ''C'' such that each vertex in ''G'' is incident with at least one edge in ''C''. The set ''C'' is said to ''cover'' the vertices of ''G''. The following figure shows examples of edge coverings in two graphs (the set ''C'' is marked with red). : A minimum edge covering is an edge covering of smallest possible size. The edge covering number

\rho(G)

is the size of a minimum edge covering. The following figure shows examples of minimum edge coverings (again, the set ''C'' 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 , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...

: a matching ''M'' in which each vertex is incident with exactly one edge in ''M''. 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 ...

''K''_''m'',''n'' has edge covering number max(''m'', ''n'').

Algorithms

A smallest edge cover can be found in

by finding a

maximum matching Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is ad ...

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

; 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 optimiza ...

is an

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 ...

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 minimal edge Cover

C

and

M

, the following is true:

, V,  = , C,  + , M,

. Counting the edges in the minimal edge cover duplicates the edges in the

, summing to

2*, M,

(equaling the number of vertices in the matching), but also counts the unmatched vertices, because they have to be adjacent to an edge in the edge cover.

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