The 'subgraph isomorphism problem': Given graphs G_α and G_β, does G_β contain a subgraph that is isomorphic to G_α?

In other words, is there a 1-1 (into) mapping, ρ : V_α → V_β, such that ∀ vertices u, v, in G_α, if u and v are adjacent in G_α then vertices ρ(u) and ρ(v) are adjacent in G_β?

There are variations on the problem:

Decision problem (y/n): Is there any such isomorphism, or not?

Enumeration problem: Enumerate all such isomorphisms, if any.

We may be given directed graphs or undirected graphs.

The 'vertex induced subgraph-isomorphism problem': Does G_β contain a vertex induced subgraph that is isomorphic to G_α? In other words, is there a 1-1 mapping, ρ : V_α → V_β, such that ∀ vertices u, v, in G_α, vertices u and v are adjacent in G_α if and only if ρ(u) and ρ(v) are adjacent in G_β?

Subgraph isomorphism is an NP-complete problem. (For a fixed G_α the problem is polynomial in |G_β| but the polynomial depends on G_α.)

The following assumes undirected graphs, symmetric matrices.

Sources

Search for [subgraph isomorphism] in the [bib].