In the last 2 paragraphs of the paper about Hopcroft–Karp algorithm to find the maximum cardinality matching in bipartite graph:


The execution time of a phase is O(m+n), where m is the number of edges in G, and n is the number of vertices. Hence the execution time of the entire algorithm is O((m+n)s), where s is the cardinality of a maximum matching.

If G has n vertices then m <= n^2 / 4 and s < n / 2 so that the execution time is bounded by O(n^(5/2)).

I don't understand given:

m <= n^2 / 4
s <= n / 2

why they concluded:

O((m+n)s) = O(n^(5/2))

Shouldn't it be:

O((m+n)s) = O(n^3)

Any idea?

  • 1
    $\begingroup$ This is explained on Wikipedia. Remember to research the problem yourself before asking here. $\endgroup$ – David Richerby Jan 3 '14 at 16:01
  • $\begingroup$ Thanks. I had referred this Wikipedia before, but was not sure if I should trust Wikipedia or the original algorithm's paper. $\endgroup$ – An Phung Jan 3 '14 at 16:18
  • $\begingroup$ Corollary 5 of the paper says there are only $O(\sqrt{s})$ phases. $\endgroup$ – David Richerby Jan 3 '14 at 16:23
  • $\begingroup$ That must be it. I think they forgot to draw the $\sqrt{}$ symbol. $\endgroup$ – An Phung Jan 3 '14 at 16:33
  • $\begingroup$ There does seem to be a space left for it on the fifth-to-last line of the paper before the references (they write O((m+n) s) instead of O((m+n)s); compare the sixth-to-last line of the first column of p122). Isn't it good that we don't have to typeset papers that way any more? $\endgroup$ – David Richerby Jan 3 '14 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.