How slow can Algorithm 7.5.1H be?

1Algorithm H, one step at a time

Algorithm H keeps a matching between girls and boys. Matched pairs are couples, drawn as double lines; unmatched vertices are free. An augmenting path runs from a free girl to a free boy, alternating between edges outside and inside the matching. Swapping its two kinds of edges adds a couple. A path with $2L-1$ edges has level $L$.

Step H1 builds a greedy matching. Then each round does two things:

• a breadth-first search (steps H2–H10) builds a dag of all shortest augmenting paths (SAPs), level by level;
• a depth-first search (H11–H17) takes SAPs out of the dag one by one, augmenting along each and deleting its vertices, until none is left.

What the algorithm does depends on the input in only two ways: the numbering of the girls, which fixes the order in which H1 scans them, and the order of each girl’s list of boys. The reverse lists $\mathtt{BLINK}[b]$ that the search follows are built by the algorithm, and new entries go to the front. Watch that happen below. In round 2 of this nine-pair example, the first round with a dag, the search finds just one SAP, although three disjoint ones exist: the one it finds meets all three.

2Tchoukaillon graphs

Suppose the graph has a perfect matching ($s=M=N$) and the current matching leaves $f$ girls free. If the round’s dag has level $L$ and there are $f$ disjoint SAPs, then any maximal set of disjoint SAPs has at least $\lceil f/(L+1)\rceil$ members, because one SAP can meet at most $L+1$ of them. Exercise 15(c) asks for a graph that starts with the largest possible number of free girls, $\lfloor s/2\rfloor$, and removes only that minimum at levels $L=2,3,\ldots$. The numbers then follow the Tchoukaillon schedule $$f_2=\lfloor s/2\rfloor,\qquad a_L=\lceil f_L/(L+1)\rceil,\qquad f_{L+1}=f_L-a_L.$$

Knuth noticed that this is the arithmetic of a solitaire game, Tchoukaillon (exercise 11), a one-player relative of mancala. Pit $k$ may be emptied only when it holds exactly $k$ stones, which are sown one each into pits $k-1,\ldots,1$ and the store. For each number of stones there is exactly one winning position. Play it below; the number of moves made from pit $L$ is $a_L$.

3How many rounds can there be?

Before a round at level $L$ with $f$ free girls, a maximum matching supplies $f$ disjoint augmenting paths, each using at least $L$ of its $s$ edges. So $fL\le s$: every round of every run is a point on or below the hyperbola $fL=s$. With $n$ rounds, the $i$th round after H1 has level at least $i+1$ and at least $n-i$ free girls, and maximizing $(i+1)(n-i)$ gives the whole answer:

The Tchoukaillon schedule starts at the top of the hyperbola and must shed free girls fast. A worst case starts lower and slides down along it, one free girl per round.

4Staircase graphs

The bound is attained by the staircase graphs $\Gamma_n$. They are planar, have maximum degree three, and come with an input order under which every step of Algorithm H can be predicted. The cells form $n-1$ left-justified rows, plus one extra corner cell at the bottom. Each cell holds a girl and a boy; a boy is joined to his own girl, to the girl of the next cell in his row, and to the girl of the cell below, except that the edge into the corner is left out (it would only complicate the proofs; the explorer below lets you add it).

When $f$ girls are free, the basic paths are hooks, one starting at the first cell of each of rows $1,\ldots,f$. Hook $x$ runs east along row $x$ to column $c=f+1-x$ and then turns south down column $c$; a row with fewer than $c$ cells is a hook by itself, and the last hook ends at the corner.

The trick is to keep some hooks longer than the shortest level. They count as free girls but are not SAPs, so at most $L+1$ disjoint SAPs exist. Because new entries go to the front of the reverse lists, the first search takes the first arc at every boy and descends a staircase through every shortest hook. That one SAP blocks all the others: if $m$ hooks have the shortest level, the dag contains $2^m-1$ SAPs, and every one of them meets it.

5The literal definition

Suppose a round has $f$ disjoint SAPs of level $L$, and the next round has the literal property: every augmenting path has level $L+1$. Then the first of the two rounds removes at least half of the free girls. The heart of the proof is a splice. After augmenting along a selected path $S$, its new couples $e_1,\ldots,e_L$ can only be used in position: a new augmenting path that uses $e_i$ uses it as its $i$th couple. If two new disjoint paths crossed $S$ at $e_i$ and $e_j$, then following one, walking back along $S$, and finishing along the other would give an augmenting path with $4(j-i)$ more edges, although every augmenting path of the next round has level $L+1$.

6The open question

Can the Tchoukaillon schedule be realized for every $s$, with no condition on the paths? Computer search has found inputs for every $s\le41$, and all of them even keep $f$ disjoint SAPs in every round. Any family that works for unboundedly large $s$ needs at least $s/12-O(1)$ independent cycles (cycle rank).

The input order is a genuine obstacle. The six-pair graph below admits a run in which each of the rounds at levels 2, 3, 4 removes a maximal set consisting of a single SAP, which is exactly the schedule for $s=6$. But Algorithm H chooses its SAPs by its own rules: its queue order, the insertion at the front in step H6, and the replacement rule of step H16. Try to find a numbering and list orders that make it follow the schedule, or let the computer try all 103,680 of them.

7Try your own graph

Write one line per girl, $1,2,\ldots,M$, listing her boys in the order of her list. Algorithm H runs on exactly that input, so changing the order of a list, or swapping two girls’ numbers, can change what it does.