skavurskaa's blog

Min weight perfect matching on complete bipartite graph?
By skavurskaa, history, 8 years ago, In English

Problem statement: Given a complete bipartite graph KN, N with weights Wuv assigned to each edge uv, find a perfect matching with minimal sum of edge weights among all perfect matchings.

Is there any easy to code polynomial algorithm for this problem? I know an easy way to solve it using subset dp in O(N22N), and i also think that it is possible to modify the Hungarian Algorithm to solve this problem. But is there any easier algorithm considering it is always a complete bipartite graph? I don't care too much about the time complexity as long as it is polynomial.

Thanks in advance!

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

You can solve it using min-cost-flow.

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

I don't understand why the most basic Hungarian Algorithm would not be applied here?

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

    I think i know how to solve it using the Hungarian Algorithm, but i would like to know if there is any algorithm that is easier to code and with polynomial complexity :)

    For example, we can solve this problem using subset dp, the code is very very easy but the time complexity is very high too.

    Maybe there is an algorithm that doesn't rely on graph theory or network flows when it's the special case of a complete bipartite graph?

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

      I don't suppose it will be any easier in this case only because it's complete. We can convert any non-complete bipartite graph to a complete one and solve the same task on our new graph just by adding every missing edge with infinite weight. The Hungarian Algorithm has been the way to go for this task for quite some time. Perhaps you may find min-cost max flow easier to implement, but there are some really short and easy to comprehend implementations, under 30 lines, for the Kuhn-Munkres algo, you just have to look for them.

      A neat approximation which may come in handy while in a contest and failing to implement any of those algorithms is simply creating as many different Greedy algorithms possible and taking the best answer out of all.

      → Reply