I'm reading section 19.3 of Combinatorial Optimization by Schrijver where he details an algorithm for finding the min-weight edge cover. His method works for general graphs, but I'm particularly interested in bi-partite graphs. To find the min-weighted edge cover of a graph $G=(V,E)$ with a weight function $w: E \to R$, he first defines a clone graph, $\tilde{G} = (\tilde{V},\tilde{E})$. He then defines a larger graph, $G'=(V',E')$ whose set of vertices, $V'$ is the union of $V$ and $\tilde{V}$. The edges, $E'$ and weight function $w'(E')$ are as follows:

  1. $w'(e)=w'(\tilde{e})=w(e)$ for $e \in E$
  2. $w'(v,\tilde{v})=2\mu(v)$ for each $v \in V$ where $\mu(v)$ is the minimum weight edge of $G$ incident on $v$.

Now, we construct a minimum weight perfect matching, $M$ for $G'$ and this yields a minimum weight edge cover $F$ for $G$ once we replace any edge $v\tilde{v}$ in $M$ by an edge $e_v$ of minimum weight of $G$ incident on $v$.

Now, for the proof that this works, the author notes that $w(F)=\frac{1}{2}w'(M)$. So far so good.

Then, he states that any edge cover $F'$ for $G$ gives by reverse construction a perfect matching $M'$ in $G'$ with $w'(M')\leq 2w(F')$.

This is the part I don't understand. How does one go about constructing this new perfect matching, $M'$ and further prove the inequality?


1 Answer 1


Let $M$ be a maximal subset of $F'$ which is a matching. Any vertex $v$ not covered by $M$ must be covered by some edge $e_v=(v,w)$ in $F'$. Since $M$ is maximal, $w$ must be covered by $M$. It follows that if $v_1 \neq v_2$ are not covered by $M$, then $e_{v_1} \neq e_{v_2}$.

The matching $M'$ consists of the two copies of each edge in $M$, and of the edges $(v,\tilde{v})$ for each $v$ not covered by $M$. Edges of the first type have total weight $2w(M)$. Since $w(v,\tilde{v}) \leq 2w(e_v)$, edges of the second type have total weight at most $2w(F' \setminus M)$ (this crucially uses that $e_{v_1} \neq e_{v_2}$ for any $v_1 \neq v_2$ not covered by $M$). Hence $w(M') \leq 2w(F')$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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