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.

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.

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)

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

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

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.