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

www:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Monday, 25-Mar-2019 21:10:10 EDT.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.