= Minimum-weight edge cover by matching savings
{title2=$\operatorname{OPT}=\sum_v c_v-\max_M\sum_{uv\in M}(c_u+c_v-w(uv))$}
For a finite <graph> without an <isolated vertex> and with nonnegative edge weights, put $c_v=\min_{e\ni v}w(e)$ and let $e_v$ attain this minimum. Define savings $p(uv)=c_u+c_v-w(uv)$ and baseline $B=\sum_vc_v$. A <maximum-weight matching> $M$ with weights $p$, allowing arbitrary <cardinality>, gives a minimum-weight <edge cover>
$$
F_M=M\cup\{e_v:v\text{ is unmatched by }M\}.
$$
It replaces separate cheapest coverage of two endpoints by a shared <edge> when doing so saves enough weight. Savings can be negative even though original costs are nonnegative; such <edges> need not be selected.
\b[Proof.] The construction covers all <vertices>. Duplicate selected <edges> are counted once, so nonnegative weights give $w(F_M)\leq B-p(M)$. Take an optimal <edge cover> and delete redundant <edges> to make it inclusion-minimal without increasing cost. Its components are <star graphs>, by the argument for the <edge cover and matching identity>. Select one <edge> from each component to obtain a <matching in a graph> $N$. A component with center $a$, selected leaf $b$ and other leaves $L$ contributes $w(ab)+\sum_{v\in L}c_v$ to $B-p(N)$, at most its total edge weight since $c_v\leq w(av)$. Thus $B-p(N)\leq\operatorname{OPT}$. Maximizing $p$ gives
$$
\operatorname{OPT}\leq w(F_M)\leq B-p(M)\leq B-p(N)\leq\operatorname{OPT},
$$
which proves both the construction and the displayed identity, including zero-weight cases. One call to a general-<graph> <maximum-weight matching> <polynomial-time algorithm> suffices, together with linear-time preprocessing. Choosing a <maximum cardinality matching> under these modified weights would impose an unnecessary constraint and can spoil the reduction.<Maximum-weight matching documentation by NetworkX>[max_weight_matching, maxcardinality=False, and Notes on polynomial running time]{ref}
Back to article page
