If you have some bipartite graph with an adjacency matrix that represents the weights of the edges of that particular bipartite graph, then the Hungarian algorithm outputs a maximum weight transversal. However if you would apply this to a marriage problem, where you have a bipartite graph with an equal amount of men and women that need to be paired with each other for marriage where the weights would represent the combined 'happiness/utility' between the pair, then when applying the Hungarian algorithm it will give you a maximized sum of these weights, but this matching will not guarantee to be a stable matching. Now I have found that there exists an algorithm called the Gale-Shapely algorithm that always finds a stable matching when you have an equal number of vertices in both classes of a bipartite graph. But if I understood it correctly, a stable matching does not have to mean that the sum of the edge weights in the matching is maximized. Now my question becomes: Does there exist an algorithm that outputs a maximum weight transveral and has a stable matching? Or is this still an open problem in graph theory to find such an algorithm?

Correct me if my explanation above about the Hungarian algorithm and Gale-Shapely algorithm is wrong, I am not a mathematics students.

  • $\begingroup$ What do you mean by "Does there exist an algorithm that outputs a maximum weight transveral and has a stable matching?". In general, a maximum weighted matching need not be stable, so the two solutions are necessarily different. You have to pick which of the two best represents what you want $\endgroup$ – Federico Nov 27 '18 at 14:46
  • $\begingroup$ Yes so indeed as I understood a maximum weighted matching need not be stable. So suppose I would apply the Hungarian algorithm on a marriage problem. Where there are 5 men and 5 woman to be paired with each other where the edges represent the happiness of a men i and a woman j being paired with each other. Then the algorithm would output me a matching such that the sum of these weights is maximized, but the marriages not to be stable. So my question is, is there an algorithm that gives me a matching such that the it gives me a maximum weighted matching and is also a stable matching? $\endgroup$ – Kroko Nov 27 '18 at 14:50
  • 1
    $\begingroup$ Why do you think such a matching exists? Or are you asking for an algorithm that finds such a matching if one exists, and otherwise demonstrates that none exists? $\endgroup$ – saulspatz Nov 27 '18 at 14:52
  • $\begingroup$ So it has two give you two different solutions in general. Well, just run the Hungarian algorithm and then the Gale-Shapley algorithm $\endgroup$ – Federico Nov 27 '18 at 14:52
  • $\begingroup$ @salspatz I'm asking whether there exists an algorithm that finds me a matching M, such that M is a maximum weight matching and simultaneously stable. $\endgroup$ – Kroko Nov 27 '18 at 14:54

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.