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.


Actions:
Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: 33 (Google Scholar) | 11 (Web of Science)
Uncontrolled Keywords: graph minors NP-completeness treewidth
Subjects:
  • 68-XX Computer science > 68Qxx Theory of computing > 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)

  • 68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R10 Graph theory

    		•
    Divisions: Mathematical Institute
    Related URLs:
    Deposit Information:
    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