Блог пользователя fakerman

Doubt regarding complexity of bipartite matching using Dinic's and Hopcroft Karp
Автор fakerman, история, 6 лет назад, По-английски

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
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 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.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← 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)

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 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}$$$.

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 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})$$$

        → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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.

      → Ответить