I'm trying to find pairs in a complete, weighted graph, similar to the one below (weights not shown).

For each possible pair there is a weight and I would like to find pairs for including all vertices, maximizing the weight of those pairs.

Many of the algorithms for finding maximum matchings are only concerned with finding them in bipartite graphs (e.g. Hungarian algorithm). In this case the graph is not bipartite. The only algorithm I found that seems to fit the problem here is Edmond's Blossom algorithm and it's (revised?) Blossom V variant.

As far as I understand the complexity of Blossom is polynomial ($n^3$) and so with bigger graphs complexity increases quickly. I currently don't expect more than 100 vertices which should be manageable unless the $n$ in $n^3$ concerns the number of edges in the graph. In this case I might need to find a way to make the graph less dense.

My questions are:

  1. Is Blossom/Blossom V the only algorithm that should be considered for this problem or did I miss any other contenders while digging into this?
  2. Do you know if in these kinds of algorithms $n$ usually refers to the number of vertices or edges?
  3. Since even with Blossom this might be computationally intensive I was wondering if someone can think of some smart steps to simplify the problem, maybe turning it into another problem that could be easier to solve.
  • $\begingroup$ To provide some additional context for the third question: The idea is to match people based on some criteria. For instance in a (fun) chess tournament you might want to match people based on age, rank, city, etc. These parameters will determine the weights between vertices. You want to match everyone while making sure you maximise the weight. $\endgroup$ – Martin Klepsch May 6 at 6:01
  • $\begingroup$ "...unless the $n$ in $n^3$ concerns the number of edges in the graph." Why not check the specification of Blossom algorithm? $\endgroup$ – Apass.Jack May 6 at 11:09
  • 1
    $\begingroup$ If you are willing to trade quality for time, A simple approximation algorithm for the weighted matching problem may be interesting. $\endgroup$ – Marcus Ritt May 6 at 11:33
  • $\begingroup$ @Apass.Jack Fair enough. I found this: "A straightforward implementation of Edmonds’s algorithm requires $O(n2m)$ time, where $n$ is the number of nodes in the graph and $m$ is the number of edges." — so $n$ usually refers to the number of nodes but some of the algorithms also depend on the number of edges. $\endgroup$ – Martin Klepsch May 6 at 18:15
  • $\begingroup$ @MartinKlepsch since you have a complete graph, then $m = n^2$ and thus the Edmonds' algorithm complexity is $O(2n^3) = O(n^3)$. $\endgroup$ – Iago Carvalho May 7 at 1:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.