Maximum-weight matching

Assign each edge $e$ a real benefit $w_e$. A maximum-weight matching maximizes ${\sum }_{e\in M}{w}_e$ over all matchings in a graph $M$; the empty matching in a graph is allowed. Setting every $w_e=1$ recovers a maximum cardinality matching, but otherwise the objectives can disagree.

On the same path graph $P_4$, give the middle edge benefit $3$ and each outer edge benefit $1$. The matching in a graph $\{(2,3)\}$ has total benefit $3$, while the two-edge matching in a graph $\{(1,2),(3,4)\}$ has total benefit $2$. Thus the smaller choice is the unique maximum-weight matching. If instead the requirement is to find a maximum cardinality matching and then maximize benefit among those, the outer edges must be chosen. Requiring a perfect matching before optimizing cost is another distinct problem, covered by minimum-weight perfect matching. With negative benefits a maximum-weight matching can even be empty, so it need not be a maximal matching.

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 }_v{c}_v$. A maximum-weight matching $M$ with weights $p$, allowing arbitrary cardinality, gives a minimum-weight edge coverIt 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.

Proof. The construction covers all vertices. Duplicate selected edges are counted once, so nonnegative weights give $w(F_M)\le 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\le w(av)$. Thus $B-p(N)\le \mathrm{OPT}$. Maximizing $p$ giveswhich 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.^[ref]

For nonnegative weights on a finite graph, scan edges in nonincreasing weight order, selecting each when it shares no endpoint with an already selected edge. This greedy matching is a factor-two approximation algorithm for maximum-weight matching.

Proof. Charge each optimal edge to itself if selected, and otherwise to an earlier selected edge that blocked it. The receiving edge weighs at least as much. Each selected edge receives at most two charges, since its two endpoints each meet at most one optimal edge. Summing proves the bound. Sorting takes $O(|E|\log |E|)$ time, followed by a scan that records which vertices are used.

The factor is sharp even for strictly positive weights. On a four-vertex path graph with consecutive weights $1,1+\epsilon ,1$, where $0<\epsilon <1$, the greedy matching weighs $1+\epsilon$ and the optimal matching in a graph weighs two. Their ratio tends to two as $\epsilon \downarrow 0$. For infinitely many sizes, use $k$ disjoint copies with $\epsilon =1/k$, $k\ge 2$. This example isolates the obstruction: a locally attractive edge can block two compatible edges.