6
$\begingroup$

I have a rather basic question about the number of operations taken by the Hopcroft-Karp algorithm for finding a maximum matching in a bipartite graph. It is commonly reported as $O(m \sqrt{n})$ where $m$ is the number of edges in the graph and $n$ is the number of vertices(for example, see wikipedia or this book, among many examples - I cannot post more than two links due to reputation constraints).

What bothers me about this is that if $m$ is small (say $m=n^{1/4}$) this seems to require less than $n$ iterations, which is odd: surely you have to at least look at every node, i.e., just to see if it has any incident edges or not?

Having looked at Hopcroft and Karp's original paper, I see they quote a running time of $O((m+n)\sqrt{n})$ which makes more sense.

So my question is: what is the reason why the running time of Hopcroft-Karp is usually quoted as $O(m \sqrt{n})$? Does this reflect an assumption that the graph is connected (I never see this stated explicitly)?

|cite|improve this question
$\endgroup$
  • $\begingroup$ As a comment, big-oh notation measures the behaviour of a function as its arguments get larger. It's formally defined when there's only one variable, but here you have two. One of the dirty secrets of algorithm analysis is that there is no agreement on precisely what this means. When you say "if $m$ is small", someone might informally object that "well, big-oh only says what happens when $m$ gets large!" If that seems like a cop-out to you, you're not alone. See here for details: people.cis.ksu.edu/~rhowell/asymptotic.pdf $\endgroup$ – Pseudonym Jun 30 '14 at 2:11
  • $\begingroup$ @Pseudonym: the OP doesn't say $m$ is small. He says $m=O(n^{1/4})$, which goes to infinity. $\endgroup$ – Yves Daoust Oct 12 '15 at 7:12
9
$\begingroup$

The correct running time is indeed probably $O((m+n)\sqrt{n})$. However, this is a mouthful, and the expression $O(m\sqrt{n})$ looks nicer and is also more succinct. In most cases, $m \geq n/2$, since otherwise there is an isolated vertex. In fact, by finding isolated vertices, we can improve the running time of the algorithm to $O(n + m\sqrt{n})$.

An alternative way of stating the running time would be $O(m\sqrt{n})$, assuming $m \geq n$. The case of small $m$ is not so interesting (since then there are isolated vertices which can be eliminated), and so it is usually assumed that $m = \Omega(n)$.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Thank you! Another thought I had after writing the question is that perhaps the implicit assumption is that the graph is given as a list of edges. I think in that case, the running time is $O(m \sqrt{n})$. Could this be the assumption everyone is making when they write the time this way? $\endgroup$ – Javin Aldrecht Jun 30 '14 at 0:28
  • $\begingroup$ @Javin Right, that's another possible explanation. $\endgroup$ – Yuval Filmus Jun 30 '14 at 0:38

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.