Is there an algorithm to find the best set of Pairs of vertices in a weighted graph without repetition?

Question

Is there any efficient algorithm to find the set of edges with the following properties, in a complete weighted graph with an even number of vertices.

• the set has the smallest, maximum edge weight for any set that meats the other criteria possible
• every vertex is connected to exactly one edge in the set

All weights are positive

dI cannot think of one better than brute force, but I do not recognise it as NP hard.

Answer 1

One way to solve this problem in polynomial time is as follows:

1. Sort the edge weights in O(E log E) time
2. For each edge, assign it a pseudo-weight E' = 2^{position in the ordering} in ~O(E) time
3. Find the minimum weight perfect matching among pseudo-weights in something like O(V^3) time (depending on the algorithm you pick, it could be slower or faster)

This minimizes the largest edge that the perfect matching contains, which is exactly what you're looking for in something like O(V^3) time.

Sources for how to do part 3 are given below
[1] http://www2.isye.gatech.edu/~wcook/papers/match_ijoc.pdf
[2] http://www.cs.illinois.edu/class/sp10/cs598csc/Lectures/Lecture11.pdf
[3] http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/papers/blossom5.ps

with sample C++ source available at http://ciju.wordpress.com/2008/08/10/min-cost-perfect-matching/

Answer 2

try this (I just thought this up so I've got neither the proof that it will give an optimum answer or whether it will produce a solution in every cases):

1. search for the heaviest vertices V(A, B)
2. remove vertice V from the graph
3. if A is only connected to a single other vertice T(A, C) then remove all other edges connected to C, repeat step 3 with those edges as well
4. if B is only connected to a single other vertice S(B, D) then remove all other edges connected to D, repeat step 4 with those edges as well
5. repeat from step #1