Premium
The computational complexity of graph contractions II: Two tough polynomially solvable cases
Author(s) -
Levin Asaf,
Paulusma Daniel,
Woeginger Gerhard J.
Publication year - 2008
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20249
Subject(s) - combinatorics , mathematics , computational complexity theory , vertex (graph theory) , time complexity , discrete mathematics , graph , algorithm
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