The complexity of induced minors and related problems

The computational complexity of a number of problems concerning induced structures in graphs is studied, and compared with the complexity of corresponding problems concerning non-induced structures. The effect on these problems of restricting the input to planar graphs is also considered. The principal results include: (1) Induced Maximum Matching and Induced Directed Path are NP-complete for planar graphs, (2) for every fixed graphH, InducedH-Minor Testing can be accomplished for planar graphs in time0(n), and (3) there are graphsH for which InducedH-Minor Testing is NP-complete for unrestricted input. Some useful structural theorems concerning induced minors are presented, including a bound on the treewidth of planar graphs that exclude a planar induced minor.The research of the first author was supported by the U.S. Office of Naval Research under Contract N00014-88-K-0456, by the U.S. National Science Foundation under Grant MIP-8603879, and by the National Science and Engineering Research Council of Canada. The second author acknowledges the support of the U.S. Office of Naval Research when visiting the University of Idaho in spring 1990. Some results were also obtained during a visit to the University of Cologne in fall 1990.