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

作者：Kawarabayashi Ken ichi; Kobayashi Yusuke^*

来源：Journal of Computer and System Sciences, 2012, 78(2): 670-680.

DOI：10.1016/j.jcss.2011.10.004

• Disjoint paths
• Induced subgraph
• Planar graph
• Linear time algorithm

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 {(s(1), t(1)), ... ,(s(k), t(k))}. The objective is to find k paths P-1, ..., P-k such that P-i is a path from s(i) to t(i) and P-i and P-j 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].

• 出版日期2012-3