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

  • $\begingroup$ @D.W. your edits are fine and make the question more direct. However, I didn't intend the question to be specifically about bipartite graphs. It just so happens that the example I gave involved a bipartite graph; but that was incidental. $\endgroup$ – Rohit Pandey Nov 27 '20 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.