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: | Export: EndNote, Zotero | BibTex |

Usage statistics | Look up in GoogleScholar | Find in a UK Library |