Suppose we are given a directed graph G = (V, E), a set of nodes A V (denoted as people) and a set of nodes B V (denoted as exit). Assume A and B are disjoint. We want to find a schedule such that every person can escape to an exit node. More specifically, a schedule is a set of paths in G so that:
Every path contains exactly one node in A.
Each node in A is the first node of the corresponding path.
For each path, the last node is an exit node.
All the paths are edge-disjoint.
Given G, A, B, provide a polynomial time algorithm that decides whether such a schedule exists.
Suppose the third condition is changed to: All the paths are node-disjoint.
Provide again a polynomial time algorithm that decides whether such a schedule exists. Provide an example with the same G, A, B such that in this instance, the answer is "yes" to part (a) but "no" to part (b).