1
$\begingroup$

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|)$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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|})$.

Improve this answer
$\endgroup$
1
  • 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
    Commented Sep 16, 2019 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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