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:  [error in script] 33 (Google Scholar)  [error in script] 
Uncontrolled Keywords:  [error in script] 
Subjects: 

Uncontrolled Keywords:  graph minors, NPcompleteness, treewidth 
Subjects:  68XX Computer science > 68Qxx Theory of computing > 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R10 Graph theory 
Divisions:  Mathematical Institute 
Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  19 Jan 2012 10:57 
ZAIK Number:  [error in script] 

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 