Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer
The algos i looked for finding the minimum vertex cover are all based on first finding the maximum matching. – dilpreet023 Jul 7 '13 at 5:50
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. – Shil B. Jul 7 '13 at 16:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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