The Complexity of Induced Minors and Related Problems

Fellows, Michael and Kratochvil, Jan and Middendorf, Matthias and Pfeiffer, Frank (1995) The Complexity of Induced Minors and Related Problems.
Published in: Algorithmica Vol. 13 (3). pp. 266-282.


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 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.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr91-101
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 10:57