Skip to content

Jack Edmonds and the Good Algorithm

Abstract

In 1965 a mathematician at the National Bureau of Standards published an algorithm for finding maximum matchings in graphs, and stopped in the middle of the paper to apologise for a word. Section 2 is headed “Digression” and explains what he means by an efficient algorithm: one whose difficulty grows algebraically rather than exponentially with the size of the input. Jack Edmonds (born 1934) wrote that paragraph because he did not think anyone had a formal way to say it. Sixty years later the distinction he drew is the class P, the left-hand side of P vs NP.

Washington

Edmonds was born on 5 April 1934 in Washington, D.C., and went to McKinley Technology High School, graduating in 1952. He studied at Duke, finished his undergraduate degree at George Washington University in 1957, and took a master’s at the University of Maryland. From 1959 to 1969 he worked at the National Bureau of Standards, as a founding member of the operations research group that Alan Goldman built there.

That group put him in the room with the linear programming people. The matching work started, by his own account in the paper’s opening pages, from investigations “begun with G. B. Dantzig while at the RAND Combinatorial Symposium during the summer of 1961”. See George Dantzig and the Simplex Method.

The Digression

The problem was maximum matching: given a graph, pick as many edges as possible so that no two of them share a vertex. For bipartite graphs the answer had been known for decades. General graphs were harder, because of odd cycles, and Edmonds’s solution was to contract each odd cycle, a “blossom”, into a single vertex, solve the smaller problem, and expand it again. He had the algorithm in 1961 and published it in 1965 in the Canadian Journal of Mathematics as “Paths, Trees, and Flowers”.

Before describing it he wrote a section explaining his terms:

An explanation is due on the use of the words “efficient algorithm.” […] According to the dictionary, “efficient” means “adequate in operation or performance.” This is roughly the meaning I want […] Perhaps a better word is “good.” I am claiming, as a mathematical result, the existence of a good algorithm for finding a maximum cardinality matching in a graph. There is an obvious finite algorithm, but that algorithm increases in difficulty exponentially with the size of the graph. It is by no means obvious whether or not there exists an algorithm whose difficulty increases only algebraically with the size of the graph.

He then admits he cannot make it rigorous: “I am not prepared to set up the machinery necessary to give them formal meaning, nor is the present context appropriate for doing this.”

Two things are unusual about this. The first is that in 1965 the interesting question about an algorithm was still whether it terminated at all; brute-force search over all matchings is perfectly finite, and a mathematician of the period could reasonably call the problem solved. Edmonds is arguing that finiteness is worthless and the growth rate is the whole question. The second is the honesty of the disclaimer, which is why the idea is usually shared out: Alan Cobham published the same criterion in the same year, and the polynomial-time definition of tractability is filed under the Cobham-Edmonds thesis.

Matroids and Polyhedra

The companion paper, “Maximum Matching and a Polyhedron with 0,1 Vertices”, appeared in the Journal of Research of the National Bureau of Standards in 1965 and did something the algorithm alone could not. It described the matching problem as a polyhedron and gave the inequalities that define it, so that linear programming duality could be pointed at a combinatorial problem. That technique, a good description of the polyhedron leading to a fast algorithm and to a proof that the answer is optimal, became the method of the field.

The other half of the idea was what he called a good characterization: a way of certifying that an answer is optimal which can itself be checked quickly. NIST, looking back at the decade he spent there, credits him with describing the class NP, defining tractable computation as polynomial time, and conjecturing that the two are not the same.

He applied the same thinking to matroids, the abstract structure that captures what independence means in a vector space and in a graph at once. His matroid intersection theorem gives a min-max formula for the largest set independent in two matroids simultaneously, which in modern terms puts the problem in NP and in co-NP at the same time, a strong hint that it lies in P, as it does. Polymatroids, matroid partition, submodular flows with Richard Giles, optimum branchings in the 1967 Journal of Research paper, and the Gallai-Edmonds decomposition of graphs all come out of the same decade.

The name most computer science students meet first is the Edmonds-Karp algorithm of 1972, written with Richard Karp, which fixes the Ford-Fulkerson maximum flow method by always augmenting along a shortest path and thereby bounds its running time independently of the capacities. See Graph Algorithms.

Waterloo

Edmonds left the Bureau in 1969 for the Department of Combinatorics and Optimization at the University of Waterloo, and stayed there until retiring in 1999. The John von Neumann Theory Prize came in 1985, awarded by ORSA and TIMS, the two societies that merged into INFORMS ten years later, for the matching work and the polyhedral method that came with it. NIST put him in its gallery of alumni in 2014, where he talked about the technical high school in Washington rather than about matroids.

The vocabulary he was reaching for in 1965 got its formal machinery from other people. Juris Hartmanis and Richard Stearns had defined complexity classes by resource bounds in the same year (see Hartmanis and Stearns), Stephen Cook and Leonid Levin supplied NP-completeness in 1971 and 1973 (see Cook and Levin), and Karp’s 1972 list of twenty-one problems showed how much of practice sat on the other side of the line. Edmonds had drawn the line first, in a digression he apologised for.

📚 Sources