Chapter 12. Bipartite Matching

Augmenting paths, the König / Dilworth duality, and chain-cover / antichain extraction from a matching.

This page: LLP forms. View classical forms »

Setting

A matching in an undirected graph $(V, E)$ is a subset $M \subseteq E$ no two of whose edges share an endpoint. The maximum cardinality matching problem asks for the largest such subset. In a bipartite graph $(L, R, E)$ the problem is solvable in polynomial time; in general graphs it requires the more delicate Edmonds blossom algorithm, which we do not cover here.

A vertex is exposed (or unmatched) under $M$ if no edge of $M$ touches it. An augmenting path is a path between two exposed vertices that alternates unmatched and matched edges, starting and ending with unmatched edges. Toggling matched / unmatched along an augmenting path strictly increases the matching size, by exactly one. This is the engine of every classical bipartite-matching algorithm.

The Sequential Augmenting-Path Algorithm

Process the left vertices $v_1, v_2, \ldots$ in any fixed order. At step $i$, search for an augmenting path that starts at $v_i$ (a DFS or BFS suffices since $v_i$ is exposed when first visited). If one exists, toggle the path; otherwise leave $M$ unchanged. The result is a maximum matching of size $\sum_i G[i]$, where $G[i] \in \{0, 1\}$ records whether $v_i$ ended up matched. Sequential running time: $O(|V| \cdot |E|)$. Hopcroft-Karp tightens this to $O(\sqrt{|V|} \cdot |E|)$.

König's theorem and the vertex cover

A vertex cover is a set of vertices touching every edge. König's theorem states that in any bipartite graph, $$ |\text{maximum matching}| \;=\; |\text{minimum vertex cover}|. $$ The proof is constructive: from a maximum matching $M$, place each $L$-endpoint of $M$ into the cover, then "swap" along uncovered $L$-$R$ edges (always available because the matching is maximum). The resulting set has size $|M|$ and covers every edge.

Dilworth's theorem and the antichain

Given a finite poset $(P, \leq)$, a chain is a totally-ordered subset and an antichain is a pairwise-incomparable subset. Dilworth: $$ |\text{minimum chain cover}| \;=\; |\text{maximum antichain}|. $$ The proof uses the strict split reduction: build a bipartite graph $(L, R, E)$ with $L = \{x^- : x \in P\}$, $R = \{x^+ : x \in P\}$, and an edge $(x^-, y^+)$ whenever $x < y$ in $P$. A maximum matching $M$ in the strict split yields a minimum chain cover of size $n - |M|$ (Fulkerson 1956): every matched edge merges two chains into one. The matching number, the chain-cover number, the antichain number, and the bipartite vertex-cover number are linked by König / Dilworth into a single equality.

The LLP perspective

With a minimum chain cover in hand, an antichain of the same size emerges as the fixed-point of an LLP algorithm: each chain $C_j$ contributes a single representative, indexed by $G[j]$ (initially $1$). When some $C_j[G[j]]$ is dominated by some $C_k[G[k]]$, advance $G[j]$ to the next chain element. At termination, no representative dominates any other — exactly an antichain of size $m$, the chain count.

• LLP-Antichain. $G[j] \in \mathbb{N}$; forbidden when $G[j] < |C_j|$ and some $k \neq j$ has $C_j[G[j]] \leq C_k[G[k]]$. Advance: $G[j] := G[j] + 1$.

The LL DSL versions ship in book/lang/progs-bipartite/.

LLP-Antichain

LLP form on the per-chain index vector. Forbidden whenever the current representative on chain $j$ is dominated by some other representative; advancing moves $G[j]$ one step up the chain. The fixed-point set $\{C_j[G[j]] : j = 1, \ldots, m\}$ is a maximum antichain.

Time complexity: $O(n^2)$, where $n$ is the number of poset elements.

int[] LLPAntichain(int[][] chains, int[] len, boolean[][] leq) {
  int[] G = 0;
  forbidden (j) :
    G[j] < len[j]
      && (exists k in [0..n-1] :
            k != j && leq[chains[j][G[j]]][chains[k][G[k]]])
  =>
    advance :
      G[j] = G[j] + 1;
  return G;
}

LLP predicates for this chapter

Each LLP program in this chapter defines a state vector $G$ and a forbidden predicate; the algorithm runs until no $j$ is forbidden. The table below lists, for each algorithm, what $G[i]$ represents and the negation of the forbidden clause from the matching .llp source.