I was wondering if there exists a way to compute the size of the maximum matching in a bipartite graph without having to compute the maximum matching itself. Any help or direction will be really appreciated.

Thank you.


You could find the minimum vertex cover. According to the König-Egerváry Theorem, the minimum vertex cover is the same size as a maximum matching of any bipartite graph.

  • $\begingroup$ The algos i looked for finding the minimum vertex cover are all based on first finding the maximum matching. $\endgroup$ – dilpreet023 Jul 7 '13 at 5:50
  • $\begingroup$ Sorry, I am not familiar then with any algorithm of the sort you are looking for, however the randomized algorithm explained in this paper runs pretty fast. $\endgroup$ – Shil B. Jul 7 '13 at 16:49

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.