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:
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.