Skip to main content

Research Repository

Advanced Search

On graph contractions and induced minors

Hof, P. van 't; Kaminski, M.; Paulusma, D.; Szeider, S.; Thilikos, D.M.

On graph contractions and induced minors Thumbnail


Authors

P. van 't Hof

M. Kaminski

S. Szeider

D.M. Thilikos



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.

Citation

Hof, P. V. '., Kaminski, M., Paulusma, D., Szeider, S., & Thilikos, D. (2012). On graph contractions and induced minors. Discrete Applied Mathematics, 160(6), 799-809. https://doi.org/10.1016/j.dam.2010.05.005

Journal Article Type Article
Publication Date Apr 1, 2012
Deposit Date Oct 6, 2010
Publicly Available Date Mar 28, 2024
Journal Discrete Applied Mathematics
Print ISSN 0166-218X
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 160
Issue 6
Pages 799-809
DOI https://doi.org/10.1016/j.dam.2010.05.005
Keywords Graph contraction, Graph induced minor, Graph minor.
Public URL https://durham-repository.worktribe.com/output/1517168

Files

Accepted Journal Article (298 Kb)
PDF

Copyright Statement
NOTICE: this is the author's version of a work that was accepted for publication in Discrete applied mathematics.





You might also like



Downloadable Citations