The computational complexity of graph contractions II: Two tough polynomially solvable cases

For a fixed pattern graph H , let H ‐C ONTRACTIBILITY denote the problem of deciding whether a given input graph is contractible to H . This article is part II of our study on the computational complexity of the H ‐C ONTRACTIBILITY problem. In the first article we pinpointed the complexity for all pattern graphs with five vertices except for two pattern graphs H . Here, we present polynomial time algorithms for these two remaining pattern graphs. Interestingly, in all connected cases that are known to be polynomially solvable, the pattern graph H has a dominating vertex, whereas in all cases that are known to be NP‐complete, the pattern graph H does not have a dominating vertex. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008