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

2
votes

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.

2
algorithmgraphcomplexity-theorygraph-algorithm
By having the "minimum maximum weight possible", do you mean that the maximum edge weight in the set is the minimum of all posible sets? If so, then why not just choose the empty set, and if that's not allowed, choose the set with a single edge, which is the edge with the smallest weight. - Peter Alexander
edited for correction. I actually have a need for this. - ashaw
Ah, then why not just combine the last two statements into "every vertex is connected to exactly one edge in the set" :-) - Peter Alexander
I have done this, as this is a good idea. - ashaw
Unless you constrain the graph further (e.g. is it bipartite?) there is not necessarily even a solution: e.g. 4 vertices a, b, c, d with 3 edges ab, ac, ad. - j_random_hacker

2 Answers

2
votes

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/

0
votes

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