A large collection of mobile wireless devices can naturally form a network in which the devices are the nodes, and two devices x and y are connected by an edge if they are able to directly communicate with each other (e.g., by a short-range radio link). Such a network of wireless devices is a highly dynamic object, in which edges can appear and disappear over time as the devices move around. For instance, an edge (x, y) might disappear as x and y move far apart from each other and lose the ability to communicate directly. In a network that changes over time, it is natural to look for efficient ways of maintaining a path between certain designated nodes. There are two opposing concerns in maintaining such a path: we want paths that are short, but we also do not want to have to change the path frequently as the network structure changes. (That is, wed like a single path to continue working, if possible, even as the network gains and loses edges.) Here is a way we might model this problem.

Suppose we have a set of mobile nodes V, and at a particular point in time there is a set E0 of edges among these nodes. As the nodes move, the set of edges changes from E_0 to E_1, then to E_2, then to E_3, and so on, to an edge set E_b. For i = 0, 1, 2, . . . , b, let G_i denote the graph (V, E_i). So if we were to watch the structure of the network on the nodes V as a time lapse, it would look precisely like the sequence of graphs G_0, G_1, G_2,..., G_{b1}, G_b. We will assume that each of these graphs G_i is connected. Now consider two particular nodes s, t V. For an s-t path P in one of the graphs G_i, we define the length of P to be simply the number of edges in P, and we denote this l(P).

Our goal is to produce a sequence of paths P_0, P_1,..., P_b so that for each i, P_i is an s-t path in G_i. We want the paths to be relatively short. We also do not want there to be too many changespoints at which the identity of the path switches. Formally, we define changes(P_0, P_1,..., P_b) to be the number of indices i (0 i b 1) for which P+i /= P_i+1. Fix a constant K > 0. We define the cost of the sequence of paths P_0, P_1,..., P_b to be

cost(P_0, P_1,..., P_b) = Sum^b_{i=0} l(Pi) + K changes(P_0, P_1,..., P_b).

(a) Suppose it is possible to choose a single path P that is an s-t path in each of the graphs G_0, G_1,..., G_b. Give a polynomial-time algorithm to find the shortest such path.

(b) Give a polynomial-time algorithm to find a sequence of paths P_0, P_1,..., P_b of minimum cost, where Pi is an s-t path in G_i for i = 0, 1, . . . , b.