On graph contractions and induced minors

Pim van 't Hof, Marcin Kamiński, Daniël Paulusma, Stefan Szeider and Dimitrios M. Thilikos

Discrete Applied Mathematics, vol. 160, no. 6, pp. 799-809, 2012.
[DOI] [Preprint]

A preliminary version of this paper, entitled "On contracting graphs to fixed pattern graphs", appeared in the proceedings of SOFSEM 2010, the 36th International Conference on Current Trends in Theory and Practice of Computer Science (held on January 23-29, 2010 in Špindlerův Mlýn, Czech Republic), Lecture Notes in Computer Science, vol. 5901, pp. 503-514, 2010.
[DOI] [Slides]

This paper has also been presented at GROW 2009, the 4th Workshop on Graph Classes, Optimization and Width Parameters (held on October 15-17, 2009 in Bergen, Norway).


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 |V(H)| if G belongs to any non-trivial 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.