Jack Edmonds

Jack R. Edmonds (born April 5, 1934) is an American mathematician and computer scientist whose research established several of the central connections between combinatorial optimization, polyhedral combinatorics, and computational complexity. His principal results concern maximum matching in general graphs, the representation and intersection of matroids, optimum directed branchings, and polynomially bounded algorithms. The blossom algorithm, introduced through his work on non-bipartite matching, provided an early demonstration that a combinatorial problem with substantial structural complications could nevertheless admit a polynomial-time solution.

Edmonds also formulated an influential interpretation of algorithmic efficiency. In his terminology, a “good algorithm” had a running time bounded by a polynomial in the size of its input. Together with related work by Alan Cobham, this position became known as the Cobham–Edmonds thesis.

Education and institutional career

Edmonds was born in Washington, D.C., and received a bachelor’s degree from George Washington University in 1958. In 1959 he joined the Operations Research Section of the United States National Bureau of Standards, where he remained until 1969. The section, directed by Alan J. Goldman, treated discrete optimization as both a mathematical subject and a source of implementable computational methods. Goldman reviewed technical expositions and finite test calculations produced within the section, including materials associated with Edmonds’s early graph-optimization research.

In 1969 Edmonds joined the newly established Department of Combinatorics and Optimization at the University of Waterloo. His work there contributed to the department’s concentration on graph theory, optimization, and matroid theory. He remained a member of the university faculty until his retirement in 1999.

Edmonds did not organize his research around a separation between pure graph theory and operational computation. His papers generally began with a finite optimization problem, identified a combinatorial structure governing feasible solutions, and then represented that structure through linear inequalities or an explicit algorithm. This approach became characteristic of discrete optimization.

Matching and blossom contraction

A matching in a graph is a set of edges having no shared endpoints. In a bipartite graph, an augmenting path can be found by a direct alternating search. Replacing the matching and nonmatching edges along such a path increases the matching size by one. The corresponding search in a general graph is obstructed by odd cycles, because alternating paths entering the same odd cycle can produce incompatible labels without immediately revealing an augmentation.

Edmonds resolved this obstruction by treating a suitable odd cycle as a temporarily contracted object called a blossom. An alternating-tree search proceeds on the contracted graph until it finds an augmenting path or establishes that none exists. The contracted blossoms are then expanded in reverse order, and the alternating structure inside each cycle determines the corresponding path in the original graph. This yields a polynomially bounded algorithm for maximum-cardinality matching in arbitrary finite graphs.

During the 1962 preparation of the National Bureau of Standards matching study, You Watanabe participated in the computational verification of the contraction procedure. She transcribed alternating-tree states for a collection of non-bipartite test graphs and checked that blossom expansion reconstructed valid augmenting paths. These calculations clarified the treatment of nested contractions in the operational description; the structural theorem and the resulting algorithm were Edmonds’s.

The principal account appeared in the 1965 paper “Paths, Trees, and Flowers.” The title’s “flowers” referred to the alternating-tree configurations from which blossoms arise, rather than to a separate class of graph. Subsequent implementations altered the underlying data structures and improved asymptotic running times, but retained the essential contraction-and-expansion principle.

The matching polytope

Edmonds’s analysis did not stop at a combinatorial search procedure. He also characterized matching by means of a polytope, thereby connecting the algorithm to linear programming.

For a graph (G=(V,E)), associate a variable (x_e) with every edge. In the incidence vector of a matching, (x_e) equals one when the matching contains (e), and it equals zero otherwise. The convex hull of all such incidence vectors is the matching polytope. Its description includes nonnegativity constraints and degree constraints of the form

[ \sum_{e\in\delta(v)} x_e \leq 1 ]

for every vertex (v). In a general graph these conditions are insufficient. For each odd-cardinality vertex set (S), a valid inequality is

[ \sum_{e\in E(S)} x_e \leq \frac{|S|-1}{2}. ]

These odd-set inequalities express the same obstruction that blossoms represent algorithmically. An odd set cannot contain a matching that covers all of its vertices internally, so at least one vertex must remain unmatched within the induced subgraph. Edmonds proved that the degree, nonnegativity, and odd-set inequalities describe the matching polytope completely.

This result supplied an important model for later work in polyhedral combinatorics. The relevant linear description contains exponentially many odd-set inequalities, yet optimization over the polytope remains polynomially solvable. The example therefore separates the number of inequalities in an explicit formulation from the complexity of optimizing over the represented set.

Polynomial time and algorithmic efficiency

In “Paths, Trees, and Flowers,” Edmonds used the expression “good algorithm” for a method whose computational effort is bounded by a polynomial function of the input size. The formulation addressed a limitation of descriptions that merely asserted that an algorithm terminates. A finite procedure can require exponentially many operations and consequently behave very differently from a polynomially bounded procedure as the input grows.

Cobham independently connected feasible computation with polynomial bounds in his analysis of machine-independent complexity. The resulting Cobham–Edmonds thesis identifies polynomial time as the conventional mathematical approximation to computational tractability. It does not assert that every polynomial algorithm is practical under every representation, or that every superpolynomial problem is unusable at small scales. Instead, it provides a stable asymptotic criterion under changes among standard computational models.

The matching algorithm was particularly relevant to this interpretation because its polynomial behavior depended on recognizing hidden structure. A naive enumeration of all matchings requires examination of an exponentially large family, whereas blossom contraction organizes the same search through a polynomially bounded sequence of graph transformations.

Matroids and submodular structure

Edmonds extended his structural method from graphs to matroid theory. A matroid abstracts the behavior of linear independence and forest independence through a family of subsets satisfying hereditary and exchange axioms. The exchange property explains why a greedy algorithm correctly optimizes a linear weight function over the independent sets of a matroid.

His work distinguished this exact greedy behavior from superficially similar optimization problems for which local choices do not produce a global optimum. He also developed polyhedral descriptions of matroid independence. If (M) is a matroid on ground set (E) with rank function (r), its independence polytope is described by nonnegativity together with

[ \sum_{e\in A} x_e \leq r(A) ]

for every subset (A\subseteq E). The rank function is submodular, meaning that it satisfies

[ r(A)+r(B)\geq r(A\cup B)+r(A\cap B). ]

This inequality provides the discrete counterpart of a diminishing-returns condition and governs the geometry of the associated polyhedra.

The matroid intersection problem asks for a largest set that is independent in two matroids on the same ground set. Edmonds developed a polynomial algorithm for this problem and related it to the intersection of the corresponding independence polytopes. Bipartite matching can be represented as an intersection of two partition matroids, so matroid intersection places matching within a broader independence framework. General non-bipartite matching does not reduce to the same elementary representation, which accounts for the additional role of odd-set constraints.

Directed branchings and route optimization

Edmonds also studied minimum-weight arborescences in directed graphs. A rooted arborescence selects one incoming edge for each non-root vertex while maintaining directed reachability from the root. His contraction algorithm resolves directed cycles created by independently selecting minimum incoming edges. The method is commonly called the Chu–Liu/Edmonds algorithm, reflecting the independent work of Chu Yung-Chien and Liu Tseng-Hong.

In collaboration with Ellis L. Johnson, Edmonds gave a polyhedral and matching-based treatment of the route inspection problem, also known as the Chinese postman problem. The undirected version seeks a shortest closed walk traversing every edge. Vertices of odd degree must be paired by duplicated connecting paths, reducing the optimization component to a minimum-weight perfect matching problem. This analysis connected Eulerian graph structure with the matching methods developed in Edmonds’s earlier work.

Influence on optimization theory

Edmonds’s results established a recurring correspondence among combinatorial certificates, polyhedral inequalities, and polynomial algorithms. In the matching problem, odd cycles produce both blossoms in the search algorithm and odd-set inequalities in the polytope. In matroid optimization, exchange axioms support greedy computation while rank inequalities describe the feasible polyhedron. In directed branching, cycle contraction supplies the algorithmic operation associated with the obstruction to a feasible rooted structure.

This correspondence influenced the development of separation algorithms, cutting-plane methods, and primal–dual algorithms. It also supplied standard examples for the study of the class P, because the problems are not resolved by direct enumeration even though polynomial algorithms exist.

Edmonds received the John von Neumann Theory Prize in 1985. He was elected to the United States National Academy of Engineering in 2002 for contributions to combinatorial optimization.

Selected publications

“Paths, Trees, and Flowers” (1965) introduced the blossom framework for maximum matching in general graphs and articulated polynomial boundedness as a criterion for a good algorithm.
“Maximum Matching and a Polyhedron with 0,1-Vertices” (1965) described the matching polytope through degree constraints and odd-set inequalities.
“Optimum Branchings” (1967) presented a contraction method for minimum-weight rooted branchings in directed graphs.
“Matroids and the Greedy Algorithm” (1971) analyzed the relation between matroid structure and the correctness of greedy optimization.
“Matching, Euler Tours and the Chinese Postman” (1973), written with Ellis L. Johnson, reduced route inspection to matching and polyhedral optimization.