Subgraph Isomorphism

 LA home Computing Algorithms  glossary  Graphs   Directed   DAG   Undirected   DF Trav   Canonical   Isomorphism   Subg. Iso.   Stable mrrg.   Subg. Iso. also see   enum.subG.
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.

–mα –mβ

output:

Sources

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