Subgraph Isomorphism Problem

Determine whether a target graph contains a structure-preserving copy of a pattern graph by finding an injective vertex mapping that preserves required adjacency, optionally also non-adjacency.

Version

v3 · 2026-09-06 · History

Domain-specific #

2885

Origin domain

theoretical computer science

Subdomain

graph algorithms

Aliases

Subgraph matching, Subgraph isomorphism

Core Idea

The subgraph isomorphism problem asks whether a smaller pattern graph occurs inside a target graph with its vertex and edge relations preserved. Given pattern (H=(V_H,E_H)) and target (G=(V_G,E_G)), one seeks an injective mapping \(f:V_H\to V_G\) such that every pattern edge maps to a target edge. In the induced variant, pattern nonedges must also map to target nonedges among the selected target vertices. The decision version returns yes or no; search returns a witness mapping; enumeration or counting versions return all occurrences or their number.

Scope of Application

The problem is central to graph algorithms and computational complexity and recurs in graph databases, cheminformatics, bioinformatics, circuit design, compiler optimization, model checking, computer vision, and graph rewriting. A molecular query can be a labeled pattern sought in a compound graph; a graph database query can require one relationship motif; a rewrite engine must locate the left-hand side of a rule before applying it.

Clarity

For non-induced subgraph isomorphism, require

\[ (u,v)\in E_H \Rightarrow (f(u),f(v))\in E_G. \]

For induced subgraph isomorphism, require the biconditional on distinct pattern vertices: adjacency in (H) exactly matches adjacency among their images in (G). Injectivity is separate from adjacency preservation and should be stated explicitly.

Manages Complexity

Naively, mapping (k) pattern vertices into (n) target vertices considers roughly \(n(n-1)\cdots(n-k+1)\) injective assignments. Subgraph solvers manage that explosion by removing candidates before and during search. Degree or label constraints initialize domains; neighborhood consistency removes images lacking support; choosing a highly constrained pattern vertex early reduces branching; propagation revises remaining domains after every assignment.

Abstract Reasoning

Reduction reasoning. Encode clique by setting (H=K_k), showing that a solver for general subgraph isomorphism solves an NP-complete problem.

Domain filtering. Assign each pattern vertex a set of target candidates satisfying unary constraints such as label and degree; then remove candidates without compatible neighbors.

Backtracking invariant. Maintain an injective partial map that already preserves every fully instantiated constraint. Extend it or backtrack when a domain becomes empty.

Knowledge Transfer

The constraint model transfers across domains because molecules, circuits, social motifs, syntax structures, and database records can all be represented as graphs. What transfers is literal when vertices and edges have explicit semantics and exact structure-preserving occurrence is the question.

The broader concepts isomorphism, search, constraint satisfaction, and graph_data_type travel further. The candidate remains domain-specific because its inputs, witness, validity, and complexity are fixed in graph-theoretic terms. It is a major computational problem, not a prime abstraction.

Relationships to Other Abstractions

Current abstraction Subgraph Isomorphism Problem Domain-specific

Parents (1) — more general patterns this builds on

• Subgraph Isomorphism Problem is part of Graph Data Type Domain-specific

  graph_data_type: pattern and target are represented as graph objects.

Hierarchy paths (4) — routes to 3 parentless roots

• Subgraph Isomorphism Problem → Graph Data Type → Abstract Data Type → Information Hiding → Abstraction

Show alternative paths (3)

Neighborhood in Abstraction Space

Subgraph Isomorphism Problem sits in a sparse region of the domain-specific corpus (75^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

• Pathwidth — 0.84
• Hadwiger number — 0.84
• Copying Mechanism — 0.83
• Grundy Number — 0.83
• Friendly-index set — 0.82

Computed from structural-signature embeddings · 2026-09-08