Subgraph Isomorphism

A graph is the simplest map there is: a handful of dots (vertices) joined by lines (edges). Friendships, molecules, road systems, web pages — almost anything made of things and connections is a graph.

Now a natural question: given a small pattern graph and a big target graph, does the pattern appear somewhere inside the target? Not the exact same drawing — we are allowed to bend and relabel — but the same shape of connections. This is the subgraph isomorphism problem.

It sounds like a game of spot-the-shape, and for tiny graphs it is. But as the graphs grow, the number of ways to line up pattern vertices against target vertices explodes, and there is no known shortcut. That little gap between "I found a match" and "I can prove there is none" turns out to be one of the deepest dividing lines in computer science.

Below is a small pattern graph and a larger target graph. The matcher tries to map each pattern vertex onto a target vertex so that every pattern edge lands on a real target edge. Press Search and watch it assign vertices one by one, backtracking whenever a partial map can't be completed.

<p class="hint">{{hint}}</p>
<div class="stage">
  <div class="panel">
    <div class="cap">{{cap_pattern}}</div>
    <svg id="pat" viewBox="0 0 160 160"></svg>
  </div>
  <div class="panel">
    <div class="cap">{{cap_target}}</div>
    <svg id="tgt" viewBox="0 0 240 200"></svg>
  </div>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="search" type="button">{{btn_search}}</button>
  <button id="shuffle" type="button" class="ghost">{{btn_shuffle}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.stage { display: flex; gap: 1rem; flex-wrap: wrap; }
.panel { background: #f3f6f9; border: 1px solid #d8e0e8; border-radius: 10px; padding: .5rem; }
.cap { font: 700 13px system-ui; color: #1d3557; margin-bottom: .2rem; }
svg { display: block; }
.edge { stroke: #adb5bd; stroke-width: 3; }
.edge.lit { stroke: #0a7d33; stroke-width: 4; }
.node { fill: #c9ccd1; stroke: #8b929b; stroke-width: 2; }
.node.mapped { fill: #1d3557; stroke: #122440; }
.node.cur { fill: #e63946; stroke: #c92f3c; }
.nlabel { font: 700 13px ui-monospace, monospace; fill: #fff; text-anchor: middle; dominant-baseline: central; }
.nlabel.dark { fill: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: default; }

// Code not found

Notice the asymmetry. Verifying a proposed mapping is instant: check each pattern edge and confirm the matching target edge exists. Finding the mapping is the hard part — the matcher may try many dead ends before it succeeds or proves no embedding exists. Shuffle the target a few times and watch the number of backtracking steps swing wildly.

How hard is subgraph isomorphism, really?

• Checking a candidate mapping is easy: given which pattern vertex goes to which target vertex, just confirm every pattern edge maps to an existing target edge — that is polynomial time. So the problem sits in NP.
• Brute force tries every way to assign the k pattern vertices to the n target vertices: that is up to n × (n-1) × … × (n-k+1) mappings, which explodes exponentially.
• It is NP-complete. The decision version was among the problems shown NP-complete in the wave following Stephen Cook's 1971 theorem and Richard Karp's 1972 list. The classic argument: the clique problem — "does the target contain k mutually-connected vertices?" — is just subgraph isomorphism where the pattern is a complete graph on k vertices. Since clique is NP-complete, so is subgraph isomorphism.
• Smart matchers exist — Ullmann's 1976 algorithm and modern ones like VF2 prune the search hard — but their worst case is still exponential. No polynomial-time general algorithm is known.

That is the punchline: the moment your pattern is big enough that local checks can't settle it, you are facing a genuine instance of the same wall behind P vs NP. (Beware a cousin: deciding whether two whole graphs are isomorphic — graph isomorphism — is not known to be NP-complete and may be strictly easier. Adding "is it a subgraph" is what makes this version hard.)

"Find this shape inside that network" is one of the most useful questions you can ask, and it is exactly subgraph isomorphism:

• Chemistry and drug discovery: a molecule is a graph of atoms and bonds. Searching a database for compounds that contain a given substructure (a reactive group, a drug scaffold) is substructure search — subgraph isomorphism at industrial scale.
• Social networks and security: looking for a specific interaction pattern — a fraud ring, a money-laundering cycle, a community motif — means hunting that pattern inside a giant relationship graph.
• Biology: recurring network motifs in gene-regulation or protein-interaction networks are found by counting small subgraphs.
• Software and data: detecting duplicated code, matching query patterns in knowledge graphs, and recognizing shapes in computer-vision scene graphs all reduce to embedding a pattern in a host.

Understand subgraph isomorphism and you have met graph pattern matching — the engine under cheminformatics, network analysis, and any system that asks "where does this appear?" It is a close relative of clique and the broader family around P vs NP.

Subgraph isomorphism hides a familiar twist: confirming a match is the work of a moment, while finding one — or proving none exists — can demand exponential search. It is NP-complete, provably as hard as any problem in NP, and yet it quietly runs every time a chemist searches for a scaffold or an analyst hunts a fraud ring.

So the next time a pattern search feels slow, it is not a bug in the software — it is intractability made practical. You have run into P vs NP again, this time wearing the friendly face of dots and lines, and the clever shortcut may simply not exist.