CODEWITHSUNDEEP
algorithmgraphminimum-spanning-tree
ccying
ccying

Reputation: 251

Linear algorithm to make edge weights unique

I have a weighted graph, and I want to compute a new weighting function for the graph, such that the edge weights are distinct, and every MST in the new graph corresponds to an MST in the old graph.

I can't find a feasible algorithm. I doubled all the weights, but that won't make them distinct. I also tried doubling the weights and adding different constants to edges with the same weights, but that doesn't feel right, either.

The new graph will have only 1 MST, since all edges are distinct.

Upvotes: 2

Views: 481

Answers (2)

Prune
Prune

Reputation: 77910

Very simple: we multiply all weights by a factor K large enough to ensure that our small changes cannot affect the validity of an MST. I'll go overboard on this one: 

K = max(<sum of all graph weights>, 
        <quantity of edges>)
        + 1

Number the N edges in any order, 0 through N-1. To each edge weight, add the edge number. It's trivial to show that

  1. the edge weights are now unique (new difference between different weights is larger than the changes);
  2. any MST in the new graph maps directly to a corresponding MST in the old one (each new path sum is K times the old one, plus a quantity smaller than K -- the comparison (less or greater than) on any two paths cannot be affected).

Yes, this is overkill: you can restrict the value of K quite a bit. However, making it that large reduces the correctness proofs to lemmas a junior-high algebra student can follow.

Upvotes: 2

Patrick87
Patrick87

Reputation: 28332

We definitely cannot guarantee that all of the MSTs in the old graph are MSTs in the new graph; a counterexample is the complete graph on three vertices where all edges have equal weights. So I assume that you do not require the construction to give all MSTs, as that is not possible in the general case.

Can we always make it so that the new graph's MSTs are a subset of the old graph's? This would be easy if we could construct a graph without a MST. Of course, that doesn't make any sense and is impossible, since all graphs have at least one MST. Is it possible to change edge weights so that only one of the old graph's MSTs is an MST for the new graph? I propose that this is possible in general.

  1. Determine some MST of the old graph.
  2. Construct a new graph with the same edges and vertices, but with weights assigned as follows:
    • if the edge in the new graph belongs to the MST determined in step 1, give it a unique weight between 1 and n, the number of edges in the graph.
    • otherwise, give the edge in the new graph a unique weight greater than or equal to n^2, the square of the number of edges in the graph.

Without proof, it seems like this should guarantee that only the nominated MST from the old graph is an MST of the new graph, and therefore every MST in the new graph (there is just the one) is an MST in the old graph.

Now, one could ask whether we can do the deed with additional restrictions:

  • Can you do it if you only want to change the values of edges that are not unique in the old graph?
  • Can you do it if you want to keep relative weights the same for edges which were unique in the old graph?

One could even pose optimization problems:

  • What is the minimum number of edge weights that must be changed to guarantee it?
  • What is the weighting with minimum distance (according to some metric) from the old weighting that guarantees it?
  • What is the weighting that minimizes the average change while also guaranteeing it?

I am hesitant to attempt these, what I believe to be much more difficult, problems.

Upvotes: 2

Related Questions