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. 266282.
Abstract
The computational complexity of a number of problems concerning induced structures in graphs is studied, and compared with the complexity of corresponding problems concerning noninduced 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 NPcomplete for planar graphs, (2) for every fixed graph H, induced Hminor testing can be accomplished for planar graphs O(n), and (3) there are graphs H for which induced H minor testing is NPcomplete 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.
Item Type:  Article 

Citations:  33 (Google Scholar)  11 (Web of Science) 
Uncontrolled Keywords:  graph minors NPcompleteness treewidth 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
ZAIK Number:  zpr91101 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  19 Jan 2012 10:57 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/101 