fakerman's blog

Doubt regarding complexity of bipartite matching using Dinic's and Hopcroft Karp
By fakerman, history, 6 years ago, In English

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.

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply