# NP-completeness of Induced disjoint paths

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?

• "(a set of) $k$ induced paths" as in simply $k$ different (not necessarily vertex-disjoint) paths? – dkaeae May 28 '19 at 7:35
• No, a set of $k$ paths who induce a graph with $k$ components, each being a path, I would guess. – Pål GD May 28 '19 at 7:43
• @dkaeae they have to be induced aka chordless. – Juho May 28 '19 at 7:44
• What is an induced path? – xskxzr May 29 '19 at 17:59
• @xskxzr A set of vertices that induce a subgraph that is a path. So specifically, not every path is an induced path. – Juho May 29 '19 at 20:11

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

• as a side question, can your reduction be adapted to work when the set of sources and sinks does not come in pair, i.e. a feasible solution is allowed to pair them arbitrarily. – Thinh D. Nguyen May 31 '19 at 15:14
• This seems like a completely different question. – Yuval Filmus May 31 '19 at 15:59
• So, I will ask another question. – Thinh D. Nguyen Jun 1 '19 at 9:49
• Where did you ask the other question? – heretoinfinity Apr 2 at 16:49

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.