Prove finding k disjoint paths from n given paths in a directed graph is NP-complete

Question

Problem: Given n paths in a directed graph G(V, E) and an integer k, find out k paths among them such that no two of them pass through a common node.

Prove that the given problem is in NP-complete.

I was able to prove that the problem is in NP. Hint is that we need to come up with a polynomial time reduction of the independent set problem to this problem prove that it is in NP-hard.

Answer 1

Membership of your problem in $\mathsf{NP}$ is trivial. To prove that it is also $\mathsf{NP}$-hard consider an instance of (the decision version of) independent set consisting of a graph $G=(V, E)$ with $|V|=n$ and of an integer $k$.

Construct the graph $H = (V', E')$ where $V' = V \cup \{ x_{u,v} \, : \, (u,v) \in E \}$ and $E' = V' \times V'$.

For each $u \in V$ let $v_1, v_2, \dots, v_h$ be the neighbors of $u$ in $G$ and define the path $P_u = \langle u, x_{u,v_1}, x_{u,v_2}, \dots, x_{u,v_h} \rangle$ in $H$. Let $\mathcal{P} = \{P_u \, : \, u \in V\}$.

There is an independent set of size at most $k$ in $G$, if and only if there is a subset $\mathcal{P}'$ with $|\mathcal{P}'| \le k$ such that the paths in $\mathcal{P}'$ are pairwise vertex-disjoint.

More precisely, if $S$ is an independent set of $G$, then $\{ P_u \, : \, u \in S \}$ is a collection of pairwise vertex-disjoint paths in $H$ and, if $\mathcal{P}'$ is a collection of pairwise vertex-disjoint paths in $H$, then $\{u \, : \, P_u \in \mathcal{P}' \}$ is an independent set of $G$.