Introduction

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.

Hunt the Pattern

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">Left: a small <b>pattern</b> graph. Right: a larger <b>target</b>. The matcher maps each pattern vertex to a target vertex so that every pattern edge becomes a real target edge. Press <b>Search</b> to watch it assign vertices and <b>backtrack</b>. Verifying a map is instant; finding one can blow up.</p>
<div class="stage">
  <div class="panel">
    <div class="cap">Pattern</div>
    <svg id="pat" viewBox="0 0 160 160"></svg>
  </div>
  <div class="panel">
    <div class="cap">Target</div>
    <svg id="tgt" viewBox="0 0 240 200"></svg>
  </div>
</div>
<div class="status" id="status">Press Search to hunt the pattern.</div>
<div class="btns">
  <button id="search" type="button">Search</button>
  <button id="shuffle" type="button" class="ghost">Shuffle target</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Subgraph isomorphism: can the PATTERN be embedded in the TARGET so every
// pattern edge maps to a target edge? Checking a map is a quick edge scan;
// finding one is NP-complete. We use backtracking (Ullmann-style) and animate it.

// Pattern: a triangle 0-1-2 plus a tail 2-3 (a "kite handle").
const PN = 4;
const PE = [[0,1],[1,2],[2,0],[2,3]];
const PPOS = [[40,40],[120,40],[80,100],[80,150]];

// Target: 6 vertices. Layout fixed; adjacency reshuffled to vary difficulty.
const TN = 6;
const TPOS = [[40,40],[120,30],[200,55],[60,120],[150,120],[210,150]];
let TE = [];           // target edges
let adj = [];          // adjacency matrix

function buildAdj(){
  adj = Array.from({length:TN},()=>Array(TN).fill(false));
  for(const [a,b] of TE){ adj[a][b]=true; adj[b][a]=true; }
}
const padj = Array.from({length:PN},()=>Array(PN).fill(false));
for(const [a,b] of PE){ padj[a][b]=true; padj[b][a]=true; }

function makeTarget(){
  // Guarantee at least one embedding exists: pick 4 distinct target vertices
  // as a planted copy of the pattern, then add a few random extra edges.
  const perm = [...Array(TN).keys()];
  for(let i=perm.length-1;i>0;i--){ const j=Math.floor(Math.random()*(i+1)); [perm[i],perm[j]]=[perm[j],perm[i]]; }
  const set = new Set();
  const add=(a,b)=>{ const k=a<b?a+'-'+b:b+'-'+a; set.add(k); };
  for(const [a,b] of PE) add(perm[a], perm[b]);   // planted pattern
  // sprinkle random noise edges
  let tries=0;
  while(set.size < PE.length+3 && tries<40){ tries++;
    const a=Math.floor(Math.random()*TN), b=Math.floor(Math.random()*TN);
    if(a!==b) add(a,b);
  }
  TE = [...set].map(s=>s.split('-').map(Number));
  buildAdj();
}

// ── Backtracking matcher. Returns {ok, map, steps}. map[p] = target vertex. ──
function solve(){
  const map = Array(PN).fill(-1);
  const used = Array(TN).fill(false);
  let steps = 0;
  function consistent(p, t){
    for(let q=0;q<p;q++){ if(padj[p][q] && !adj[t][map[q]]) return false; }
    return true;
  }
  function bt(p){
    if(p===PN) return true;
    for(let t=0;t<TN;t++){ steps++;
      if(used[t]) continue;
      if(!consistent(p,t)) continue;
      map[p]=t; used[t]=true;
      if(bt(p+1)) return true;
      map[p]=-1; used[t]=false;
    }
    return false;
  }
  const ok = bt(0);
  return { ok, map: ok?map.slice():null, steps };
}

// ── Rendering ──
function drawGraph(svg, n, edges, pos, mapInfo){
  svg.innerHTML='';
  const NS='http://www.w3.org/2000/svg';
  for(const [a,b] of edges){
    const l=document.createElementNS(NS,'line');
    l.setAttribute('x1',pos[a][0]); l.setAttribute('y1',pos[a][1]);
    l.setAttribute('x2',pos[b][0]); l.setAttribute('y2',pos[b][1]);
    l.setAttribute('class','edge'+(mapInfo&&mapInfo.litEdges&&mapInfo.litEdges.has((a<b?a+'-'+b:b+'-'+a))?' lit':''));
    svg.appendChild(l);
  }
  for(let i=0;i<n;i++){
    const c=document.createElementNS(NS,'circle');
    c.setAttribute('cx',pos[i][0]); c.setAttribute('cy',pos[i][1]); c.setAttribute('r',16);
    let cls='node';
    if(mapInfo){ if(mapInfo.cur===i) cls+=' cur'; else if(mapInfo.mapped&&mapInfo.mapped.has(i)) cls+=' mapped'; }
    c.setAttribute('class',cls);
    svg.appendChild(c);
    const t=document.createElementNS(NS,'text');
    t.setAttribute('x',pos[i][0]); t.setAttribute('y',pos[i][1]);
    t.setAttribute('class','nlabel'+(cls==='node'?' dark':''));
    t.textContent=String.fromCharCode((svg.id==='pat'?80:65)+i); // P:A.. / T:A..
    svg.appendChild(t);
  }
}

function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

function renderStatic(){
  drawGraph(document.getElementById('pat'), PN, PE, PPOS, null);
  drawGraph(document.getElementById('tgt'), TN, TE, TPOS, null);
}

function animateResult(res){
  const btn=document.getElementById('search'); btn.disabled=true;
  if(!res.ok){
    setStatus(fmt('No embedding exists (checked %steps% assignments).', { steps: res.steps }),'bad');
    btn.disabled=false; return;
  }
  const mappedT=new Set(), mappedP=new Set();
  let i=0;
  const timer=setInterval(()=>{
    if(i>=PN){ clearInterval(timer);
      // light up matched edges on both graphs
      const lit=new Set();
      for(const [a,b] of PE){ const ta=res.map[a], tb=res.map[b]; lit.add(ta<tb?ta+'-'+tb:tb+'-'+ta); }
      drawGraph(document.getElementById('tgt'), TN, TE, TPOS, {mapped:mappedT, litEdges:lit});
      const litP=new Set(); for(const [a,b] of PE) litP.add(a<b?a+'-'+b:b+'-'+a);
      drawGraph(document.getElementById('pat'), PN, PE, PPOS, {mapped:mappedP, litEdges:litP});
      setStatus(fmt('Found! Pattern embeds via %map% (%steps% steps).', { map: res.map.map((t,p)=>String.fromCharCode(80+p)+'→'+String.fromCharCode(65+t)).join(', '), steps: res.steps }),'ok');
      console.log('mapping', res.map, 'steps', res.steps);
      btn.disabled=false; return;
    }
    const t=res.map[i];
    drawGraph(document.getElementById('pat'), PN, PE, PPOS, {cur:i, mapped:new Set(mappedP)});
    drawGraph(document.getElementById('tgt'), TN, TE, TPOS, {cur:t, mapped:new Set(mappedT)});
    setStatus(fmt('Mapping %fromCharCode% → %fromCharCode2% …', { fromCharCode: String.fromCharCode(80+i), fromCharCode2: String.fromCharCode(65+t) }),'');
    mappedP.add(i); mappedT.add(t); i++;
  }, 650);
}

document.getElementById('search').addEventListener('click',()=>animateResult(solve()));
document.getElementById('shuffle').addEventListener('click',()=>{ makeTarget(); renderStatic(); setStatus('Target reshuffled. Press Search.',''); });

makeTarget(); renderStatic();
Result
Console

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.

The Real Complexity

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.)

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/subgraph-isomorphism/Content licensed under CC BY-NC 4.0.