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
    $\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$ – Yuval Filmus May 21 at 13:13
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$.

| cite | improve this answer | |
$\endgroup$
  • $\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 May 21 at 13:42
  • $\begingroup$ Yes, this is correct. In particular $E'$ contains all possible edges. $H$ is a complete graph. $\endgroup$ – Steven May 21 at 13:44
  • $\begingroup$ I think you can remove $V$ from $V'$, though it's not a big difference. $\endgroup$ – Yuval Filmus May 21 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 May 21 at 14:08
  • $\begingroup$ Nice answer! $\quad$ $\endgroup$ – John L. May 22 at 5:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy