NP-completeness of Induced disjoint paths

Question

In graph theory, it is well-known to be NP-complete the problem of given a set of $k$ pairs of source-sink, deciding whether there exists $k$ vertex-disjoint paths connecting these pairs.

Our problem is a variant in which the requirement of being vertex-disjoint is replaced by being induced.

A set of $k$ paths is said to be induced if:

1. They are vertex-disjoint.
2. Each one is itself an induced path.
3. No edge connects two vertices of two different paths.

Input: A graph $G(V,E)$ and $k$ pairs of source-sink $\{(s_1,t_1),\dots,(s_k,t_k)\}$

Output: YES if there exists (a set of) $k$ induced paths connecting $s_i$ to $t_i$ for every $1\leq i\leq k$, NO otherwise.

Is this problem NP-complete?

Answer 1

Your problem is NP-hard (and so NP-complete), by reduction from 3SAT.

Consider a 3SAT instances with variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$.

For each variable $x_i$, there are four vertices $a_i,T_i,F_i,b_i$, connected as follows: $a_i-T_i-b_i$ and $a_i-F_i-b_i$.

For each clause $C_j = \ell_{j,1} \lor \ell_{j,2} \lor \ell_{j,3}$ (where $\ell_{j,1},\ell_{j,2},\ell_{j,3}$ are literals), there are five vertices $c_j,L_{j,1},L_{j,2},L_{j,3},d_j$, connected as follows: $c_j-L_{j,k}-d_j$ (for $k=1,2,3$). Additionally, if $\ell_{j,k} = x_i$ then we connect $L_{j,k}$ with $F_i$, and if $\ell_{j,k} = \bar{x}_i$ then we connect $L_{j,k}$ with $T_i$.

The source-sink pairs are $(a_i,b_i)$ (for $i=1,\ldots,n$) and $(c_j,d_j)$ (for $j=1,\ldots,m$).

Each $a_i-b_i$ path corresponds to a truth assignment of $x_i$, and each $c_j-d_j$ path corresponds to a choice of a satisfied literal in $C_j$.

Answer 2

Another way to see that this problem is NP-hard would be to construct a reduction from the "$k$ vertex-disjoint paths" problem mentioned in the question itself. The reduction takes the input graph $G$ and subdivides every edge — i.e. a new vertex $v_{ab}$ is introduced for each edge $ab$ of $G$ and the the edge $ab$ is replaced with the path $a,v_{ab},b$ — to obtain a new graph $G'$. Note that $G'$ is a bipartite graph with partite sets $V(G)$ (the old vertices) and $\{v_e\colon e\in E(G)\}$ (the new vertices), with the additional property that every new vertex has degree 2. It is quite straightforward to see that there is a set of $k$ vertex-disjoint paths in $G$ (between the given terminals) if and only if there is a set of $k$ induced paths (between the same terminals) in $G'$. For each path $P=a_1,a_2,\ldots,a_t$ in $G$, let $P'$ be the path $a_1,v_{a_1a_2},a_2,v_{a_2a_3},a_3,\ldots,a_{t-1},v_{a_{t-1}a_t},a_t$ in $G'$. If $P_1,P_2,\ldots,P_k$ is a set of $k$ vertex-disjoint paths in $G$, then $P'_1,P'_2,\ldots,P'_k$ form a set of $k$ induced paths in $G'$ between the same pairs of terminals. (Note that for every new vertex that appears on a path $P'_i$, the two edges incident on that vertex also belong to $P'_i$. Also, one endpoint of every edge in $G'$ is a new vertex, and the terminal vertices of each path $P'_i$ are old vertices. Thus there can be no edge in $G'$ between vertices that lie on two different paths $P'_i$ and $P'_j$, or between two non-consecutive vertices of some path $P'_i$.) Similarly, consider a path $Q$ between two old vertices $x$ and $y$ in $G'$. Then $Q$ is of the form $x=a_1,b_1,a_2,b_2,\ldots,b_{t-1},a_t=y$ where $a_1,a_2,\ldots,a_t$ are old vertices and $b_1,b_2,\ldots,b_{t-1}$ are new vertices. Clearly, for $i\in\{1,2,\ldots,t-1\}$, $b_i=v_{a_ia_{i+1}}$, which also means that $a_ia_{i+1}\in E(G)$. Let $Q^*$ be the path $a_1,a_2,\ldots,a_t$ in $G$. Now if $Q_1,Q_2,\ldots,Q_k$ form a set of $k$ induced paths (in fact even just a set of $k$ vertex-disjoint paths) in $G'$, then $Q_1^*,Q_2^*,\ldots,Q_k^*$ are vertex-disjoint paths in $G$ between the same pairs of terminals.