graphs – Maximum cardinality matching of maximum weight

Given a graph, I want to find the matching with the maximum size in terms of edges, but among those matchings, given a real weight function on the edges, the one with the maximum weight. Is there an algorithm that can find such a matching in polynomial time?


To make things more concrete, here is an example bi-partite graph where the edge between 1->5 is poisoned; if you select it, you won’t get a matching of largest possible size (which is 3). But if we gave this poisoned edge a large weight, the maximal weight matching will be forced to pick it, making the size of the matching less than it possibly could be.


Side note: these questions are readily extended to the min edge cover, min weighted edge cover and “is there a polynomial time algorithm for min edge cover with minimal weight”.

enter image description here