HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

How fast can we compute the size of maximum matching in an unweighted bipartite graph?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
fastcanthemaximumgraphcomputesizeunweightedbipartitehow

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#43696, answer score: 3

Revisions (0)

No revisions yet.