1

G is an undirected connected graph with positive costs on all edges. Given is edge e whose cost is strictly more than 10. We need to answer whether the MST cost will improve if the cost of e is reduced by 10.

I know of a solution that involves generating a new graph with only edges with cost<cost(e)-10. What's wrong with this much simpler solution: Take one of e's vertices v. Find the minimal cost edge incident to v. Now reduce e's cost and find the minimal cost edge incident to v again. If there was a change, it means that prim would find a better MST and the cost is improved. If not, it means that prim would find the same MST and the cost stays the same.

What's wrong with this logic?

related to Update minimum spanning tree with modification of edge

ihadanny
  • 4,377
  • 7
  • 45
  • 76

2 Answers2

1

I don't think that your solution is correct.

Consider the following graph G = (V, E), V = {a, b, c, d, e}, E = {ab, bc, cd, de, ae, bd} and the respective weights are {5, 10, 10, 5, 17}.

By running Kruskal or Prim, we find that our MST is {ab, bc, cd, de}, and his weight is 30.

Now, let's reduce the weight of the edge bd from 17 to 7, and examine the edges again.

Running Prim or Kruskal with G' will output an MST which weighs 27 (actually we have 2 such MSTs {ab, bd, de, cd} and {ab, bd, de, bc}).

But if we use your algorithm, we would get the same exact tree, because when we examine the nodes b or d, the edge bd is not the lightest edge that is adjacent to either one of these nodes.

Daniel Shterenberg
  • 427
  • 3
  • 11
1

Let's G = (V, E) be a graph.
Definition
1
where w(<u,v>) is the weight of <u,v>.

Lemma 1
Let's G be a graph, v a vertex of G and e an edge of G incident to v. If w(e) = C(v) then e belongs to some MST of G.

It's true that if C(v) value is altered when e's cost is reduced by 10 then the MST cost will improve if the cost of e is reduced by 10 by lemma 1.

First half is ok. Let's take a look to second part.

If not, it means that prim would find the same MST and the cost stays the same.

General explanation
The aforementioned quote falsely implies that the converse of lemma 1 is true (e belongs to some MST of G then w(e) = C(v)) since it claims that if we reduce e's cost by 10 and w(e) != C(v) then MST cost is preserved which implies that e doesn't belong to any MST of G.

Short explanation: a counterexample
Let's G = ({1, 2, 3, 4}, {<1, 2>, <1, 3>, <2, 4>, <3, 4>, <1, 4>}) with weight function w(<1, 2>) = 1, w(<1, 3>) = 3, w(<2, 4>) = 3, w(<3, 4>) = 1, w(<1, 4>) = 12 and e = <1, 4>.

After reducing e's cost we know that C(1) = C(4) = 1 != w(e). Proposed algorithm state that: "prim would find the same MST and the cost stays the same".

Let's check if there is a decrease in G's MST cost when the cost of e is reduced by 10:
MST cost before reducing the cost of e by 10: 5
MST cost after reducing the cost of e by 10: 4

Since there is a decrease in the MST cost then such claim (quoted one) is false and proposed algorithm doesn't work.

Note: The algorithm is wrong no matter which MST algorithm is used as the counterproof relies only on MST properties.

Eloy Pérez Torres
  • 1,050
  • 4
  • 14