Graph Isomorphism

Test whether two graphs have the same structure (a bijection between vertices that preserves edges).

Algorithm Complexity When to use

Algorithm	Complexity	When to use
Isomorphism	O(\|V\|!) worst case	Test if two graphs are isomorphic (same structure, same size). Simple backtracking implementation.
VF2 Subgraph Isomorphism	O(V²) best / O(V! · V) worst	Test if one graph is isomorphic to an induced subgraph of another. Also exposes `vf2_graph_iso` for full-graph isomorphism and `vf2_subgraph_mono` for non-induced subgraphs. Finds all matches via a callback.
McGregor Common Subgraphs	Exponential	Find the largest subgraph common to two graphs.

O(|V|!) worst case

Test if two graphs are isomorphic (same structure, same size). Simple backtracking implementation.

O(V²) best / O(V! · V) worst

Test if one graph is isomorphic to an induced subgraph of another. Also exposes vf2_graph_iso for full-graph isomorphism and vf2_subgraph_mono for non-induced subgraphs. Finds all matches via a callback.

McGregor Common Subgraphs

Exponential

Find the largest subgraph common to two graphs.

All graph isomorphism algorithms have exponential worst-case complexity. In practice they are fast on most real-world graphs due to pruning, but they can be slow on highly symmetric or regular graphs.

Edit this Page