implementing the Blossom algorithm for maximum weight matching [$1000]

[Krastanov]

Implement the well-known Blossom algorithm for maximum weight (perfect) matching in generic graphs.

• wiki link: https://en.wikipedia.org/wiki/Blossom_algorithm
• many simple (not-optimized) implementations of the algorithm from class projects and the like are available if one searches online for "blossom algorithm simple"

Two bounties are available here:

• a 500$ bounty for implementing a pure-julia Blossom with tests and documentation, making it the default here, and moving BlossomV.jl from a dependency to a weak dependency (so that it is not necessary during installation)
• a 500$ bounty on improving the performance of the new implementation to no-worse than 90% of BlossomV.jl

Required skills: Both skills in graph theory and high-performance julia.

Reviewer: @Krastanov or @gdalle or members of the JuliaGraphs community

Duration: 1 month per stage (except potential review overhead)

Payout procedure (for this particular bounty program):

The Funding for these bounties comes from the National Science Foundation and from the NSF Center for Quantum Networks. The payouts are managed by the NumFOCUS foundation and processed in bulk once every two months. If you live in a country in which NumFOCUS can make payments, you can participate in this bounty program.

Click here for more details about the bug bounty program.

Bug bounty logistic details (click to expand)

To claim exclusive time to work on this bounty either post a comment here or message [email protected] with:

• your name
• github username
• (optional) a brief list of previous pertinent projects you have engaged in

Currently the project is claimed by no one until ....

If you want to, you can work on this project without making a claim, however claims are encouraged to give you and other contributors peace of mind. Whoever has made a claim takes precedence when solutions are considered.

You can always propose your own funded project, if you would like to contribute something of value that is not yet covered by an official bounty.

[simonschoelly]

Some suggestions:

• Why not implement the original blossom algorithm first? It only works for unweighted graphs - but as far as I know the Kolmogorov algorithm is based on that.
• Instead on creating an optimal algorithm create a working algorithm first - it might potentially waste one or two loop iterations and use non-optimal data structures but we can work from that on.
• JGraphT has an implementation that might be worth looking at.

[Krastanov]

I concur (and the bounty explicitly is split in two parts where the first one does not require a fast implementation at all)

A few other open source implementations:

• https://lemon.cs.elte.hu/trac/lemon
• Find a maximum matching of a non-bipartite graph igraph/igraph#2403 (see the list in the first comment)
• New feature: maximum matching of general graph igraph/igraph#2550

[Krastanov]

Ok, let's do another round. @amicciche, you had expressed interest in this bounty. Could you comment here to confirm you indeed want to take on it for the next month or so?

[amicciche]

Yes! I'd love to give this a try. Thanks!

[Krastanov]

Sounds good, marking as reserved!