Cookies

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.

Abstract

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:PDF - Accepted Version (291Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1016/j.dam.2010.05.005
Publisher statement:NOTICE: this is the author's version of a work that was accepted for publication in Discrete applied mathematics.
Record Created:06 Oct 2010 12:50
Last Modified:03 Apr 2013 13:17

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library