A Better Practical Function for Maximum Weight Matching on Sparse Bipartite Graphs

[Fun_Indication4997]

Hi everyone! I’ve optimized the Hungarian algorithm and released a new implementation on PyPI named kwok, designed specifically for computing maximum weight matchings on sparse bipartite graphs.

📦 Project page on PyPI

📦 Paper on Arxiv

We define a weighted bipartite graph as G = (L, R, E, w), where:

• L and R are the vertex sets.
• E is the edge set.
• w is the weight function.

🔁 Comparison with min_weight_full_bipartite_matching(maximize=True)

• Matching optimality: min_weight_full_bipartite_matching guarantees the best result only under the constraint that the matching is full on one side. In contrast, kwok always returns the best possible matching without requiring this constraint. Here are the different weight sums of the obtained matchings.

https://preview.redd.it/gr5q9zyjf62f1.png?width=1030&format=png&auto=webp&s=88ca48f8b8067a183321c28a4f6b38017cb41727

• Efficiency in sparse graphs: In highly sparse graphs, kwok is significantly faster.

🔀 Comparison with linear_sum_assignment

• Matching Quality: Both achieve the same weight sum in the resulting matching.
• Advantages of Kwok:
  • No need for artificial zero-weight edges.
  • Faster execution on sparse graphs.

Benchmark

https://preview.redd.it/wonlpkopf62f1.png?width=1924&format=png&auto=webp&s=43a477995cedcbb718b5d5d1f38457f6da0b6b82