11
$\begingroup$

Is there a way to compute the size of a maximum matching in an unweighted bipartite graph more efficiently (e.g. faster) than computing a maximum matching?

It is a long shot but it is often an interesting problem to avoid throwaway computations like these.


Motivation

The problem I am trying to solve is match-2 where the two sets are of different sizes. I need to determine whether there is a matching that covers all the vertices from the smaller set. Knowing the size of the maximum matching would let me check if it is is equal to or smaller than the size of the smaller set (if such a thing is possible then whenever the result is "yes, there is a matching that covers the small set" you would effectively know what its size is but only in that case), but that is not strictly necessary: if there is a way to compute the answer without computing the size it is good for me.

$\endgroup$
3
$\begingroup$

I believe the best algorithm known is Hopcroft and Karp, "An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite Graphs", SIAM Journal of Computing 2:4 (1973), pp 225-231.

$\endgroup$

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.