Find minimum-weight complete graph that spans a gi

问题:

Let T = (V, E) be a tree of |V| vertices and |E| = |V-1| edges, with known costs. We want to construct a minimum-weight complete Graph G = (V, E') that spans T as its unique minimum spanning tree.

Example: consider the following tree T. Edges in red have a given cost. Dotted edges will be added to construct a complete graph from this tree.

The minimum-weight complete graph G that spans T as its unique MST is the following:

---

I am trying to find a (polynomial-time) algorithm that generates this graph. I am looking mostly for a tip, not the complete solution. So far, I have devised the following algorithm:

1) Find a cut of the graph that includes the heaviest MST edge of weight w_max and no other MST edges. All other edges have to be w_max + 1. The following pictures illustrates my idea:

Edges (1--2), (1--4), (4--5), (2--3) and (2--5) are included in this cut C. The only edge that is included in the MST is edge (2--3) and it's the heaviest edge in the MST, with w=56. Thus, all other edges should have w=57. Proof: assume the contrary; we can replace (2--3) with another edge and still keep the tree connected. Now the tree's weight is lighter, thus (2--3) doesn't belong to the MST. Contradiction.

2) Repeat for all other edges e_i of the MST, of weight w_i, in decreasing weight order. Take a cut that includes only e_i and no other MST edges. Any unknown non-MST edge of this cut, should have a weight of w_i + 1.

---

Questions:

1) Is the above algorithm correct? According to the Cut property, it should be.

2) Could I do it more efficiently? I don't have an algorithm to find cuts on the top of my head, but I don't feel this approach could be efficient.

---

edit: Another approach that I had in my mind was an approach based on Kruskal's algorithm:

1) Using a Union-Find, I iterate all MST edges, by ascending cost, and unify the corresponding vertices under the same component.

2) In each step, two different components are unified through an edge of cost w. Any other edges that form a cycle within the same (new) component should have a cost of w+1.

回答1:

Answering my own question

Here's an efficient answer I've come up with, following also the feedback from @sasha . Suppose we would like to calculate the total weight of the complete graph G, i.e;

Let T = (V, E) be a tree of |V| vertices and |E| = |V|-1 edges, with known weights. Calculate the total weight w_total of the minimum-weight complete Graph G = (V, E') that spans T as its unique minimum spanning tree. NB: edge weights are natural numbers.

Algorithm:

1. Initialize a Union-Find with |V| singleton components.
2. Sort all edges of T by ascending weight. Running time: O(|V| * log|V|).
3. Iterate next edge e = (v1,v2) of T. Add its weight w_e to w_total.
4. Find v1's andv2's components in the Union-Find: set1,set2, containing size1 and size2 vertices, respectively.
5. These components will be unified. Since G is a complete graph, size1 × size2 edges will be added: one edge is the MST e edge, all others have to be heavier than e, so that Kruskal's algorithm will ignore them. Thus, their minimum weight should be at least w_e + 1.
6. w_total += (size1 × size2 - 1) × (w_e + 1).
7. Unify the two components set1 and set2.
8. Repeat from step 2 for the next MST edge e.

Running time: O(|V| * log|V|).

---

If the problem becomes: list in detail all edges e = (v1, v2) of the complete graph and their weight w, we just have to do, between steps 6 and 7:

for all vertices v1 in set1
  for all vertices v2 in set2
    create edge e = (v1, v2); ignore if edge is the MST edge
    w_e = w_mst_edge + 1

So the running time becomes O(|E| + |V| * log|V|) = O(|V|^2), since we have |E| = |V|*(|V|-1)/2 edges in the complete graph G.