Question

Shortest Path

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 integers. Let P be a minimum-cost s-t path for this instance. Now suppose we replace each edge cost ce by its square, c 2 e, thereby creating a new instance of the problem with the same graph but different costs. For each of the following statements, decide whether it is true or false. If it is true, give a short explanation. If it is false, give a counterexample. (a) [2 points] The cost of P in the original instance is strictly less than that of P in the new instance. (b) [2 points] P is the unique minimum cost s-t path in the original instance (before squaring costs). (c) [2 points] P must still he a minimum-cost s-t path for the new instance (after squaring costs).

Answer 1

a) True for more than two node and False for 2 nodes and cost of the edge is 1

If the number of the nodes in the graph are more than 2 and as the edge costs are distinct and integer the the sum of squares of integers is always greater than its corresponding integer so P in original instance is always less than P in new instance, but if there are only two nodes and its cost of the edge is 1 then afer squaring it its cost remains same which is not strictly increasing(exception)

b)False

There can be any number of shortest paths for a given graph. Let us say a graph has two paths

First Path(AB,BC,CD) edge costs are (4,3,6)

Second path(AE,EF,FD) edge costs are (7,1,5)

Here we can see two shortest paths for the given graph,

However we can only have one minimum spanning tree for edges with distinct edge costs

c)False

P can or can't be a minimum cost s-t pathfor new instance,Let us say there are two paths

Before squaring

First Path(AB,BC,CD) edge costs are (3,4,5) total cost is 12

Second path(AE,EF,FD) edge costs are (1,2,7) total cost is 10

Here the second path is shortest path,

But after squaring the same costs become

First Path(AB,BC,CD) edge costs are (9,16,25) total cost is 50

Second path(AE,EF,FD) edge costs are (1,4,49) total cost is 54

Here the first path is shortest path,

which contradicts the given statement