Jack Edmonds: complexity revealed
-----------------------------------
The American mathematician Jack Edmonds was born in 1934. After completing his studies, he joined the National Bureau of Standards, where he worked on graph coloring, representing them by means of maps and darts. In the late 1950s and early 1960s, graph theory moved from the realm of "pleasant and delightful problems" to become an academic subject (see Mathématiques discrètes et Combinatoire, Bibliothèque Tangente 39, 2009).
Claude Berge describes the alternating-path method for maximum-cardinality matching problems. At a famous conference in Calgary, Canada, he presents this "algorithm." Jack, sitting in the audience, stands up and says: "Claude, your algorithm stinks." ("Your algorithm stinks"). For the same problem, Jack uses alternating trees together with linear programming duality. His trees are far from simple: they may contain odd cycles, which he "shrinks" (contracts) to a single vertex, and so on, yielding a polynomial-time algorithm. The term was coined. On the night before his own talk, he attempts to generalize his algorithm to find a maximum-cardinality set of pairwise nonadjacent vertices in a graph; this is a generalization of the matching problem. Then comes a revelation: what if there are problems for which no polynomial-time algorithm exists? The study of computational complexity is born. In his paper Paths, Trees and Flowers, he describes his matching algorithm before embarking on a "digression"—his label for the paragraph in which he observes that this notion of complexity is a genuine mathematical problem.
Edmonds also pioneered polyhedral approaches, providing a complete description of the matching polytope. He went on to solve a great many polynomial-time combinatorial problems. The problem of finding a maximum-cardinality common independent set in two matroids is one example with a particularly elegant solution…
Vašek Chvátal
-------------
