Hopcroft-Karp

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

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_label}}: 0</span>
    <span id="match-label">{{matched_label}}: 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">{{btn_next_phase}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
  <div class="legend">
    <span class="leg-unmatched">── {{legend_unmatched}}</span>
    <span class="leg-matched">── {{legend_matched}}</span>
    <span class="leg-aug">── {{legend_aug}}</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; }

// Code not found

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 $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)$ 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)$ total — another $O(E\sqrt{V})$.
• Total: $O(E\sqrt{V})$. For sparse graphs (E ≈ V) this is $O(V^{3/2})$; for dense (E ≈ $V^{2}$) it is $O(V^{5/2})$, matching the title of the original Hopcroft–Karp paper.

Compare this to simpler approaches:

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.

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(E\sqrt{V})$ bound is the difference between finishing in seconds and waiting hours.

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)$ was too slow for large graphs. The 1973 paper by Hopcroft and Karp, together with the parallel work by Karzanov, pushed it to $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.