We define the Escape Problem as follows. We are given a directed graph G = (V, E

Question

We define the Escape Problem as follows. We are given a directed graph G = (V, E) (picture a network of roads). A certain collection of nodes X V are designated as populated nodes, and a certain other collection S V are designated as safe nodes. (Assume that X and S are disjoint.) In case of an emergency, we want evacuation routes from the populated nodes to the safe nodes. A set of evacuation routes is defined as a set of paths in G so that (i) each node in X is the tail of one path, (ii) the last node on each path lies in S, and (iii) the paths do not share any edges. Such a set of paths gives a way for the occupants of the populated nodes to “escape” to S, without overly congesting any edge in G. (a) Given G, X, and S, show how to decide in polynomial time whether such a set of evacuation routes exists. (b) Suppose 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 nodes.” With this new condition, show how to decide in polynomial time whether such a set of evacuation routes exists. Also, provide an example with the same G, X, and S, in which the answer is yes to the question in (a) but no to the question in (b).

Explanation / Answer

Proof. ( ) Suppose the ow network has a max-ow value of | X | . (It cannot be more than | X | since the cut separating the source s has capacity | X | .) Because all edge capacities are integral, the integrality theorem tells us that there exists an integral ow f . This ow f has f ( e ) { 0 , 1 } for any edge e other than edges from S to t . Similar to our proof of Menger’s theorem, trace a walk of edges with ow values a starting from s . This walk has to end at t due to ow conservation constraints. Remove all cycles from this walk and we get the rst X,Y -path. Then, set reduce all ow values on edges of this walk by 1, and we get a new feasible ow with value | X | - 1. Repeat the procedure recursively until we get | X | paths. ( ) If a set of evacuation routes exists, we simply set all ow values on edges of these routes to be 1, ow values of edges from the source s to each vertex in X to 1, and ow values of an edge ( v,t ) from S to t to be the number of evacuation routes which end at t .

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.