Induced disjoint paths problem in a planar digraph

As an extension of the disjoint paths problem, we introduce a new problem which we call the induced disjoint paths problem. In this problem we are given a graph GG and a collection of vertex pairs {(s1,t1),…,(sk,tk)}{(s1,t1),…,(sk,tk)}. The objective is to find kk paths P1,…,PkP1,…,Pk such that PiPi is a path from sisi to titi and PiPi and PjPj have neither common vertices nor adjacent vertices for any distinct i,ji,j.The induced disjoint paths problem has several variants depending on whether kk is a fixed constant or a part of the input, whether the graph is directed or undirected, and whether the graph is planar or not. We investigate the computational complexity of several variants of the induced disjoint paths problem. We show that the induced disjoint paths problem is (i) solvable in polynomial time when kk is fixed and GG is a directed (or undirected) planar graph, (ii) NP-hard when k=2k=2 and GG is an acyclic directed graph, (iii) NP-hard when k=2k=2 and GG is an undirected general graph.As an application of our first result, we show that we can find in polynomial time certain structures called a “hole” and a “theta” in a planar graph.