4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Hint: Given an instance of independent set, construct an instance of your problem whose vertices are the edges of the original instances. You can assume without loss of generality that the graph in the latter instance is complete. $\endgroup$ Commented May 21, 2020 at 13:13

1 Answer 1

5
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ If I am not wrong, the intuition behind the solution that $x_{u, v}$ must be only selected once which ensures that if we pick u then we are not picking v in out independent set. But the edges formed are not quite clear to me. If $(u,v) \in E$ does this mean that $(u,x_{u,v}) \in E' $ and $(v,x_{u,v}) \in E'$ and all $(x_{u, v_i},x_{u, v_j} ) \in E'$ . $\endgroup$
    – user121450
    Commented May 21, 2020 at 13:42
  • $\begingroup$ Yes, this is correct. In particular $E'$ contains all possible edges. $H$ is a complete graph. $\endgroup$
    – Steven
    Commented May 21, 2020 at 13:44
  • $\begingroup$ I think you can remove $V$ from $V'$, though it's not a big difference. $\endgroup$ Commented May 21, 2020 at 13:58
  • $\begingroup$ @YuvalFilmus Keeping $V$ also handles the case in which there are multiple singleton vertices in $G$ (that would result in multiple "empty" paths otherwise). $\endgroup$
    – Steven
    Commented May 21, 2020 at 14:08
  • $\begingroup$ Nice answer! $\quad$ $\endgroup$
    – John L.
    Commented May 22, 2020 at 5:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.