In computer science, the minimum edge cover problem is the problem of finding an edge cover of minimum size.
It is an optimization problem that belongs to the class of covering problems and can be solved in polynomial time.
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).
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.
A smallest edge cover can be found in polynomial time by finding a maximum matching and extending it greedily so that all vertices are covered.
[1][2] 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; 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 is an NP-hard problem.
[1] Looking at the image it already becomes obvious why, for a given minimum edge cover
edges of a maximum matching, covering