Augmentingpath

An augmenting path is a concept in matching theory used to increase the size of a given matching. Let G = (V,E) be a graph and M ⊆ E a matching. An M-augmenting path is a simple path whose endpoints are unmatched by M, and whose edges alternate between not in M and in M, beginning and ending with an edge not in M. If such a path P exists, flipping the status of every edge along P (including not-in-M edges and excluding in-M edges) yields a new matching M' with |M'| = |M| + 1. Thus, the existence of an augmenting path guarantees that the current matching is not maximum.

Berge’s lemma states that a matching is maximum if and only if no augmenting path exists with respect to that matching. This equivalence underpins many maximum-cardinality matching algorithms: discovering an augmenting path allows the matching to be enlarged, while the absence of such paths certifies optimality.

In bipartite graphs, augmenting paths play a central role in efficient algorithms such as the Hopcroft–Karp algorithm, which finds multiple shortest augmenting paths per phase and runs in O(E√V). In general graphs, augmenting-path methods must handle odd cycles, typically via the Edmonds’ blossom algorithm, which detects augmenting paths despite the presence of blossoms (odd-length cycles) and achieves polynomial-time performance.

The augmenting-path concept also appears in maximum flow algorithms, where augmenting paths in a residual network are used to increase the total flow, illustrating the broader utility of the idea in combinatorial optimization.