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 graph H, Induced H-Minor Testing can be accomplished for planar graphs in time O(n), and (3) there are graphs H for which Induced H-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.