Edge cover

Algorithms

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

Looking at the image it already becomes obvious why, for a given minimum edge cover ${\displaystyle C}$ and maximum matching ${\displaystyle M}$, letting ${\displaystyle c}$ and ${\displaystyle m}$ be the number of edges in ${\displaystyle C}$ and ${\displaystyle M}$ respectively, we have: ${\displaystyle |V|=c+m}$. Indeed, ${\displaystyle C}$ contains a maximum matching, so the edges of ${\displaystyle C}$ can be decomposed between the ${\displaystyle m}$ edges of a maximum matching, covering ${\displaystyle 2m}$ vertices, and the ${\displaystyle c-m}$ other edges that each cover one other vertex. Thus, as ${\displaystyle C}$ covers all of the ${\displaystyle |V|}$ vertices, we have ${\displaystyle |V|=2m+(c-m)}$ giving the desired equality.