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.

(a) 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, c2e, 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.

(b) 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, c2e, 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

a.) If you squared each edge of given graph and then construct a MST from that graph. Then MST will be same as that of the previous MST as we haven\'t changed anything just scaled up the cost.

b.) Same thing applies here as well. When we squared each edge of given graph. It will not really make much a bit difference as we have just scaled up the cost associated with the edge. So, P still be a minimum cost path for this new instance,