# 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 $M_1$ and $M_2$ on ground set S that have a common base, and a weight function $w: S \to {\mathbb R}_+$. Can we find in polynomial time the maximum weight k-element set that is a subset of a common base of $M_1$ and $M_2$?

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

1. J. Lakhal, L. Litzler, A polynomial algorithm for the extendability problem in bipartite graphs, Information Processing Letters 65 (1998), 11-16. DOI link
2. F. Zhang, H. Zhang, Construction for bicritical graphs and k-extendable bipartite graphs, Discrete Mathematics 306 (2006), 1415-1423. DOI link
3. 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