Question

We define the Escape Problem as follows. We are given a directed graph G = (V; E) (picture a network of roads.) A sure collection of vertices X V is designated as populated vertices and a positive other collection S V is designated as safe vertices. (Assume that X and S are disjoint.) In case of an emergency, we want migration routes from the populated vertices to the safe vertices. A set of evacuation routes is de?ned as a set of paths in G such that

(i) each vertex in X is the tail of one path,

(ii) the last vertex on each path lies in S, and

(iii) The paths do not share any edges. Such a set of paths gives way for occupants of the populated vertices to "escape" to S without overly congesting any edge in G.

(a) Given G, X, and S, shows how to decide in polynomial time whether such a set of evacuation routes exists.

(b) Assume we have exactly the same problem as in (a), but we want to enforce an even stronger version of the "no congestion" condition (iii). Thus we change (iii) to say, "The paths do not share any vertices." With this new state, show how to decide in polynomial time whether such a set of evacuation routes exists. Also provide an instance with the same G, X, and S in that the answer is "yes" to the question in (a) but "no" to the question in (b).