Maximum weight k-element subsets of perfect matchings

From Egres Open
Jump to: navigation, search

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?


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].


  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