A simple reduction from maximum weight matching to maximum cardinality matching

作者：Pettie S^*

来源：Information Processing Letters, 2012, 112(23): 893-898.

DOI：10.1016/j.ipl.2012.08.010

• Graph algorithms
• Maximum matching

Let MCM(m, n) and MWM(m. n. N) be the complexities of computing a maximum cardinality matching and a maximum weight matching, and let MCMbi, MWMbi 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) = 0(N . MCMbi(m, n)) and Huang and Kavitha (2012) [2] recently proved the analogous result for general graphs, that MWM(m. n, N) = 0(N . MCM(m,n)).
We show that Gabow's MWMbi 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.

• 出版日期2012-12-15