On Graph Contractions and Induced MinorsPim van't Hof, Marcin Kaminski, Daniel Paulusma, and Dimitrios M. ThilikosDiscrete Applied Mathematics, vol. 160, no. 6, pp. 799-809, 2012. A preliminary and shorter version of the paper appeared in the Proceedings of SOFTSEM 2010, 36th International Conference on Current Trends in Theory and Practice of Computer Science, January 23-29, 2010, Spindleruv Mlyn, Czech Republic, Lecture Notes in Computer Science 5901, p. 503-514, Springer-Verlag 2010. Abstract:For a fixed graph H, the H-Contractibility problem asks if a graph is H-contractible, i.e., can be transformed into H via a series of edge contractions. The computational complexity classification of this problem is still open. So far, H has a dominating vertex in all cases known to be polynomially solvable, 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 is polynomially solvable. Furthermore, 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. 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.Download: [paper pdf] |