skip to content

In a partial pairing of work items to eligible engineers, what is an augmenting path and what does its existence prove?

level: seniorimportance: should knowfreq 42%

answer

  1. a path, not a cycle
  2. both ends currently unpaired
  3. edges alternate outside, inside, outside
  4. flip the whole path at once
  5. none exists means nothing better exists

basics

~20 s

An augmenting path runs between two currently unpaired vertices and alternates unpaired and paired edges. One exists exactly when the pairing is not maximum, and flipping every edge along it enlarges the pairing by exactly one.

solid answer

~40 s

Take the current pairing `M` on the eligibility graph. An **alternating path** is a path whose edges alternate between edges outside `M` and edges inside `M`. It is **augmenting** when both of its endpoints are vertices that `M` leaves unpaired. Such a path must start and end with an unpaired edge, so it has one more unpaired edge than paired ones. Flip it - every unpaired edge on the path joins `M`, every paired edge leaves - and the pairing grows by exactly one, while every interior vertex stays paired, merely to a different partner. The criterion runs both ways, and that is what makes it a certificate: if an augmenting path exists the pairing is provably not maximum, and if none exists the pairing provably is maximum.

code

pseudocode · 14 lines
pseudocode
// P is an augmenting path in the pairing M:
// it runs free -> ... -> free and its edges
// alternate: outside M, inside M, outside M, ...
// so P holds k edges of M and k + 1 outside it.

for each edge e in P:
    if e is in M:
        remove e from M        // this pair is broken
    else:
        add e to M             // this pair is created

// removed k, added k + 1  ->  size(M) grew by exactly one.
// Every interior vertex of P kept exactly one pair,
// so nothing that was staffed became unstaffed.

go deeper

for a junior

Recall that an assignment can sometimes be improved by moving an existing pair rather than by adding one, and that a chain of such moves has a name.

for a middle

Explain the alternation pattern and the free endpoints, and show that the edge counts differ by one so a flip gains exactly one pair whatever the path length.

for a senior

Demonstrate that you use the criterion in the strong direction: absence of any augmenting path is a proof of optimality, which is the claim you can defend when someone re-runs the assignment and gets a different arrangement.

for a principal

Weigh what the assignment service should certify. Publishing the improvement chain makes a suboptimal result explainable and reviewable; publishing only the final count leaves reviewers unable to distinguish optimal from merely unimproved.

## Alternating, augmenting, and the difference between them Fix a matching `M` on the bipartite eligibility graph whose two sides are backlog items and engineers. Call a vertex **free** when `M` does not pair it. Two definitions do all the work: - an **alternating path** is a path whose edges alternate between edges not in `M` and edges in `M`; - an **augmenting path** is an alternating path whose **two endpoints are both free**. The second condition is the whole content. Alternating paths are common and mean nothing on their own; the free endpoints are what turn one into a proof. | Structure | Endpoints | Effect of flipping every edge along it | |---|---|---| | Alternating path with one paired endpoint | One free, one paired | Size unchanged, and the flip may break a pair | | Alternating cycle (even length) | None - it closes | Size unchanged, partners rearranged | | Augmenting path | Both free | Size grows by exactly one | ## Why the flip gains exactly one, and never more An augmenting path begins at a free vertex, so its first edge cannot be in `M`; the same argument applies at the other end, so its last edge is also outside `M`. Alternation then forces the pattern *out, in, out, in, ..., out*: if the path has `k` edges from `M`, it has `k + 1` edges outside `M`, and its length is odd. Flipping means swapping membership along the path. You lose `k` pairs and gain `k + 1`, a net gain of exactly **one** - independently of how long the path is. A five-edge augmenting path has three unpaired and two paired edges, and still gains exactly one. The flip is also safe for the work already scheduled. Every interior vertex of the path was touched by exactly one path edge in `M` and one outside it; after the flip it is still touched by exactly one path edge in `M`. So no item that was staffed becomes unstaffed. Only the two endpoints change status, from free to paired, which is precisely the +1. In the small example where item `A` is eligible for engineers `X` and `Y`, item `B` only for `X`, and `M = {A-X}`: the path `B - X - A - Y` is alternating (`B-X` outside, `X-A` inside, `A-Y` outside) and both `B` and `Y` are free. Flipping yields `{B-X, A-Y}`, size two. ## The criterion, stated in both directions The reason this concept is asked at all is that it is an *if and only if*, and the two directions carry different weight: 1. **If an augmenting path exists, the matching is not maximum.** This direction is the easy one - the flip exhibits a larger matching, so the current one was beatable. 2. **If no augmenting path exists, the matching is maximum.** This direction is the theorem. It is what lets you stop and claim optimality rather than merely claim you could not find an improvement. Getting the direction backwards is the common failure. "I could not improve it" is a statement about your search; "no augmenting path exists" is a statement about the graph. Only the second one is a proof, and the criterion is what converts the first into the second. Note also what the criterion does *not* say. It does not say that every unstaffed item can be reached by an augmenting path - when a matching is maximum, items can remain unstaffed permanently, and no rearrangement will help. Their being unreachable by any augmenting path is exactly why. ## Reading it as a certificate at work The practical payoff of the criterion is in what you can tell a reader of the output: - **"We can do better"** is backed by an augmenting path: name the free item, the chain of reassignments, and the free engineer at the far end. That is a concrete, reviewable story - *move item A from X to Y, then B can take X*. - **"This is the best possible"** is backed by the absence of any such chain. It is a stronger claim and it is the one worth putting in a report, because it survives someone re-running the assignment with different input order. - **Rearrangement without gain is real and useful.** Flipping an alternating *cycle* changes who works on what while keeping the count identical, which is how preference or fairness adjustments happen without costing coverage. The criterion is a characterisation of optimality, not a procedure: the question of how one searches for such a path, and how much that search costs, belongs to the algorithmic material rather than to the structure theory here.

  • Does the augmenting-path criterion hold only when the graph is bipartite?
    The criterion itself is general: in any graph, a matching is maximum exactly when no augmenting path exists. What changes without bipartiteness is the difficulty of the search, because odd cycles let a path revisit a region and hide an improvement. That search cost is algorithmic territory; the structural statement is the same either way.
  • Can flipping along an augmenting path leave a previously staffed item unassigned?
    No. Every vertex strictly inside the path is touched by one path edge in the matching and one outside it, so after the flip it is still paired, just to a different partner. Only the two free endpoints change status, and they change from unpaired to paired, which is the net gain of one.
  • What does flipping an alternating cycle do?
    An alternating cycle has even length with equal numbers of paired and unpaired edges, so flipping it leaves the size unchanged and only swaps partners. That is the structural room you have to satisfy preferences or balance load without losing any coverage.

saying these in an interview costs you the question

  • Thinks any alternating path improves the pairing
  • Forgets that both endpoints must currently be unpaired
  • Believes a flip can unstaff an item that was already staffed
  • Claims a longer augmenting path adds more than one pair
  • Treats "I found no improvement" as equivalent to "none exists"