Let $G = (X+Y, E)$ be a bipartite graph, and suppose we want to find a maximum-cardinality matching in $G$. The Hopcroft-Karp algorithm runs in time $O(|E|\sqrt{|V|})$, where here $|V| = |X|+|Y|$. So if the graph is unbalanced and $|X|<|Y|$, the run-time is $O(|E|\sqrt{|Y|})$.

Is there an algorithm that attains a better worst-case runtime complexity for the case of an unbalanced bipartite graph, where $|X| \in o(|Y|)$? In particular, if $|X|$ is constant, is it possible to get run-time $O(|E|)$?


I just found the answer myself. In this paper:

Lyle Ramshaw, Robert E. Tarjan (2012). "On minimum-cost assignments in unbalanced bipartite graphs‏". Technical reports, HP research labs.

in section 5, the authors show that the Hopcroft-Karp algorithm in fact solves the following problem: given an integer $s$, find matchings with $1,\ldots,s$ edges. The run-time is $O(|E|\sqrt{s})$. In particular, if $|X|<|Y|$, we can take $s=|X|$ and the run-time is $O(|E|\sqrt{|X|})$.

| cite | improve this answer | |
  • 1
    $\begingroup$ I would suggest this link arxiv.org/abs/1904.11244 as an additional note on parameterized matching. It proves square root dependence on many parameters, i.e. $O(|E|\sqrt k)$, for different parameters $k$. $\endgroup$ – narek Bojikian Sep 16 '19 at 0:40

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.