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

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.