TY - JOUR
T1 - Subgraph isomorphism in graph classes
AU - Kijima, Shuji
AU - Otachi, Yota
AU - Saitoh, Toshiki
AU - Uno, Takeaki
N1 - Funding Information:
The authors would like to thank the anonymous referees for their helpful comments and suggestions. Part of this research is supported by the Funding Program for World-Leading Innovative R & D on Science and Technology, Japan , and Grants-in-Aid for Scientific Research from Ministry of Education, Science and Culture, Japan , and Japan Society for the Promotion of Science .
PY - 2012/11/6
Y1 - 2012/11/6
N2 - We investigate the computational complexity of the following restricted variant of Subgraph Isomorphism: given a pair of connected graphs G=(V G,E G) and H=(V H,E H), determine if H is isomorphic to a spanning subgraph of G. The problem is NP-complete in general, and thus we consider cases where G and H belong to the same graph class such as the class of proper interval graphs, of trivially perfect graphs, and of bipartite permutation graphs. For these graph classes, several restricted versions of Subgraph Isomorphism such as Hamiltonian Path, Clique, Bandwidth, and Graph Isomorphism can be solved in polynomial time, while these problems are hard in general.
AB - We investigate the computational complexity of the following restricted variant of Subgraph Isomorphism: given a pair of connected graphs G=(V G,E G) and H=(V H,E H), determine if H is isomorphic to a spanning subgraph of G. The problem is NP-complete in general, and thus we consider cases where G and H belong to the same graph class such as the class of proper interval graphs, of trivially perfect graphs, and of bipartite permutation graphs. For these graph classes, several restricted versions of Subgraph Isomorphism such as Hamiltonian Path, Clique, Bandwidth, and Graph Isomorphism can be solved in polynomial time, while these problems are hard in general.
UR - http://www.scopus.com/inward/record.url?scp=84865102283&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84865102283&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2012.07.010
DO - 10.1016/j.disc.2012.07.010
M3 - Article
AN - SCOPUS:84865102283
SN - 0012-365X
VL - 312
SP - 3164
EP - 3173
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 21
ER -