I have a complete and weighted graph with an even number of vertices. I would like to separate all the vertices into pairs such that the sum of all the edge weights for each edge connecting the vertices in each pair is at a minimum.

I have had some success solving this using the Hungarian Algorithm as found here (under the O(n4) algorithm explanation header). To apply this I created a weighted bipartite graph made of two copies of the vertex set from the original graph. Here's a simple example of that:

Making a bipartite graph from the original.

In this problem a feasible matching means if vertex i is matched with vertex j, vertex j must be matched with vertex i, as that is the only meaningful result in the context of the problem since the matching must be done in pairs.

The Hungarian Algorithm is successful in the large majority of cases, but can fail to find a feasible matching if there exists another minimal cost matching that is not feasible, and it finds that solution first.

Is there a way to modify the algorithm to come up only with feasible solutions?


There is no general extension of Hungarian algorithm for non-bipartite graphs. However, this problem can be solved using the Blossom algorithm.

  • $\begingroup$ That makes sense, solving the matching on the original graph wouldn't have this problem. Thanks for the direction. $\endgroup$ – Adam Oct 14 '14 at 17:00

This is called maximum weighted matching, this is a variant of Blossom and can be found in the python package networkx under networkx.algorithms.matching.max_weiht_matching see doc here.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.