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?

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

2 Answers 2


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

  • $\begingroup$ 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. $\endgroup$ May 31, 2019 at 15:14
  • $\begingroup$ This seems like a completely different question. $\endgroup$ May 31, 2019 at 15:59
  • $\begingroup$ So, I will ask another question. $\endgroup$ Jun 1, 2019 at 9:49
  • $\begingroup$ Where did you ask the other question? $\endgroup$ Apr 2, 2021 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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.