Developer Guide and Reference

  • 2021.6
  • 04/11/2022
  • Public Content
Contents

Subgraph Isomorphism

Subgraph Isomorphism algorithm receives a target graph LaTex Math image. and a pattern graph LaTex Math image. 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 LaTex Math image. is called a subgraph of graph LaTex Math image. if LaTex Math image. and LaTex Math image. contains all the endpoints of all the edges in LaTex Math image. [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 LaTex Math image. and LaTex Math image., the problem is to determine whether graph LaTex Math image. contains a subgraph isomorphic to graph LaTex Math image. and find the exact mapping of subgraph LaTex Math image. in graph LaTex Math image..
LaTex Math image. is called
target
graph, LaTex Math image. is called
pattern
graph.
Mapping is a bijection or one-to-one correspondence between vertices of LaTex Math image. and a subgraph of graph LaTex Math image.. 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 LaTex Math image. in graph LaTex Math image. 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

Examples

oneAPI C++
Batch Processing:

Product and Performance Information

1

Performance varies by use, configuration and other factors. Learn more at www.Intel.com/PerformanceIndex.