• Overview and Definitions
• Maximum Bipartite Matching: Hopcroft–Karp
• Assignment Problem: Hungarian Algorithm
• Variants and Notes
• Exercises

• Bipartite matching: graph G = (L ∪ R, E). A matching is a set of disjoint edges. Goal: max-size matching.
• Assignment problem: complete weighted bipartite graph; goal: min-cost perfect matching.
• Kőnig–Egérváry: In bipartite graphs, size of max matching = size of min vertex cover.

// Hopcroft–Karp for bipartite matching
// L side: 0..(nL-1), R side: 0..(nR-1); adjL[u] lists neighbors v in R
function hopcroftKarp(nL, nR, adjL) {
  const NIL = -1;
  const pairU = Array(nL).fill(NIL);
  const pairV = Array(nR).fill(NIL);
  const dist = Array(nL).fill(0);
  function bfs() {
    const q = [];
    for (let u = 0; u < nL; u++) {
      if (pairU[u] === NIL) { dist[u] = 0; q.push(u); }
      else dist[u] = Infinity;
    }
    let reachableFree = false;
    for (let qi = 0; qi < q.length; qi++) {
      const u = q[qi];
      for (const v of adjL[u]) {
        const u2 = pairV[v];
        if (u2 !== NIL && dist[u2] === Infinity) { dist[u2] = dist[u] + 1; q.push(u2); }
        if (u2 === NIL) reachableFree = true;
      }
    }
    return reachableFree;
  }
  function dfs(u) {
    for (const v of adjL[u]) {
      const u2 = pairV[v];
      if (u2 === NIL || (dist[u2] === dist[u] + 1 && dfs(u2))) {
        pairU[u] = v; pairV[v] = u; return true;
      }
    }
    dist[u] = Infinity; // mark as dead-end in this layer graph
    return false;
  }
  let matching = 0;
  while (bfs()) {
    for (let u = 0; u < nL; u++) if (pairU[u] === NIL && dfs(u)) matching++;
  }
  return { matching, pairU, pairV };
}

• Idea: Layered BFS builds the level graph; DFS finds a maximal set of vertex-disjoint shortest augmenting paths per phase.
• Use cases: job assignment (unweighted), scheduling, pairing tasks, team formation.

// Hungarian algorithm for minimum-cost perfect matching in an n x n cost matrix
function hungarian(cost) {
  const n = cost.length;
  const u = Array(n+1).fill(0), v = Array(n+1).fill(0);
  const p = Array(n+1).fill(0), way = Array(n+1).fill(0);
  for (let i = 1; i <= n; i++) {
    p[0] = i;
    let j0 = 0;
    const minv = Array(n+1).fill(Infinity);
    const used = Array(n+1).fill(false);
    do {
      used[j0] = true;
      const i0 = p[j0];
      let delta = Infinity, j1 = 0;
      for (let j = 1; j <= n; j++) if (!used[j]) {
        const cur = cost[i0-1][j-1] - u[i0] - v[j];
        if (cur < minv[j]) { minv[j] = cur; way[j] = j0; }
        if (minv[j] < delta) { delta = minv[j]; j1 = j; }
      }
      for (let j = 0; j <= n; j++) {
        if (used[j]) { u[p[j]] += delta; v[j] -= delta; }
        else minv[j] -= delta;
      }
      j0 = j1;
    } while (p[j0] !== 0);
    do {
      const j1 = way[j0];
      p[j0] = p[j1];
      j0 = j1;
    } while (j0 !== 0);
  }
  const matchR = Array(n).fill(-1);
  for (let j = 1; j <= n; j++) if (p[j] > 0) matchR[j-1] = p[j] - 1;
  // matchR[j] = i means row i assigned to column j
  let minCost = 0;
  for (let j = 0; j < n; j++) if (matchR[j] !== -1) minCost += cost[matchR[j]][j];
  return { matchR, minCost };
}

• Notes: Works on square matrices; pad with dummy rows/cols for rectangular cases.
• Outputs: minimal total cost and assignment mapping.

• Min-cost max-flow: generalizes weighted matching; useful when costs are not bipartite-only.
• General graph matching: Edmonds' Blossom algorithm for non-bipartite graphs.
• Vertex cover extraction: From HK result via alternating BFS starting from unmatched L nodes.

1. Implement Hopcroft–Karp and validate on random bipartite graphs against naive DFS augmenting paths.
2. Solve a sample assignment matrix with Hungarian; verify min cost.
3. From a maximum matching, derive a minimum vertex cover in a bipartite graph.