We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

On graph contractions and induced minors.

Hof, P. van 't and Kaminski, M. and Paulusma, Daniel and Szeider, S. and Thilikos, D.M. (2012) 'On graph contractions and induced minors.', Discrete applied mathematics., 160 (6). pp. 799-809.


The Induced Minor Containment problem takes as input two graphs G and H, and asks whether G has H as an induced minor. We show that this problem is fixed parameter tractable in |VH| if G belongs to any nontrivial minor-closed graph class and H is a planar graph. For a fixed graph H, the H-Contractibility problem is to decide whether a graph can be contracted to H. The computational complexity classification of this problem is still open. So far, H has a dominating vertex in all cases known to be solvable in polynomial time, whereas H does not have such a vertex in all cases known to be NP-complete. Here, we present a class of graphs H with a dominating vertex for which H-Contractibility is NP-complete. We also present a new class of graphs H for which H-Contractibility can be solved in polynomial time. Finally, we study the (H,v)-Contractibility problem, where v is a vertex of H. The input of this problem is a graph G and an integer k, and the question is whether G is H-contractible such that the “bag” of G corresponding to v contains at least k vertices. We show that this problem is NP-complete whenever H is connected and v is not a dominating vertex of H.

Item Type:Article
Keywords:Graph contraction, Graph induced minor, Graph minor.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:NOTICE: this is the author's version of a work that was accepted for publication in Discrete applied mathematics.
Date accepted:No date available
Date deposited:07 October 2010
Date of first online publication:April 2012
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar