In complexity theory and graph theory, induced subgraph isomorphism is an NP-complete decision problem that involves finding a given graph as an induced subgraph of a larger graph.
Formally, the problem takes as input two graphs G<sub>1</sub>=(V<sub>1</sub>, E<sub>1</sub>) and G<sub>2</sub>=(V<sub>2</sub>, E<sub>2</sub>), where the number of vertices in V<sub>1</sub> can be assumed to be less than or equal to the number of vertices in V<sub>2</sub>. G<sub>1</sub> is isomorphic to an induced subgraph of G<sub>2</sub> if there is an injective function f which maps the vertices of G<sub>1</sub> to vertices of G<sub>2</sub> such that for all pairs of vertices x, y in V<sub>1</sub>, edge (x, y) is in E<sub>1</sub> if and only if the edge (f(x), f(y)) is in E<sub>2</sub>. The answer to the decision problem is yes if this function f exists, and no otherwise.
This is different from the subgraph isomorphism problem in that the absence of an edge in G<sub>1</sub> implies that the corresponding edge in G<sub>2</sub> must also be absent. In subgraph isomorphism, these "extra" edges in G<sub>2</sub> may be present.
The complexity of induced subgraph isomorphism separates outerplanar graphs from their generalization seriesâÂÂparallel graphs: it may be solved in polynomial time for 2-connected outerplanar graphs, but is NP-complete for 2-connected seriesâÂÂparallel graphs.
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. 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, but the induced subgraph isomorphism problem can be solved in polynomial time on these two classes.
Moreover, the induced subtree isomorphism problem (i.e. the induced subgraph isomorphism problem where G<sub>1</sub> 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.