Path Selection (K&T Ch8.Ex9). Consider the following problem. You are managing a commu- nication network, modeled by a directed graph G = (V,E). There are c users who are interested in making use of this network. User i (for each i = 1, 2, ..., c) issues a request to reserve a specific path Pi in G on which to transmit data.

You are interested in accepting as many of these path requests as possible, subject to the following restriction: if you accept both Pi and Pj, then Pi and Pj cannot share any nodes.

Thus, the Path Selection problem asks: Given a directed graph G = (V,E), a set of requests P1,P2,...,Pc (each of which must be a path in G) and a number k, is it possible to select at least k of the paths so that no two of the selected paths share any nodes? Prove that Path Selection is NP-complete.