Solving the min edge cover using the maximum matching algorithm

Question

To solve an instance of an edge cover, we can use the maximum matching algorithm.

Edge Cover: an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set [from Wikipedia].

Maximum matching: a matching or independent edge set in a graph is a set of edges without common vertices [from Wikipedia].

For example to find the min edge cover of the example below, we can:

1- Find a maximum matching.

2- Extending it greedily so that all vertices are covered.

The image below present this solution:

My question is why this reduction works, is there a proof for that result? or at least an intuition to help me undestand!

How can be sure that the final solution is the min edge cover of the graph and there is no other edge cover with size less than the founded solution.

Answer 1

Assume, w.l.o.g., that G=(V,E) is a graph without isolated vertex. Let's denote by $\mathcal{A}$ the algorithm you describe in your question. We seek to prove that given $G$, $\mathcal{A}$ outputs a minimum edge cover. Before we do that, it can be benifical to make some simple observations. First, both edge cover and matching are set of edges, and the subset of an edge cover can be a matching. Given a minimal edge cover $C$(not necessarily the minimum), we denote by $M_C \subseteq C$ the maximum matching containing in $C$ . Note that $M_C$ is the matching of maximum size whose edges are all in $C$. We call any edge in $M_C$ the matched edge. We use $V(M_C)$ to denote the vertices of edges in $M_C$

Observation 1 Every vertex in $V\setminus V(M_C)$ must be covered by an edge which is incident to an edge in $M_{C}$. Otherwise we could find a larger matching in $C$.

Observation 2 Every edge in $C$ covers 1 or 2 vertices. Specifically, an edge in $M_C$ covers two vertices, an edge in $C\setminus M_C$ covers 1 vertex.

Theorem 1 $|V|=|C|+|M_C|$

Proof $\;$ By observation 2 and the definition of edge cover, we have $2|M_C|+|C-M_C|=|V|$.

By observation 1 we have that algorithm $\mathcal{A}$ outputs a minimal edge cover. Then he correctness of algorithm $\mathcal{A}$ is obvious from theorem 1: when $|M_C|$ is maximized, $|C|$ is minimized since they sum to a fixed number $|V|$. In such situation, theorem 1 is called Gallai’s theorem

Answer 2

Every edge connects exactly two vertex, thus for $n$ vertices, the minimum edge cover uses between $n/2$ and $n$ edges. In fact every new edge you add to your subset covers either 1 new vertex, or 2 new vertices. When it is 2 new vertices, the edge is part of the maximum matching.

$k$ the number of edge needed for the cover is:

$k = n - a$

with $a$, the number of edges in the maximum matching (at most $a = n/2$).

Starting from the maximum matching, you cannot have any new edge covering 2 vertices (or a re-arrangement of edges that augment $a$). Either it would not be a "maximum matching".

The greedy part of the algorithm just collects the 1 vertex covering edges needed to complete the problem.

Answer 3

Suppose a maximum matching, of size r say, is removed from the graph, along with the endpoints of edges of the matching and edges incident to these endpoints. Suppose k vertices remain. These k vertices form an independent set (otherwise the graph would have had a larger matching, a contradiction)and so covering them requires k separate edges. So a minimum edge cover has size r+k.

Intuitively, you want a maximum matching because then you get to cover the most number (ie two) of distinct vertices with each edge of the cover, thereby using few edges.