On graph contractions and induced minors

Pim van 't Hof, Marcin Kaminski, Daniël Paulusma, Stefan Szeider, Dimitrios M. Thilikos

Research output: Contribution to journalConference articleAcademicpeer-review

25 Citations (Scopus)
1 Downloads (Pure)

Abstract

The Induced Minor Containment problem takes as input two graphs and , and asks whether has as an induced minor. We show that this problem is fixed parameter tractable in if belongs to any nontrivial minor-closed graph class and is a planar graph. For a fixed graph , the -Contractibility problem is to decide whether a graph can be contracted to . The computational complexity classification of this problem is still open. So far, has a dominating vertex in all cases known to be solvable in polynomial time, whereas does not have such a vertex in all cases known to be NP-complete. Here, we present a class of graphs with a dominating vertex for which -Contractibility is NP-complete. We also present a new class of graphs for which -Contractibility can be solved in polynomial time. Finally, we study the -Contractibility problem, where is a vertex of . The input of this problem is a graph and an integer , and the question is whether is -contractible such that the “bag” of corresponding to contains at least vertices. We show that this problem is NP-complete whenever is connected and is not a dominating vertex of .
Original languageEnglish
Pages (from-to)799-809
Number of pages11
JournalDiscrete applied mathematics
Volume160
Issue number6
DOIs
Publication statusPublished - 2012
Externally publishedYes
Event4th Workshop on Graph Classes, Optimization, and Width Parameters, GROW 2009 - Bergen, Norway
Duration: 31 Dec 200931 Dec 2009
Conference number: 4

Fingerprint Dive into the research topics of 'On graph contractions and induced minors'. Together they form a unique fingerprint.

Cite this