patternMinor
Solving the min edge cover using the maximum matching algorithm
Viewed 0 times
solvingthemaximumedgeminalgorithmusingcovermatching
Problem
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.
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.
Solution
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
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
Context
StackExchange Computer Science Q#110819, answer score: 7
Revisions (0)
No revisions yet.