For each of the following two statements decide whether it i

For each of the following two statements, decide whether it is true or false. If it is true, give a short explanation. If it is false, give a counterexample. Suppose we are given an instance of the Minimum Spanning Tree Problem on a graph G, with edge costs that are all positive and distinct. Let T be a minimum spanning tree for this instance. Now suppose we replace each edge cost ce by its square, thereby creating a new instance of the problem with the same graph but different costs. True or false? T must still be a minimum spanning tree for this new instance. Suppose we are given an instance of the Shortest s-t Path Problem on a directed graph G. We assume that all edge costs are positive and distinct. Let P be a minimum-cost s-t path for this instance. Now suppose we replace each edge cost ce by its square, ce2, thereby creating a new instance of the problem with the same graph but different costs. True or false? P must still be a minimum-cost s-t path for this new instance.

Solution

For first case it is True.

If the costs C2e into Kruskal\'s algorithm it will sort them in the similar order? Place the same subset of edges in the MST.

For second case is False.

Let G have edges (a,b),(b,c) and (d,c) where the initial 2 edges have cost 6 and the final cost 10.

The shortest path is the edge (d,c) however after squaring the costs the shortest path would go through b.