5
$\begingroup$

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:

enter image description here

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

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

$\endgroup$
1
$\begingroup$

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 arbitrary 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 There is no edge between vertices in $V-V(M_C)$. Otherwise we could make a larger matching by adding such an edge into $M_C$.

Observation 2 Every vertex in $V-V(M_C)$ must be covered by an edge which is incident to a matched edge.

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

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

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

The 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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Observation 3 is in fact a definition, where when multiple edges are incident to one vertex, you define which edge "covers" this vertex. $\endgroup$ – xskxzr Feb 27 at 5:40
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ "When it is 2 new vertices, the edge is part of the maximum matching." Why? In fact, whether a vertex is "new" depends on the order of edges you add to the edge cover, thus whether an edge covers two "new" vertices depends on the order, but whether an edge is part of the (or any since there may be multiple maximum matchings?) maximum matching does not depend on the order. $\endgroup$ – xskxzr Feb 27 at 5:36
-1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.