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 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 at 7:43
• @dkaeae they have to be induced aka chordless. – Juho May 28 at 7:44
• What is an induced path? – xskxzr May 29 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 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 at 15:14
• This seems like a completely different question. – Yuval Filmus May 31 at 15:59
• So, I will ask another question. – Thinh D. Nguyen Jun 1 at 9:49