2. Nonoverlapping Paths is NP-complete. Suppose you are given an undirected graph G and a set P P, P,.. , Pk), where each P is a simple path in G. We say a set of paths P, P,P) S P is nonoverlapping if no two paths in the set share a vertex. In the Nonoverlapping Paths problem, you are given a graph G, a set of paths P in G, and a positive integer t, and you are asked whether there is a nonoverlapping set of paths QCP with |2l 2t (a) Show that Nonoverlapping Paths is in NP (b) Show that Nonoverlapping Paths is NP-hard. 2. Nonoverlapping Paths is NP-complete. Suppose you are given an undirected graph G and a set P P, P,.. , Pk), where each P is a simple path in G. We say a set of paths P, P,P) S P is nonoverlapping if no two paths in the set share a vertex. In the Nonoverlapping Paths problem, you are given a graph G, a set of paths P in G, and a positive integer t, and you are asked whether there is a nonoverlapping set of paths QCP with |2l 2t (a) Show that Nonoverlapping Paths is in NP (b) Show that Nonoverlapping Paths is NP-hard