# Maximum-cardinality matching in unbalanced bipartite graphs

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

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|})$$.
• 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$. – narek Bojikian Sep 16 '19 at 0:40