CoreSource checked

VF2 Graph Isomorphism

Tests graph or subgraph isomorphism by backtracking over node mappings with feasibility pruning.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Graph Traversal
Difficulty: Intermediate
Family: Graph Isomorphism
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 0
Relationships: 4
Code example: Ready
Visualization: Ready
Aliases: VF2

Overview

VF2 grows a partial mapping between two graphs and rejects candidate node pairs when labels, adjacency to mapped nodes, or frontier constraints cannot be satisfied.

Core Concepts

graph isomorphismsubgraph isomorphismpartial mappingfeasibility pruningbacktrackingfrontier set

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(V + E)

Average

O((V + E) log V)

Worst

O(V^2 + E)

Space

O(V + E)

When to Use

Use when an exact isomorphism or subgraph-isomorphism answer is required.
Use when labels, degrees, and frontier structure provide useful pruning.

When Not to Use

Avoid when a similarity score or approximate embedding is the real requirement.
Avoid expecting predictable polynomial-time behavior on adversarial or highly symmetric graphs.

What It Does

Searches for an exact node mapping that preserves graph structure.
Uses feasibility rules to prune impossible mapping extensions early.
Supports graph or subgraph isomorphism depending on the matcher setup.

Use Cases

Exact graph matching for small to medium structured graphs.
Substructure search in labeled graphs when labels and adjacency must be preserved.
Library implementations that need a practical backtracking isomorphism method.

Inputs

Two graphs G_1, G_2 or a single graph G = (V, E) with vertex partitions

Outputs

Canonical graph certificate and automorphism group generators

Pseudocode

1.Start with an empty mapping and frontier sets
2.If every pattern node is mapped, report success
3.Choose a candidate pattern node and target node
4.Reject the pair if labels, adjacency, degree, or frontier rules fail
5.Add the pair to the mapping and update frontier state
6.Recurse; if it fails, undo the pair and try another candidate

Canonical Example

Input: pattern triangle A-B-C-A and target triangle X-Y-Z-X with extra tail X-W
Output: mapping A->X, B->Y, C->Z is a valid subgraph match
Explanation: The triangle edges are preserved even though the target graph contains an extra unmatched vertex.

Implementation Notes

Keep mapping, inverse mapping, and frontier sets for both graphs.
Check semantic feasibility for labels and syntactic feasibility for adjacency/frontier constraints.
Order candidates so label or degree mismatches fail before deeper recursion.

Common Pitfalls

Graph, subgraph, induced-subgraph, directed, and labeled matching have different feasibility rules.
Backtracking must restore mapping and frontier state exactly.
Degree checks alone are not sufficient; adjacency to already-mapped nodes must be preserved.