Proofs: Dulmage-Mendelsohn decomposition

The Dulmage-Mendelsohn decomposition runs in O((n + m) n^(1/2)) time full

This proof shows: time.worst.

Let $G = (X \cup Y, E)$ have $n$ vertices and $m$ edges, stored as adjacency lists on both sides. Each operation on an index, a mark or a queue costs $O(1)$ on the word RAM.

Line L1. Hopcroft-Karp finds a maximum matching in $O((n + m)\sqrt n)$ time and $\Theta(n + m)$ space.

Lines L2 to L6. In the search from the free left vertices, a left vertex is enqueued only when it is marked, and it is marked at most once, so at most $|X|$ vertices are dequeued. A dequeued vertex scans its adjacency list once, at $O(1)$ per edge, including the lookup of $\text{mate}[y]$ in line L5. So the search costs $O(n + m)$, and so does the mirror search of line L6.

Lines L7 and L8. $V_0$ is found by one pass over the marks, $O(n)$. $H$ has at most $|X|$ nodes and at most one arc per edge, built by one pass over the adjacency lists of $X_0$: $O(n + m)$.

Lines L9 to L11. Tarjan's algorithm runs in time linear in the size of $H$, $O(n + m)$, and reversing its output costs $O(n)$. Line L10 looks up one mate per left vertex, and writing the parts costs $O(n)$.

Total. $O((n + m)\sqrt n) + O(n + m) = O((n + m)\sqrt n)$ time. The space is the graph, the mate arrays, the marks, the queues, $H$ and Tarjan's stack, all $O(n + m)$, and the graph itself needs $\Omega(n + m)$, so it is $\Theta(n + m)$. $\blacksquare$

The Dulmage-Mendelsohn algorithm returns the canonical decomposition full

This proof shows: correctness, termination.

Let $G = (X \cup Y, E)$ be a finite bipartite graph, every edge joining $X$ to $Y$, and let $M$ be the maximum matching of line L1. Write $X_X = X \cap V_X$, $Y_X = Y \cap V_X$, $X_Y = X \cap V_Y$, $Y_Y = Y \cap V_Y$, $X_0 = X \cap V_0$ and $Y_0 = Y \cap V_0$. An edge is allowed if some maximum matching contains it.

Termination. Each search of lines L2 to L6 enqueues a vertex only when it marks it, and marks each vertex at most once, so it ends after at most $n$ dequeues. Tarjan's algorithm on the finite digraph $H$ ends. So the algorithm ends.

Claim 1 (what the search marks). A vertex is in $V_X$ if and only if it is reachable from a free vertex of $X$ by an $M$-alternating path, that is, a path $x_0\, y_1\, x_1\, y_2 \ldots$ with $x_0$ free, $x_{i-1} y_i \notin M$ and $y_i x_i \in M$. Every vertex of $Y_X$ is matched, and its mate is in $X_X$. Every neighbour of a vertex of $X_X$ is in $Y_X$.

Proof. Lines L3 to L5 follow exactly these steps: any edge from a left vertex (an edge of $M$ at $x_i$ leads back to $y_i$, already marked), and the matching edge from a right vertex. If a marked $y$ were free, the path to it would be augmenting, against the maximality of $M$ and Berge's lemma; so $y$ is matched and line L5 marks its mate. Line L4 marks every neighbour of a dequeued left vertex, and every marked left vertex is dequeued. $\square$

The mirror statement holds for $V_Y$, with the roles of $X$ and $Y$ swapped.

Claim 2 ($V_X$ and $V_Y$ are canonical). $X_X$ is the set of left vertices missed by some maximum matching, and $Y_X = N(X_X)$. Symmetrically $Y_Y$ is the set of right vertices missed by some maximum matching and $X_Y = N(Y_Y)$. Moreover $V_X \cap V_Y = \emptyset$.

Proof. If $x \in X_X$, the alternating path $P$ from a free $x_0$ to $x$ has even length and ends with an edge of $M$ at $x$, or is empty; $M \triangle E(P)$ is a maximum matching that misses $x$. Conversely let a maximum matching $N$ miss $x$. If $x$ is free in $M$ it is a root. Otherwise the component of $M \triangle N$ that contains $x$ is a path starting at $x$ with an edge of $M$. It alternates, and as $|M| = |N|$ it has even length, so it ends at a left vertex $z$ with an edge of $N$, and $z$ is free in $M$. Read from $z$, it is an $M$-alternating path from a free left vertex to $x$, so $x \in X_X$. By Claim 1, $Y_X \subseteq N(X_X)$ (each $y \in Y_X$ was marked from a left neighbour in $X_X$) and $N(X_X) \subseteq Y_X$. The mirror argument handles $V_Y$.

Suppose $v \in V_X \cap V_Y$. Let $P$ be an alternating path from a free left $x_0$ to $v$ and $Q$ one from a free right $y_0$ to $v$, and let $w$ be the first vertex of $P$ on $Q$. On $P$, left vertices are entered by edges of $M$ and right vertices by edges outside $M$; on $Q$ it is the reverse. So $P$ from $x_0$ to $w$ followed by $Q$ backwards from $w$ to $y_0$ alternates at $w$; its two parts share only $w$; and if $w = x_0$ or $w = y_0$ one part is empty. It is an $M$-augmenting path, which is impossible. $\square$

Claim 3 (two minimum covers). $K_1 = (X \setminus X_X) \cup Y_X$ and $K_2 = (Y \setminus Y_Y) \cup X_Y$ are minimum vertex covers. Hence no edge with both ends in $K_1$, or both ends in $K_2$, is allowed.

Proof. Every edge at $X_X$ ends in $Y_X$ by Claim 1, and every other edge has its left end in $X \setminus X_X$, so $K_1$ is a cover. By Claim 1, $M$ matches $Y_X$ into $X_X$, and each vertex of $X_X$ is free or the mate of a vertex of $Y_X$, so $|Y_X| = |X_X| - f$ with $f = |X| - |M|$ the number of free left vertices. Then $|K_1| = |X| - |X_X| + |Y_X| = |X| - f = |M|$, and a cover has at least $\nu(G)$ vertices, so $K_1$ is minimum. A maximum matching $N$ has $|N| = |K_1|$ edges, each with at least one end in $K_1$, and distinct edges of $N$ have distinct ends; so every edge of $N$ has exactly one end in $K_1$. The same holds for $K_2$. $\square$

Claim 3 rules out the edges from $X_0$ to $Y_X$ (both ends in $K_1$), from $X_Y$ to $Y_0$ (both in $K_2$) and from $X_Y$ to $Y_X$ (both in $K_1$). By Claim 1 and its mirror, no edge joins $X_X$ to $Y \setminus Y_X$ or $X \setminus X_Y$ to $Y_Y$. So every edge lies inside $V_X$, inside $V_Y$, inside $V_0$, or is one of the three kinds just excluded.

Claim 4 (edges inside the surplus parts are allowed). Every edge $xy$ with $x \in X_X$ and $y \in Y_X$ is allowed; symmetrically for $V_Y$.

Proof. If $xy \in M$ we are done. Otherwise let $P$ be an alternating path from a free $x_0$ to $x$, of even length. If $y$ is not on $P$, let $x' = \text{mate}[y]$; then $M' = (M \triangle E(P)) \setminus \{yx'\} \cup \{xy\}$ is a matching (it misses $x$ before the edge $xy$ is added, and $y x' \notin P$ since $y \notin P$), of size $|M|$, containing $xy$. If $y$ is on $P$, it is entered by an edge outside $M$ and left by its matching edge, so the part of $P$ from $y$ to $x$ together with the edge $xy$ is an even alternating cycle, and flipping it gives a maximum matching that contains $xy$. $\square$

Claim 5 (blocks). An edge $xy \notin M$ with $x \in X_0$ and $y \in Y_0$ is allowed if and only if $x$ and $\text{mate}[y]$ are in the same strongly connected component of $H$.

Proof. Every vertex of $V_0$ is matched, since free vertices are in $V_X$ or $V_Y$; so $\text{mate}[y] \in X_0$ by Claim 1 and its mirror, and $y$ is not in $V_X$ or $V_Y$. If $x$ and $x' = \text{mate}[y]$ are in one component, $H$ has a directed path from $x'$ back to $x$, and with the arc $x \to x'$ a directed cycle $x = x_1 \to x_2 \to \cdots \to x_k \to x_1$ with distinct nodes. Each arc $x_i \to x_{i+1}$ is an edge from $x_i$ to $\text{mate}[x_{i+1}]$, so $x_1\, \text{mate}[x_2]\, x_2\, \text{mate}[x_3] \cdots x_k\, \text{mate}[x_1]\, x_1$ is an even alternating cycle of $G$ through $xy$, and flipping it gives a maximum matching that contains $xy$.

Conversely let $N$ be a maximum matching with $xy \in N$. The component of $M \triangle N$ through $xy$ is an alternating path or cycle. A path would have an end missed by $M$ or by $N$, a vertex missed by some maximum matching, which by Claim 2 lies in $V_X$ or $V_Y$, and the whole path would be alternating from it, for $M$ or for $N$; by Claim 1 applied to that matching and Claim 2, all its vertices would lie in $V_X$ or in $V_Y$, but $x \in V_0$. So it is a cycle $C$. If $C$ met $V_X$, take a vertex $u \in X_X$ on $C$ (a vertex of $Y_X$ on $C$ has its $M$-mate in $X_X$ on $C$). Going round $C$ from $u$ along its edge of $N$, every right vertex reached is a neighbour of a vertex of $X_X$, so in $Y_X$, and its $M$-mate is in $X_X$; so all of $C$ lies in $V_X$, against $x \in V_0$. The same holds for $V_Y$. So $C \subseteq V_0$, and its $N$-edges $x_i\, \text{mate}[x_{i+1}]$ are arcs $x_i \to x_{i+1}$ of $H$ forming a directed cycle through $x \to \text{mate}[y]$. $\square$

Conclusion. By Claim 5, the edges of $M$ and the allowed edges inside $V_0$ join only vertices of one set $B_i = C_i \cup \text{mate}[C_i]$, and each $B_i$ is connected by them, since each arc inside $C_i$ is an allowed edge and $C_i$ is strongly connected. So the blocks are the connected components of the allowed edges inside $V_0$. Together with Claims 2 to 4, the allowed edges are exactly those inside $V_X$, inside $V_Y$ and inside one block, and the parts and the blocks depend only on $G$. Each block has $|C_i|$ left and $|C_i|$ right vertices. An edge $xy$ of $V_0$ between blocks gives the arc $x \to \text{mate}[y]$ between components; in the topological order of line L9 the component of $x$ comes first, so the edge goes from the left side of $B_i$ to the right side of $B_j$ with $i < j$. Line L9 returns that order, because Tarjan's algorithm emits the components in reverse topological order and the algorithm reverses it. Finally $M$ is maximum by line L1. $\blacksquare$