### fakerman's blog

By fakerman, history, 7 months ago, ,

I read somewhere that the complexity of maximum bipartite matching using Dinic's is the same as that of Hopcroft Karp. But the complexity of Dinic's is $O(V^2E)$, and creating the flow network to solve maximum bipartite matching via it will also result in a $O(V^2E)$ complexity. But Hopcroft Karp takes $O(E\sqrt{V})$ time, which is clearly better than Dinic's. Please help me clear this doubt.

• +13

 » 7 months ago, # |   0 For unit capacity graphs Dinic's algorithm works in $O(E \sqrt{V})$ and that's why it has the same complexity as Hopcroft Karp.
•  » » 7 months ago, # ^ | ← Rev. 2 →   +16 dinic with unit capacity is only in $O((V+E)\sqrt{E})$ but the bipartite matching case has an additional property wich makes it faster: every vertex has either indegree or outdegree $\leq 1$ in this case dinic is in $O((V+E)\sqrt{V})$ (same as hopcraft karp but terrible constant factors if you compare them)
•  » » » 7 months ago, # ^ |   0 Can you give the source from which you know that Dinic is $O((V+E) \sqrt{E})$. I agree it should be $V+E$ and not just $E$, but I don't see why it will be $\sqrt{E}$ instead of $\sqrt{V}$.
•  » » » » 7 months ago, # ^ |   0 My source is my algorithms lecture but i think this is the paper it refers to: "Network Flow and Testing Graph Connectivity" from Even and Tarjan.Theorem 1 proves the unit capacity part with a bound of $O((V+E)\sqrt{E})$Theorem 3 proves the unit capacity and max degree part with a bound of $O((V+E)\sqrt{V})$
•  » » » 7 months ago, # ^ |   +8 It seems there are some algorithms with wonderfully strong guarantees that never stop to amaze me. Has anyone collected all performance guarantees of Dinic (e.g. a survey-style paper)? Splay trees also fall into this category.