|
|
- 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].
|
|