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

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.