A simple reduction from maximum weight matching to maximum cardinality matching

Let mcm(m,n)mcm(m,n) and mwm(m,n,N)mwm(m,n,N) be the complexities of computing a maximum cardinality matching and a maximum weight matching, and let mcmbimcmbi, mwmbimwmbi be their counterparts for bipartite graphs, where m, n, and N are the edge count, vertex count, and maximum integer edge weight. Kao, Lam, Sung, and Ting (2001) [1] gave a general reduction showing mwmbi(m,n,N)=O(N⋅mcmbi(m,n))mwmbi(m,n,N)=O(N⋅mcmbi(m,n)) and Huang and Kavitha (2012) [2] recently proved the analogous result for general graphs, that mwm(m,n,N)=O(N⋅mcm(m,n))mwm(m,n,N)=O(N⋅mcm(m,n)).We show that Gabowʼs mwmbimwmbi and mwm algorithms from 1983 [3] and 1985 [4] can be modified to replicate the results of Kao et al. and Huang and Kavitha, but with dramatically simpler proofs. We also show that our reduction leads to new bounds on the complexity of mwm on sparse graph classes, e.g., (bipartite) planar graphs, bounded genus graphs, and H-minor-free graphs.

► We reduce maximum weight matching to maximum cardinality matching in general graphs. ► We dramatically simplify previous proofs of this reduction. ► Our results imply new bounds on maximum weight matching in special graph classes.