Induced subgraph isomorphism problem

From Wikipedia, the free encyclopedia

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₁=(V₁, E₁) and G₂=(V₂, E₂), where the number of vertices in V₁ can be assumed to be less than or equal to the number of vertices in V₂. G₁ is isomorphic to an induced subgraph of G₂ if there is an injective function f which maps the vertices of G₁ to vertices of G₂ such that for all pairs of vertices x, y in V₁, edge (x, y) is in E₁ if and only if the edge (f(x), f(y)) is in E₂. 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₁ implies that the corresponding edge in G₂ must also be absent. In subgraph isomorphism, these "extra" edges in G₂ may be present.

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.