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.
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 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.
Item Type: | Article |
---|---|
Citations: | 33 (Google Scholar) | 11 (Web of Science) |
Uncontrolled Keywords: | graph minors NP-completeness treewidth |
Subjects: |
|
Divisions: | Mathematical Institute |
Related URLs: |
ZAIK Number: | zpr91-101 |
---|---|
Depositing User: | Archive Admin |
Date Deposited: | 02 Apr 2001 00:00 |
Last Modified: | 19 Jan 2012 10:57 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/101 |