Subgraph Isomorphism
Subgraph Isomorphism algorithm receives a target graph
and a pattern graph
as input
and searches the target graph for subgraphs that are isomorphic to the pattern graph. The algorithm returns
the mappings of the pattern graph vertices onto the target graph vertices.
Operation | Computational methods | Programming Interface |
Mathematical formulation
Subgraphs definition
A graph
is called a subgraph of graph
if
and
contains all the endpoints of all the
edges in
[Gross2014].
Further we denote the induced subgraph on the vertex set
as
induced
subgraph, the induced subgraph on the edge set
as non-induced
subgraph.Computing
Given two graphs
and
, the problem is to determine whether graph
contains
a subgraph isomorphic to graph
and find the exact mapping of subgraph
in
graph
.
target
graph, pattern
graph.Mapping is a bijection or one-to-one correspondence between vertices of
and a subgraph of
graph
. Two vertices are adjacent if there is an existing edge between them, and non-adjacent otherwise.
Induced subgraph isomorphism preserves both adjacency and non-adjacency relationships between vertices,
while non-induced subgraph isomorphism preserves only adjacency relationship.
Example

For the example above, the mappings for subgraph
in graph
are:
- Induced: [3, 0, 1, 4, 2, 5]
- Non-induced: [3, 0, 1, 4, 2, 5], [3, 6, 1, 4, 2, 5], [6, 0, 1, 2, 4, 5], and [4, 0, 1, 5, 6, 2]
The notation [3, 0, 1, 4, 2, 5] means that:
- pattern vertex with id 0 is mapped on vertex in target graph with id 3
- pattern vertex with id 1 is mapped on vertex in target graph with id 0
- pattern vertex with id 2 is mapped on vertex in target graph with id 1
- pattern vertex with id 3 is mapped on vertex in target graph with id 4
- pattern vertex with id 4 is mapped on vertex in target graph with id 2
- pattern vertex with id 5 is mapped on vertex in target graph with id 5
Computation method:
fast
The method defines VF3-light algorithms with Global State Stack parallelization method
and supports induced and non-induced cases.
For more details, see [Carletti2021].
Programming Interface
Refer to API Reference: Subgraph Isomorphism.