Introduction

Imagine a hundred job applicants, each qualified for a handful of openings. You want to hire as many people as possible, each to a job they can do, and no two assigned to the same role. This is bipartite matching โ€” one of the most fundamental problems in combinatorial optimization.

The naive approach is to keep finding augmenting paths: routes that start at an unmatched applicant, alternate between unmatched and matched edges, and end at an unmatched job. Flip the edges along such a path and the matching grows by one. Repeat until none remain.

But doing that one path at a time is slow โ€” O(VE)O(VE) in the worst case. In 1973, John Hopcroft and Richard Karp published an elegant fix: find all shortest augmenting paths in a single BFS phase, augment along all of them simultaneously, and repeat. The key observation โ€” proved in their original paper โ€” is that after at most โˆšV such phases, the matching is maximum. The total cost is therefore O(EV)O(E\sqrt{V}), a result that was proved optimal for dense graphs and remains the standard algorithm decades later.

This article is about what that square root really means: why augmenting in phases is so much better, and why finding a maximum matching at all is in P โ€” firmly on the tractable side of the P vs NP dividing line.

Try It: Match Applicants to Jobs

The demo below shows a small bipartite graph: applicants on the left, jobs on the right. Edges mean "this applicant is qualified for that job." The current matching is shown in blue.

<div class="layout">
  <div class="info-bar">
    <span id="phase-label">Phase: 0</span>
    <span id="match-label">Matched: 0 / 0</span>
    <span id="status-label"></span>
  </div>
  <svg id="graph" width="100%" viewBox="0 0 420 320"></svg>
  <div class="btns">
    <button id="btn-phase" type="button">Next Phase</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
  <div class="legend">
    <span class="leg-unmatched">โ”€โ”€ unmatched edge</span>
    <span class="leg-matched">โ”€โ”€ matched edge</span>
    <span class="leg-aug">โ”€โ”€ augmenting path</span>
  </div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.layout { display: flex; flex-direction: column; gap: .5rem; padding: .5rem; }
.info-bar { display: flex; gap: 1.2rem; font-size: .9rem; font-weight: 600; flex-wrap: wrap; }
#phase-label { color: #1d3557; }
#match-label { color: #0a7d33; }
#status-label { color: #e76f00; }
svg { border: 1px solid #dde3ea; border-radius: 8px; background: #f8fafc; display: block; max-height: 300px; }
.btns { display: flex; gap: .5rem; }
button { font: 600 14px system-ui; padding: .4rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.legend { display: flex; gap: 1rem; flex-wrap: wrap; font-size: .78rem; color: #555; }
.leg-unmatched::before { content: ""; display: inline-block; width: 22px; height: 2px;
  background: #adb5c3; vertical-align: middle; margin-right: 4px; }
.leg-matched::before { content: ""; display: inline-block; width: 22px; height: 3px;
  background: #1d6edc; vertical-align: middle; margin-right: 4px; }
.leg-aug::before { content: ""; display: inline-block; width: 22px; height: 2px;
  background: #e76f00; border-top: 2px dashed #e76f00; vertical-align: middle; margin-right: 4px; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Hopcroft-Karp algorithm visualised step by step.
// Left nodes = applicants (A0-A4), right nodes = jobs (J0-J4).
// Each "Next Phase" runs one full BFS+DFS phase of Hopcroft-Karp,
// highlighting the augmenting paths found before flipping them.

const SVG_NS = 'http://www.w3.org/2000/svg';
const W = 420, H = 320;
const LX = 80, RX = 340; // x positions for left / right columns

// โ”€โ”€ graph state โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
let nL, nR, adj, matchL, matchR, phase, done, augPaths;

function randomGraph() {
  nL = 5; nR = 5;
  adj = Array.from({length: nL}, () => []);
  // Ensure graph is connected enough to be interesting (at least 2 edges per left node)
  const edges = new Set();
  // Guarantee a perfect matching seed so the demo is always solvable
  const perm = [0,1,2,3,4].sort(() => Math.random()-.5);
  for (let i = 0; i < nL; i++) {
    edges.add(i + ',' + perm[i]);
    const extra = Math.floor(Math.random() * 2) + 1;
    for (let k = 0; k < extra; k++) {
      const j = Math.floor(Math.random() * nR);
      edges.add(i + ',' + j);
    }
  }
  edges.forEach(e => {
    const [l, r] = e.split(',').map(Number);
    adj[l].push(r);
  });
  matchL = new Array(nL).fill(-1);
  matchR = new Array(nR).fill(-1);
  phase = 0;
  done = false;
  augPaths = [];
}

// โ”€โ”€ Hopcroft-Karp internals โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
const INF = 1e9;
let distL;

function bfs() {
  distL = new Array(nL).fill(INF);
  const queue = [];
  for (let u = 0; u < nL; u++) {
    if (matchL[u] === -1) { distL[u] = 0; queue.push(u); }
  }
  let found = false;
  let qi = 0;
  while (qi < queue.length) {
    const u = queue[qi++];
    for (const v of adj[u]) {
      const w = matchR[v]; // the left node matched to v (or -1)
      if (w === -1) { found = true; }
      else if (distL[w] === INF) { distL[w] = distL[u] + 1; queue.push(w); }
    }
  }
  return found;
}

// DFS that also records the path taken
function dfs(u, path) {
  for (const v of adj[u]) {
    const w = matchR[v];
    if (w === -1 || (distL[w] === distL[u] + 1 && dfs(w, path))) {
      path.push([u, v]);
      matchL[u] = v;
      matchR[v] = u;
      return true;
    }
  }
  distL[u] = INF;
  return false;
}

function runPhase() {
  // Returns array of augmenting paths found this phase.
  if (!bfs()) return null; // no augmenting path => done
  const paths = [];
  // We need to capture paths before flipping, so we use a two-pass approach:
  // first collect paths by running dfs on a copy, then actually flip.
  // Simpler: record edges inside dfs.
  const savedMatchL = matchL.slice();
  const savedMatchR = matchR.slice();

  for (let u = 0; u < nL; u++) {
    if (matchL[u] === -1) {
      const path = [];
      if (dfs(u, path)) {
        // path is filled in reverse by the recursion; edges are (leftNode, rightNode) pairs
        paths.push(path.slice());
      }
    }
  }
  return paths; // matchL/matchR already updated by dfs
}

// โ”€โ”€ layout helpers โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function ly(i) { return 40 + i * ((H - 80) / (nL - 1)); }
function ry(j) { return 40 + j * ((H - 80) / (nR - 1)); }

// โ”€โ”€ SVG rendering โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function clearSVG() {
  const svg = document.getElementById('graph');
  while (svg.firstChild) svg.removeChild(svg.firstChild);
}

function makeLine(x1, y1, x2, y2, cls, dashed) {
  const el = document.createElementNS(SVG_NS, 'line');
  el.setAttribute('x1', x1); el.setAttribute('y1', y1);
  el.setAttribute('x2', x2); el.setAttribute('y2', y2);
  el.setAttribute('class', cls);
  if (dashed) el.setAttribute('stroke-dasharray', '6 4');
  return el;
}

function makeCircle(cx, cy, r, cls) {
  const el = document.createElementNS(SVG_NS, 'circle');
  el.setAttribute('cx', cx); el.setAttribute('cy', cy); el.setAttribute('r', r);
  el.setAttribute('class', cls); return el;
}

function makeText(x, y, txt, cls) {
  const el = document.createElementNS(SVG_NS, 'text');
  el.setAttribute('x', x); el.setAttribute('y', y);
  el.setAttribute('class', cls); el.textContent = txt; return el;
}

// Build a set of (l,r) pairs that are on an augmenting path this phase
function augEdgeSet(paths) {
  const s = new Set();
  paths.forEach(path => path.forEach(([l, r]) => s.add(l + ',' + r)));
  return s;
}

function render(highlightPaths) {
  clearSVG();
  const svg = document.getElementById('graph');

  // Add SVG styles
  const style = document.createElementNS(SVG_NS, 'style');
  style.textContent = `
    .edge-unmatched { stroke: #adb5c3; stroke-width: 1.5; }
    .edge-matched   { stroke: #1d6edc; stroke-width: 2.5; }
    .edge-aug       { stroke: #e76f00; stroke-width: 2; }
    .node-left      { fill: #dce8f7; stroke: #1d3557; stroke-width: 1.5; }
    .node-right     { fill: #e8f5e9; stroke: #2e7d32; stroke-width: 1.5; }
    .node-matched-l { fill: #1d6edc; stroke: #1d3557; stroke-width: 1.5; }
    .node-matched-r { fill: #0a7d33; stroke: #2e7d32; stroke-width: 1.5; }
    .node-aug-l     { fill: #e76f00; stroke: #b34700; stroke-width: 1.5; }
    .node-aug-r     { fill: #e76f00; stroke: #b34700; stroke-width: 1.5; }
    .lbl-left       { font: 600 12px system-ui; fill: #1d3557; text-anchor: middle; dominant-baseline: central; }
    .lbl-right      { font: 600 12px system-ui; fill: #2e7d32; text-anchor: middle; dominant-baseline: central; }
    .lbl-left-matched  { font: 600 12px system-ui; fill: #fff; text-anchor: middle; dominant-baseline: central; }
    .lbl-right-matched { font: 600 12px system-ui; fill: #fff; text-anchor: middle; dominant-baseline: central; }
  `;
  svg.appendChild(style);

  const augSet = highlightPaths ? augEdgeSet(highlightPaths) : new Set();
  const augLeftSet = new Set();
  const augRightSet = new Set();
  if (highlightPaths) {
    highlightPaths.forEach(path => path.forEach(([l, r]) => { augLeftSet.add(l); augRightSet.add(r); }));
  }

  // Draw edges
  for (let u = 0; u < nL; u++) {
    for (const v of adj[u]) {
      const isMatched = matchL[u] === v;
      const isAug = augSet.has(u + ',' + v);
      let cls = isAug ? 'edge-aug' : (isMatched ? 'edge-matched' : 'edge-unmatched');
      svg.appendChild(makeLine(LX, ly(u), RX, ry(v), cls, isAug && !isMatched));
    }
  }

  // Draw left nodes
  for (let u = 0; u < nL; u++) {
    const y = ly(u);
    const isAug = augLeftSet.has(u);
    const isMatched = matchL[u] !== -1 && !isAug;
    const nodeCls = isAug ? 'node-aug-l' : (isMatched ? 'node-matched-l' : 'node-left');
    const lblCls = (isMatched || isAug) ? 'lbl-left-matched' : 'lbl-left';
    svg.appendChild(makeCircle(LX, y, 18, nodeCls));
    svg.appendChild(makeText(LX, y, 'A' + u, lblCls));
  }

  // Draw right nodes
  for (let j = 0; j < nR; j++) {
    const y = ry(j);
    const isAug = augRightSet.has(j);
    const isMatched = matchR[j] !== -1 && !isAug;
    const nodeCls = isAug ? 'node-aug-r' : (isMatched ? 'node-matched-r' : 'node-right');
    const lblCls = (isMatched || isAug) ? 'lbl-right-matched' : 'lbl-right';
    svg.appendChild(makeCircle(RX, y, 18, nodeCls));
    svg.appendChild(makeText(RX, y, 'J' + j, lblCls));
  }

  // Column labels
  const lblY = H - 8;
  const lbl1 = makeText(LX, lblY, 'Applicants', 'lbl-left');
  lbl1.setAttribute('font-size', '10'); svg.appendChild(lbl1);
  const lbl2 = makeText(RX, lblY, 'Jobs', 'lbl-right');
  lbl2.setAttribute('font-size', '10'); svg.appendChild(lbl2);
}

function updateInfo(statusText) {
  const matched = matchL.filter(v => v !== -1).length;
  document.getElementById('phase-label').textContent = fmt('Phase: %phase%', { phase: phase });
  document.getElementById('match-label').textContent = fmt('Matched: %matched% / %nL%', { matched: matched, nL: nL });
  document.getElementById('status-label').textContent = statusText || '';
}

// โ”€โ”€ button handlers โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function onPhase() {
  if (done) return;
  const paths = runPhase();
  phase++;
  if (!paths || paths.length === 0) {
    done = true;
    render(null);
    updateInfo('Maximum matching reached!');
    document.getElementById('btn-phase').disabled = true;
    return;
  }
  // Show augmenting paths briefly, then settle
  render(paths);
  updateInfo(fmt('Phase %phase%: %length% %v% found', { phase: phase, length: paths.length, v: paths.length > 1 ? 'augmenting paths' : 'augmenting path' }));
}

function onReset() {
  randomGraph();
  render(null);
  updateInfo('');
  document.getElementById('btn-phase').disabled = false;
}

document.getElementById('btn-phase').addEventListener('click', onPhase);
document.getElementById('btn-reset').addEventListener('click', onReset);

onReset();

// Expose for node verification
if (typeof module !== 'undefined') {
  module.exports = { randomGraph, runPhase, matchL: () => matchL, matchR: () => matchR };
}
Result
Console

Press Next Phase to run one BFS phase: the algorithm finds all shortest augmenting paths and flips them simultaneously. Notice how the matching can grow by two or three edges in a single phase. Press Reset to start over with a fresh random graph.

The Real Complexity

The O(EV)O(E\sqrt{V}) bound is not obvious. Here is the key argument:

  • Each BFS phase builds a layered graph from unmatched left nodes using BFS. It then finds a maximal set of vertex-disjoint shortest augmenting paths using DFS, and flips all of them. This is O(E)O(E) per phase.
  • After โˆšV phases, the shortest remaining augmenting path (if any) has length at least 2โˆšV + 1. A classical result on augmenting path lengths then limits the number of remaining augmenting paths to at most โˆšV. Each can be flipped individually in O(E)O(E) total โ€” another O(EV)O(E\sqrt{V}).
  • Total: O(EV)O(E\sqrt{V}). For sparse graphs (E โ‰ˆ V) this is O(V3/2)O(V^{3/2}); for dense (E โ‰ˆ V2V^{2}) it is O(V5/2)O(V^{5/2}), matching the title of the original Hopcroftโ€“Karp paper.

Compare this to simpler approaches:

Algorithm Time Idea
Augment one path at a time O(VE)O(VE) Find one augmenting path per round
Hopcroft-Karp O(EV)O(E\sqrt{V}) Augment all shortest paths per round
General matching (Micali-Vazirani) O(EV)O(E\sqrt{V}) General graphs (non-bipartite)

Crucially, maximum bipartite matching is in P โ€” it is solved efficiently. This places it far from the NP-complete land of graph coloring or clique. The matching problem was always tractable; Hopcroft-Karp just made it fast.

Where It Matters

Maximum bipartite matching โ€” and by extension Hopcroft-Karp โ€” appears wherever you need to assign one set of items to another with no conflicts:

  • Job scheduling and assignment: assign workers to tasks, machines to jobs, or students to advisors. Any hiring pipeline where qualifications form a graph uses matching at its core.
  • Network routing: finding edge-disjoint paths and proving max-flow min-cut results both reduce to matching. The two are deeply linked through the max-flow framework.
  • Compiler register allocation: variables must be mapped to hardware registers without conflict. The interference graph is bipartite in many practical cases; Hopcroft-Karp handles it efficiently.
  • Medical residency matching: the famous NRMP residency match uses variants of stable matching, itself rooted in bipartite graph theory.
  • Image segmentation and computer vision: pixel labeling problems frequently reduce to bipartite matching to find globally consistent assignments.

Whenever a bipartite assignment problem appears at scale โ€” millions of workers, millions of tasks โ€” the O(EV)O(E\sqrt{V}) bound is the difference between finishing in seconds and waiting hours.

Conclusion

Hopcroft-Karp shows how a single structural insight โ€” augment along all shortest paths simultaneously โ€” can shave a square root off a classic algorithm's runtime. Maximum bipartite matching was already in P, but O(VE)O(VE) was too slow for large graphs. The 1973 paper by Hopcroft and Karp, together with the parallel work by Karzanov, pushed it to O(EV)O(E\sqrt{V}) and kept it there for decades.

The lesson generalizes: the best algorithms do not just solve problems, they exploit the geometry of the problem's solution space. In matching, that geometry is the layered BFS structure that groups paths by length โ€” and augmenting layer by layer squeezes out a square-root factor that naive one-at-a-time augmentation leaves on the table.

To see matching in a broader context, explore max-flow โ€” bipartite matching reduces to it โ€” or P vs NP for why tractability itself is not obvious.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

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