# Maximum weight k-element subsets of perfect matchings

Given a bipartite graph *G* with edge weights, can we find in polynomial time a maximum weight *k*-element matching in *G* that can be extended to a perfect matching?

## Remarks

The matroid generalization of this question may also be interesting:

**Question.** *We are given two matroids [math]M_1[/math] and [math]M_2[/math] on ground set *S* that have a common base, and a weight function [math]w: S \to {\mathbb R}_+[/math]. Can we find in polynomial time the maximum weight *k*-element set that is a subset of a common base of [math]M_1[/math] and [math]M_2[/math]?*

Matching extensions are usually studied from another viewpoint. A graph *G* is **k-extendable** if every matching of size *k* can be extended to a perfect matching. For bipartite graphs, Lakhal and Litzler ^{[1]} gave a polynomial algorithm to determine the maximum value of *k* for which *G* is *k*-extendable. Later, Zhang and Zhang ^{[2]} gave a faster algorithm. However, the complexity of determining the maximum value of *k* for non-bipartite graphs is still unknown. There are several results on *k*-extendability for special graph classes; for a survey see Plummer ^{[3]}.

## References

- ↑ J. Lakhal, L. Litzler,
*A polynomial algorithm for the extendability problem in bipartite graphs*, Information Processing Letters 65 (1998), 11-16. DOI link - ↑ F. Zhang, H. Zhang,
*Construction for bicritical graphs and k-extendable bipartite graphs*, Discrete Mathematics 306 (2006), 1415-1423. DOI link - ↑ M. D. Plummer,
*Recent progress in matching extensions*, Building Bridges: Between Mathematics and Computer Science, M. Grötschel, G. O. H. Katona, eds., Springer (2008), 427-454. DOI link