Proof that Path Selection Decision problem is NP-Complete

Check if P' is a subset of P
If not, the given solution is wrong
The number of paths in P' is at least k
If not, the given solution is wrong

Initialize a list of boolean with length |V|
for each path p in P'
    for each vertex in p
        check if it is marked True in our list
        If so, the given solution is wrong
        Else, marks the vertex as True

Since no vertex was marked twice,
given solution is correct.

1. Checking P’ is a subset of P can be done in O(|P|).
2. Checking number of paths in P’ can be done in O(|P’|)
3. Checking all the paths are disjoint can be done in O(|V|)

G=(V, E) and k 

1. We denote a path by P_i for v_i.
2. Let e₁, e₂, …, e_r be the edges connected to v_i. We introduce a vertex for each such edge in G’. Further, we introduce a pair of vertices in G’ – s_i, t_i.

1. For a graph G=(V, E) there exist an independent set of size at least k.
2. There exist at least k vertices that don’t share any edge.
3. There exist at least k paths that don’t share any node in the instance of PSP. Since we are defining the vertices of G to be analogous to paths in the instance of PSP and edges of G to be analogous to vertices in those paths. And any of these path sharing nodes would mean that some two vertices in the independent set share a common edge which is never possible.
4. Yes, instance for PSP.

1. For a graph G=(V, E) there cannot exist an independent set of size k.
2. It is not possible to find k vertices of G that don’t share any edge.
3. Every set S of vertices of size k would contain vi and vj that share an edge.
4. Since we are defining the vertices of G to be analogous to paths in the instance of PSP and edges of G to be analogous to vertices in those paths, every k size set of Paths in instance of PSP would share a node.
5. There cannot exist k paths that don’t share any node in the instance of PSP.
6. No instance for PSP.