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 '19 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 '19 at 7:43
  • $\begingroup$ @dkaeae they have to be induced aka chordless. $\endgroup$ – Juho May 28 '19 at 7:44
  • $\begingroup$ What is an induced path? $\endgroup$ – xskxzr May 29 '19 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 '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$.

  • $\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$ – Thinh D. Nguyen May 31 '19 at 15:14
  • $\begingroup$ This seems like a completely different question. $\endgroup$ – Yuval Filmus May 31 '19 at 15:59
  • $\begingroup$ So, I will ask another question. $\endgroup$ – Thinh D. Nguyen Jun 1 '19 at 9:49
  • $\begingroup$ Where did you ask the other question? $\endgroup$ – 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.


Your Answer

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

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