Subgraph Isomorphism is the NP-complete computational problem of determining whether a pattern graph $H$ appears as a subgraph within a larger host graph $G$ — finding a node-injective mapping $f: V_H o V_G$ such that every edge in $H$ maps to an edge in $G$, the fundamental algorithmic primitive underlying molecular substructure search, knowledge graph querying, and network motif detection.

What Is Subgraph Isomorphism?

• Definition: Given a pattern graph $H = (V_H, E_H)$ and a host graph $G = (V_G, E_G)$ where $|V_H| leq |V_G|$, subgraph isomorphism asks whether there exists an injective mapping $f: V_H o V_G$ such that $(u, v) in E_H implies (f(u), f(v)) in E_G$. In the induced variant, the condition is strengthened to require $(u, v) in E_H iff (f(u), f(v)) in E_G$ — the matched subgraph must have exactly the same edges as $H$, no more and no less.
• NP-Completeness: Unlike full graph isomorphism (which has unknown complexity), subgraph isomorphism is definitively NP-complete — it includes the clique problem, the Hamiltonian path problem, and many other NP-complete problems as special cases. This means no polynomial-time algorithm exists (assuming P ≠ NP), and all exact algorithms have exponential worst-case running time.
• Counting Variant: The counting variant — how many distinct copies of $H$ exist in $G$ — is even harder (#P-complete). Counting triangles, 4-cliques, or other motifs in large graphs requires specialized approximate counting algorithms because exact enumeration is intractable.

Why Subgraph Isomorphism Matters

• Molecular Substructure Search: The most common operation in chemical informatics is querying "find all molecules in the database that contain this functional group." This is subgraph isomorphism — the functional group (benzene ring, hydroxyl group, amide bond) is the pattern $H$, and each database molecule is the host $G$. Pharmaceutical companies run billions of such queries daily for drug screening.
• Knowledge Graph Querying: SPARQL queries on knowledge graphs (Wikidata, Freebase) are subgraph pattern matches — "find all (Person, born_in, City) where City.country = USA" is a subgraph isomorphism query where the pattern is a small graph with typed nodes and edges. Query engines like GraphQL and Neo4j's Cypher implement optimized subgraph matching at their core.
• Network Motif Detection: Identifying statistically significant subgraph patterns (network motifs) in biological networks requires counting subgraph occurrences. The feed-forward loop motif in gene regulatory networks and the bi-fan motif in neural circuits are discovered by enumerating all occurrences of small pattern graphs and testing for statistical over-representation.
• Code Pattern Detection: Finding specific code patterns (design patterns, anti-patterns, vulnerabilities) in program dependency graphs is subgraph isomorphism — the pattern graph represents the code structure of interest, and the host graph represents the program being analyzed.

Subgraph Isomorphism Algorithms

Subgraph Isomorphism is pattern finding in networks — searching for a specific structural motif inside a larger graph, the algorithmic workhorse that powers molecular database search, knowledge graph querying, and biological network motif analysis despite its fundamental computational intractability.