Kuhn's Algorithm, in depth: maximum bipartite matching with augmenting paths, a traced example, recursive and iterative Python, correctness, complexity and when to switch

The problem, precisely

A bipartite graph has two vertex sets, L and R, and edges only between them. A matching is a set of edges in which no vertex appears twice. A maximum matching has the largest possible number of edges. Do not confuse it with a maximal matching, one you cannot add an edge to without removing another: greedy assignment always gives a maximal matching and often not a maximum one.

A two-line example shows the gap. Worker A can do jobs x and y, worker B only x. Greedy gives A the first job it sees, x, and then B has nothing. The maximum gives A job y and B job x. Kuhn's algorithm is precisely a systematic way to discover moves like "give A a different job so B can have x", however long the chain of moves becomes.

Alternating and augmenting paths

Fix a matching M. An alternating path uses edges that alternate between not in M and in M. An augmenting path is an alternating path that starts at a free (unmatched) left vertex and ends at a free right vertex. Such a path has one more non-matching edge than matching edges, so if you flip every edge on it, matched becomes unmatched and the reverse, you get a valid matching with exactly one more edge. Vertices in the middle stay matched, just to different partners; the two endpoints become matched.

Berge's theorem (1957) says the converse too: a matching is maximum if and only if no augmenting path exists. The proof sketch is worth knowing. If a larger matching M' exists, overlay M and M'. Every vertex touches at most one edge of each, so the symmetric difference splits into alternating paths and even cycles. Cycles and even-length paths contain equal numbers of edges from each matching, so since M' is larger some path must have more M' edges than M edges, and that path is augmenting for M.

So the whole algorithm is: repeatedly find an augmenting path and flip it until none exists. The algorithm is named after Harold Kuhn, whose 1955 Hungarian-method paper is built on augmenting paths; the version here organises the search one left vertex at a time.

Kuhn's algorithm

Process left vertices in order. For each one, run a depth-first search for an augmenting path starting there. From left vertex u, try each neighbour v not yet visited in this search. If v is free, you have found the end of a path. If v is matched to some u2, the path must continue through u2, so recursively ask whether u2 can be moved to another right vertex. When the recursion succeeds, each level reassigns its right vertex on the way back up, which is exactly flipping the path.

def kuhn(n_left, n_right, adj):
    """adj[u] lists the right vertices adjacent to left vertex u. Returns (size, match_r)."""
    match_r = [-1] * n_right            # match_r[v] = left vertex matched to right vertex v

    def try_kuhn(u, seen):
        for v in adj[u]:
            if seen[v]:
                continue
            seen[v] = True
            # v is free, or the vertex holding v can be moved elsewhere
            if match_r[v] == -1 or try_kuhn(match_r[v], seen):
                match_r[v] = u
                return True
        return False

    size = 0
    for u in range(n_left):
        if try_kuhn(u, [False] * n_right):    # fresh visited set per root
            size += 1
    return size, match_r

The visited array marks right vertices, and it is reset for each new root. Without it the search can cycle between two left vertices that keep offering each other the same right vertex; with it each right vertex is entered at most once per search, which bounds the work.

Worked example

Workers and their allowed jobs: A to x or y, B to x, C to y or z, D to z.

1. Root A. x is free. Match A-x. Size 1.
2. Root B. Try x: visited now, held by A. Recurse into A: x is visited, try y, free. A takes y, returning true, and B takes x. The path was B-x-A-y. Size 2.
3. Root C. Try y: held by A. Recurse into A: try x, held by B; recurse into B: B's only job x is already visited, so false. A has no more options, false. Back at C, try z: free. Match C-z. Size 3.
4. Root D. Try z: held by C. Recurse into C: y is held by A, A tries x, B fails as before; C has nothing else. D stays free. Final size 3.

Three is optimal, since there are only three jobs. The run below shows the output, and also that the stack-based version with a greedy seed finds a different matching of the same size, leaving B rather than D unassigned. A maximum matching is usually not unique; if it matters who is left out, that is a weighting problem, discussed below.

>>> adj = [[0, 1], [0], [1, 2], [2]]      # A:{x,y} B:{x} C:{y,z} D:{z}
>>> kuhn(4, 3, adj)
(3, [1, 0, 2])                            # x-B, y-A, z-C ; D unmatched
>>> kuhn_greedy(4, 3, adj)
(3, [0, 2, 3])                            # x-A, y-C, z-D ; B unmatched
3000 random graphs agree with brute force
kuhn 1981 0.09s                           # 2,000 + 2,000 vertices, 5 random edges each
kuhn_greedy 1981 0.11s

Why one pass over the left side is enough

Kuhn's loop tries each left vertex once. If the search from u fails, u is never retried, even though the matching changes later. That is safe because of a lemma: if there is no augmenting path from u with respect to M, and M is changed by flipping an augmenting path from some other root, there is still no augmenting path from u afterwards.

The intuition: the failed search from u visited a set of left and right vertices, and every right vertex it reached was matched to a left vertex it also reached. That closed set is tight. A later augmentation that passes through it would need to leave it through some edge to a right vertex outside it, but the failed search would already have explored that edge. So the region stays closed and u stays stuck. The consequence is that after one pass no free left vertex has an augmenting path, and by Berge the matching is maximum.

Cost, and where the worst case comes from

Each search visits each right vertex at most once and scans each edge at most once, so one search is O(E) and the algorithm is O(V E), with V the number of left vertices. On sparse inputs it is much faster in practice, because most searches end within a few steps at a free vertex. The single timed run on the authoring machine matched 1,981 of 2,000 left vertices in about a tenth of a second in pure Python, with five random edges per vertex.

The bad cases are graphs where late roots need long augmenting paths through densely matched regions, so each search walks most of the graph. Structured inputs, such as grids, chains of overlapping preferences, and adversarially ordered adjacency lists, are where the O(V E) bound shows up.

Two practical tweaks are common. A greedy seed matches every left vertex with a free neighbour before any search starts, so later searches begin from a larger matching; in the one run here it was not faster, so measure before assuming. Processing left vertices with few neighbours first tends to help, since they have the fewest alternatives. The recursive version can exceed Python's recursion limit when augmenting paths are thousands of vertices long, which is why the stack-based version exists.

def kuhn_greedy(n_left, n_right, adj):
    match_r, match_l = [-1] * n_right, [-1] * n_left
    for u in range(n_left):                  # greedy seed: take any free edge first
        for v in adj[u]:
            if match_r[v] == -1:
                match_r[v], match_l[u] = u, v
                break

    def augment(root, seen):
        stack, path = [(root, 0)], []        # stack of (left vertex, next edge index)
        while stack:
            u, i = stack[-1]
            if i == len(adj[u]):             # u exhausted: backtrack
                stack.pop()
                if path:
                    path.pop()
                continue
            stack[-1] = (u, i + 1)
            v = adj[u][i]
            if seen[v]:
                continue
            seen[v] = True
            path.append(v)
            if match_r[v] == -1:             # free right vertex: flip the whole path
                for (lu, _), rv in zip(stack, path):
                    match_r[rv], match_l[lu] = lu, rv
                return True
            stack.append((match_r[v], 0))    # descend into v's current partner
        return False

    size = sum(1 for x in match_l if x != -1)
    for u in range(n_left):
        if match_l[u] == -1 and augment(u, [False] * n_right):
            size += 1
    return size, match_r

What the final matching tells you

Beyond the size, the finished state certifies itself. Run one more alternating search from every free left vertex, following non-matching edges from left to right and matching edges from right to left, and mark everything reached. Konig's theorem says that the unmarked left vertices together with the marked right vertices form a minimum vertex cover, a smallest set of vertices touching every edge, and its size equals the matching size. That set is a proof of optimality you can check independently, and it is also an answer to its own family of problems.

Hall's theorem gives the dual for perfect matchings: every left vertex can be matched if and only if every subset S of left vertices has at least as many distinct neighbours as members. When Kuhn's algorithm leaves a vertex unmatched, the vertices its last failed search reached form exactly such a violating subset, which makes a good explanation for a user who asks why they were not assigned.

Kuhn versus the alternatives

Kuhn is also naturally incremental: when a new left vertex arrives, one O(E) search either matches it or proves it cannot be matched.

Failure modes

• Visited marks not reset per root. Searches then skip right vertices that a previous search touched, and the result is too small. Reuse across roots only with an algorithm designed for it, and fuzz it.
• Marking left vertices instead of right. Correct only if done consistently; mixing the two causes loops or missed paths.
• Recursion depth. Long augmenting paths crash recursive Python and can overflow the stack in C++ and Java on large inputs. Use the iterative form.
• Non-bipartite input. Odd cycles break the alternating-path argument and the algorithm can return a non-maximum answer. Check bipartiteness first.
• Duplicate edges or mixed indexing. Mixing left and right indices in one array is the most common bug. Keep the two sides in separate index spaces.
• Expecting fairness. The algorithm maximises count, not who is served. Who is left out depends on processing order, as the two outputs above show. If that matters, use costs.

Where to go next on this site

Matching is a special case of flow; see max flow with Ford-Fulkerson and Edmonds-Karp for the general machinery. For the DFS underlying every search, see BFS and DFS in depth, and for another classic DFS-based algorithm with an iterative rewrite, bridges and articulation points.

What to do next

1. Implement kuhn from memory, then test it against brute force on small random graphs as done here.
2. Add the stack-based version and run it on a 100,000-vertex chain to see the recursive one fail.
3. Extract the minimum vertex cover from a finished matching and check that its size equals the matching size.
4. Time Kuhn against a max-flow formulation on your real data before reaching for Hopcroft-Karp.
5. If unmatched vertices need explaining, report the Hall violator from the last failed search.
6. If pairs have costs, move to the Hungarian algorithm or min-cost flow.