learnig's blog

By learnig, history, 20 months ago, In English,

What is the fastest algorithm to compute maximal bipartite matching. What is its worst case run time complexity. How to construct the worst case for such algorithm. Thanks in advance.

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

»
20 months ago, # |
  Vote: I like it +9 Vote: I do not like it

The fastest is Hopcroft Karp BPM. It runs in O(sqrt(v)*E). You can go through Wikipedia to learn more.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Do you know In what case it is slow? I think on random graphs it runs pretty fast

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I bet this guy knows something about it: Burunduk1

      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        In d-regular graph (all degrees are equal to d) there is O(nlogn) algorithm Goel, Kapralov, Khanna. Notice, asymptotic is independent of number of edges. The algorithm: consider graph, on which Kuhn runs dfs, and instead of dfs run "random walk" (choose random edge and go throw it).

        On random but not regular graphs Kuhn with optimizations is better than Hopcroft.

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Bipartite Matching problem is equivalent to max flow in a modified graph.

      In graphs which are dense locally at some places and mostly sparse overall, Push Relabel Algorithm with gap Relabel heuristic runs very very fast. Much faster compared to Dinic's (which is equivalent to Hopcroft Karp).

      Asymptotic complexity of such algorithm is O(|v|^3) though for general graphs. But on random graphs it runs much more fast. To give you some numbers — my implementation runs within seconds for random graphs with n = 10000 nodes, m = 1000000 edges.

      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        it would be great if you could share your implementation code.

        • »
          »
          »
          »
          »
          20 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it
          Code
      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        If you use the lowest-label version and use global relabeling, the runtime can be bounded by (see Robert J. Kennedy, Jr. Solving unweighted and weighted bipartite matching problems in theory and practice, chapter 3 (The paper does not treat gap relabeling.)).

        Even without global relabeling, the lowest label version is usually the fastest one on bipartite matching graphs.

        • »
          »
          »
          »
          »
          20 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for sharing. Not so obvious at the moment though, I will ponder on this :)

»
20 months ago, # |
  Vote: I like it +25 Vote: I do not like it

One can also use Dinic algo and reduce problem to max flow, that will be as fast as Hopcroft Karp on bipartite graphs.

»
20 months ago, # |
  Vote: I like it +12 Vote: I do not like it

You might want to check out this variation of the alternating paths bipartite match algorithm. It is easy to code and very quick for most networks that have particularities (it can do ~1e6 vertices and edges in considerably less than 1s), even quicker than the regular Hopcroft-Karp algorithm (because it doesn't do any bfs beforehand).

Code: https://pastebin.com/q12aBwya

Note that the key optimization here is in the separation of the two for loops.

I have yet to find an example where it does quadratic time (and I think it's very non-trivial). I however suspect that the proof of Edmonds Karp upper bound cannot be applied here, as what the algorithm is doing is not equivalent to a BFS (the alternating paths aren't shortest, per se).

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Your implementation has got an Ω(V2) worst case on a sparse graph (E = Θ(V)).

    generator

    The input is a tree consisting of a long path of length and paths of length 3 hanging from every vertex in the long path. Vertex labels and edge order are chosen in a way such that initially every other edge in the long path is matched and every middle edge in a short path is matched. In a single phase, you'll find a single long augmenting path, alternating left  →  right and right  →  left. (The paths of length 3 break your heuristic.) This results in phases.

    The lower bound can be extended to Ω(VE) by adding a dense part K2x, x with where you'll scan x2 ≈ E edges every phase.

    You might be able to fix this by randomizing the vertex and edge ordering.

    • »
      »
      »
      20 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Thank you for your counterexample!

      As weird as this sounds, this implementation is the one that basically every high-school student in our country learns about as being the Hopcroft-Karp algorithm, and nobody here has managed to find a counterexample to break the heuristic (I think mostly because I am not very familiar with how to generate maximal test cases for matching in general).

      I will try to add this example to our most popular online judge archive. This should be fun.

      It seems like randomizing the order of vertices drops down the number of iterations to 8 in this case, although it's (very slightly) slower because of the shuffle algorithm. It's good to note though.