Weighted B-Matching

[np96]

Any plans on implementation of Blossom V or another b-matching algorithm?
I need to use it in my project. Although I can download Vladimir's code, I'd be happy to see it in Boost.
Looks like it is not difficult to rewrite using Boost.Graph codebase. So, the question is: why is it not there yet? I may try to submit a PR if someone else wants it in Boost.

[Becheler]

Hi @np96 ! Thank you for your interest !

Great question! If I understand correctly, the weighted matching implementation is actually quite recent: Yi Ji added it in 2018, and Joris van Rantwijk updated it just this year. So this seems to be evolving.
Also performance optimizations sometimes take longer to prioritize than correctness fixes, so Blossom V I guess had weaker priority.

Anyway, I downloaded the paper and will assess implementation feasibility. I will let you know asap :)

[np96]

@Becheler hi there! Thanks for your response.

Sorry, I messed things a bit — I am not interested in ordinary matching implementation. The one which is in the Boost is enough for me.

The thing I need: Weighted b-matching solver: each vertex is additionaly labeled by b_v and if v is in the solution it has (up to) b_v incident edges. Also might be known as degree-constrained subgraph problem.

Tried to search for any implementation for around 1 week with no luck.
Sorry again for mixing things up. GPTs are sometimes saying convincing nonsense.

[Becheler]

No worries at all, graphs and matching problems tend to be quite polymorphic and hard to identify.
I am not sure what @jeremy-murphy would say but it seems to me like a much harder problem.

[np96]

By the way, a simple and beautiful reduction to ordinary matching problem by Shiloach can be applied. Probably not the most efficient approach, but looks like the most simple to implement.

Would like to hear an expert opinion if this might be needed in Boost.