Induced subgraph isomorphism problem

[1][2] The special case of finding a long path as an induced subgraph of a hypercube has been particularly well-studied, and is called the snake-in-the-box problem.

[3] The maximum independent set problem is also an induced subgraph isomorphism problem in which one seeks to find a large independent set as an induced subgraph of a larger graph, and the maximum clique problem is an induced subgraph isomorphism problem in which one seeks to find a large clique graph as an induced subgraph of a larger graph.

Although the induced subgraph isomorphism problem seems only slightly different from the subgraph isomorphism problem, the "induced" restriction introduces changes large enough that we can witness differences from a computational complexity point of view.

For example, the subgraph isomorphism problem is NP-complete on connected proper interval graphs and on connected bipartite permutation graphs,[4] but the induced subgraph isomorphism problem can be solved in polynomial time on these two classes.

[5] Moreover, the induced subtree isomorphism problem (i.e. the induced subgraph isomorphism problem where G1 is restricted to be a tree) can be solved in polynomial time on interval graphs, while the subtree isomorphism problem is NP-complete on proper interval graphs.