A linear time algorithm for the induced disjoint paths problem in planar graphs

摘要

In this paper, we consider a problem which we call the induced disjoint paths problem (IDPP) for planar graphs.We are given a planar graph G and a collection of vertex pairs {(s1,t1),…,(sk,tk)}. The objective is to find k paths P1,…,Pk such that Pi is a path from si to ti and Pi and Pj have neither common vertices nor adjacent vertices for any distinct i,j.This problem setting is a generalization of the disjoint paths problem, since if we subdivide each edge, then desired disjoint paths would be induced disjoint paths. The problem is motivated by not only the disjoint paths problem but also the recognition of an induced subgraph. The latter has been developed in recent years, and this is actually connected to the Strong Perfect Graph Theorem (Chudnovsky, et al., 2006) [1], and the recognition of the perfect graphs (Chudnovsky, et al., 2005) [2].Our main result in this paper is to give a linear time algorithm for the IDPP for planar graphs. This generalizes the result by Reed, Robertson, Schrijver and Seymour (1993) [14]. This also gives a polynomial time algorithm to find an induced circuit through given k vertices in planar graphs if one exists when k is fixed. The case k=2 was previously proved by McDiarmid, Reed, Schrijver and Shepherd (1994) [10].