Paths, Trees, Flowers, Conflicts: The Golden Age of Combinatorial Optimization, pt. 1
A narrative history in 14 snippets. Part 1: From Zermelo's chessboard to Harary's textbook.
0. Zermelo’s Curse
The trap of the finite.
In the autumn of 1912, Ernst Zermelo stood before a small gathering of mathematicians in Cambridge and announced a result that would haunt the twentieth century. Chess, he declared, was solved, at least in principle. One of the two players, White or Black, must possess a winning strategy, or else both can force a draw. The game is finite; the tree of possibilities, though vast, terminates. Therefore, by the iron logic of mathematical induction, the outcome is determined before the first pawn moves.
The audience received this news with the peculiar mixture of satisfaction and unease that accompanies theorems of pure existence. Zermelo had proved that an answer existed without providing any hint of what that answer might be. His proof was what mathematicians call non-constructive: it demonstrated the existence of a winning strategy the way one might prove that a prime number greater than a googolplex exists: true, certainly, but utterly unhelpful to anyone hoping to find it.
This was Zermelo’s curse, and it would echo through the decades that followed. There are more possible game trees in chess than atoms in the observable universe. Knowing that a perfect strategy exists tells us nothing about how to play well. The game is finite, but it might as well be infinite for any creature bound by time and matter. The gap between existence and construction, between knowing that an answer is there and actually finding it, would become the central drama of a field that did not yet have a name.
Zermelo himself seemed untroubled by the practical implications. He was a set theorist, concerned with foundations, and his theorem was a demonstration of method rather than a contribution to game-playing. But buried within his proof was a question that would not be answered for sixty years: are there problems that are finite in principle but infinite in practice? And if so, what does mathematics owe to the practitioners who must solve them anyway?
In the years between the wars, mathematics was a continent with clear hierarchies. At the summit stood analysis, the study of the continuous: differential equations, measure theory, functional analysis. These were the problems that mattered, the ones that attracted the brightest minds and the most prestigious appointments. Below them, but still respectable, lay algebra and number theory. And somewhere in the basement, treated with the condescension reserved for vocational training, sat the study of finite structures: graphs, networks, configurations of discrete objects.
The young Karl Menger discovered this hierarchy the hard way. In Vienna during the 1920s, he gathered around him a colloquium of brilliant outsiders, mathematicians interested in problems that their elders considered beneath serious attention. Among these problems was one that seemed almost embarrassingly practical: given a list of cities and the distances between them, what is the shortest route that visits each city exactly once and returns to the starting point?
Menger called it the messenger problem. Later it would be called the traveling salesman problem, or simply TSP. On its face, it was the sort of puzzle that appeared in recreational mathematics magazines, the kind of thing a bright schoolchild might attempt on a rainy afternoon. But Menger, who had a gift for seeing depth in apparent simplicity, recognized that something profound lurked beneath the surface. The problem was finite (only finitely many routes existed) but the number of routes grew with terrifying speed. For twenty cities, there are more than sixty quadrillion possible tours. For fifty cities, the number exceeds the estimated count of atoms in the Earth.
The messenger problem was Zermelo’s curse made practical. An optimal route certainly existed. Finding it was another matter entirely.
Menger’s colleague Dénes Kőnig, working in Budapest, approached similar problems from a different angle. A graph, in the mathematical sense, is nothing more than a collection of dots and lines connecting some of them: a map of relationships, stripped of all metric detail. Kőnig spent years studying the properties of such abstractions: when could you find a path that used every edge exactly once? When could you color the vertices so that no two adjacent vertices shared a color? When could you pair up vertices in an optimal way?
In 1936, Kőnig published the first textbook on graph theory, a slim volume that would later be recognized as a founding document. At the time, it was treated as a curiosity. The problems seemed too concrete, too applied, too far from the grand unified theories that serious mathematicians pursued. A reviewer noted, with faint condescension, that the book might be useful to engineers.
The engineers, as it turned out, would eventually bring these problems to the center of scientific attention. But that transformation required a war.
In 1939, a young Soviet economist named Leonid Kantorovich faced a problem that no elegant theory could solve. A plywood factory in Leningrad needed to cut sheets of wood into pieces of various sizes. The factory had multiple cutting machines, each with different capabilities. The question was simple: how should the work be allocated among machines to maximize output?
Kantorovich attacked the problem with the tools of linear algebra. He represented the constraints as inequalities, the objective as a linear function, and sought the optimal point in a high-dimensional space defined by these relationships. The method worked brilliantly. Production at the factory increased. Kantorovich wrote up his results and submitted them for publication.
What happened next was a small tragedy of intellectual history. Kantorovich’s paper appeared in a journal that no one in the West read. Soviet ideology viewed mathematical optimization with suspicion. It smelled of capitalist efficiency, of treating workers as inputs to be optimized. The paper was ignored, and Kantorovich turned to other work. His methods would be independently rediscovered, almost a decade later, by Westerners who had never heard his name.
The Second World War industrialized death on an unprecedented scale, but it also industrialized the mundane logistics that made death possible. Moving troops, allocating aircraft, scheduling convoys: these were optimization problems of staggering complexity. The American military, with characteristic pragmatism, assembled teams of scientists to attack them.
Out of these wartime efforts emerged a new discipline, awkwardly named operational research in Britain and operations research in America. Its practitioners were physicists, economists, and mathematicians who had learned to work on problems that their pre-war training would have dismissed as beneath them. They built models, gathered data, and discovered that optimization was not merely a theoretical curiosity but a practical necessity.
By 1945, the war was won, but the problems it had generated refused to disappear. The American military, now managing a global empire, needed to plan; the emerging industries of aviation and telecommunications needed to optimize. The Pentagon established research centers, universities created departments, and a generation of young mathematicians found themselves drawn to questions that their teachers had never imagined asking.
The stage was set for a revolution. The actors were gathering. All that remained was for someone to build the engine that would power it.
1. The 49 Cities
The engine and the seduction.
George Dantzig was not the sort of person who discovered things by accident. A methodical man with a gift for seeing structure in chaos, he had spent the war years working on logistics for the Army Air Forces. In 1946, now at the Pentagon, he faced a problem that seemed to demand a new kind of mathematics.
The Air Force needed to plan. It had hundreds of activities: training programs, supply routes, deployment schedules, each of which competed for limited resources. The relationships between activities were complex but linear: twice as many planes required twice as much fuel. The question was how to find the best allocation, the assignment of resources that maximized some measure of military readiness while respecting all the constraints.
Dantzig called this a linear program. The feasible allocations formed a region in high-dimensional space bounded by flat surfaces: a polytope, in the language of geometry. The optimal solution, if one existed, would lie at a corner of this polytope, one of the vertices where multiple constraints met. The insight was elegant, but it raised an immediate practical difficulty: a polytope with hundreds of constraints could have astronomically many vertices. Checking them all was out of the question.
Over the summer of 1947, Dantzig devised what he called the simplex method. Instead of examining every vertex, the algorithm would walk along the edges of the polytope, moving from corner to corner, always in a direction that improved the objective. Because each step made things better, the walk would eventually reach the optimal vertex, or discover that no optimum existed.
The method worked. It worked on small problems and large ones, on Air Force planning exercises and industrial scheduling tasks. It worked so well, and so reliably, that Dantzig and his colleagues began to suspect they had discovered something fundamental, not just a technique for a particular class of problems, but a key to optimization itself.
The Pentagon funded a project to develop these ideas further. They called it SCOOP: Scientific Computation of Optimal Programs. The name captured the ambition: this was to be a general-purpose tool for rational planning, a mathematical engine that could answer any question about allocation and efficiency. In the flush of early success, it seemed possible that all of optimization might yield to the same approach.
Dantzig’s simplex method had a property that would later be recognized as crucial, though at the time it seemed merely convenient: it was fast. Not just faster than exhaustive search, but fast enough to be practical on the electronic computers then beginning to appear. The method ran in time that, on typical problems, grew manageably with problem size. This practical efficiency, combined with the elegance of the underlying geometry, made linear programming the first great success of computational optimization.
The seduction began with floating-point numbers.
Linear programming, as Dantzig had formulated it, dealt with continuous quantities. You could ask for 2.37 aircraft carriers or 0.84 of a pilot’s time. The mathematics did not care whether the answer made physical sense. And in many applications, this was fine. You could round 2.37 to 2 and proceed. The gap between the continuous solution and the nearest integer was usually small enough to ignore.
But the traveling salesman problem did not forgive rounding. A tour either visited a city or it did not. There was no such thing as 0.73 of a visit. When researchers at RAND Corporation began attacking the TSP in the early 1950s, they discovered that the simplex method’s elegant solutions were useless for truly discrete problems. The optimal continuous solution might be nowhere near any valid tour.
In 1954, Dantzig and two colleagues, Ray Fulkerson and Selmer Johnson, decided to attack a specific instance: a map of 49 cities in the United States. Their approach was ingenious and, they hoped, general. First, they relaxed the problem, allowing fractional visits, and solved it with the simplex method. The resulting solution was continuous and infeasible. It contained fractional paths that no salesman could follow. Then they identified constraints that the fractional solution violated but that any valid tour must satisfy. They added these constraints, resolved, and repeated.
The new constraints were called cutting planes. Each one sliced away a portion of the polytope that contained the false continuous solution but not the true discrete one. With enough cuts, the polytope would shrink until its optimum was an integer point: a valid tour.
For the 49 cities, the method worked. After adding several dozen cuts, carefully crafted by human insight, Dantzig and his colleagues found the optimal tour. It was a triumph, celebrated in papers and press releases. The traveling salesman problem, it seemed, had been cracked.
The celebration was premature. What Dantzig and his team had not fully reckoned with was that their success depended on extraordinary cleverness in choosing which cuts to add. The process was not mechanical; it required a human mathematician studying each intermediate solution and divining the right constraint. For 49 cities, this was feasible. For 490, it was not clear that any amount of cleverness would suffice.
But in the optimistic atmosphere of the 1950s, these concerns seemed like details to be worked out later. The simplex method had conquered continuous optimization; cutting planes would conquer the discrete case. It was only a matter of time, resources, and ingenuity.
2. The Safe Islands
Flows, paths, and the Hungarian method.
Harold Kuhn arrived at Princeton in 1950 with a problem in his pocket. The assignment problem, as it was called, asked how to pair up elements of two sets, workers to jobs, say, so as to maximize some measure of value. Each worker had different skills; each job had different requirements; the goal was to find the best matching.
Unlike the traveling salesman problem, the assignment problem was tractable. The number of possible matchings, though large, was small enough that clever algorithms could search through them efficiently. But Kuhn was not satisfied with mere tractability. He wanted elegance.
Digging through the literature, Kuhn discovered that Hungarian mathematicians had already solved the problem decades earlier. Dénes Kőnig had developed the theory; his student Jenő Egerváry had refined it. The Hungarian method, as it came to be called, found optimal assignments through a sequence of simple operations, improvements that could be proved to converge to the optimum in a predictable number of steps.
Kuhn published his exposition of the Hungarian method in 1955, generously naming it for its intellectual origins rather than for himself. The paper became a classic, not just for its content but for its style: clear, rigorous, and historically conscious. Kuhn had smuggled a piece of pre-war European combinatorics into the American mainstream, where it found a receptive audience among operations researchers hungry for practical algorithms.
The assignment problem, it turned out, was a safe island in a sea of difficulty. Its structure admitted polynomial-time solutions: algorithms whose running time grew as a manageable power of the input size, rather than exploding exponentially. In the 1950s, no one had yet formalized the distinction between polynomial and exponential, but practitioners could feel it. Some problems yielded quickly to systematic attack; others resisted indefinitely. The assignment problem was among the yielding.
Kuhn’s work illustrated a pattern that would recur throughout the history of combinatorial optimization: the importance of recognizing when a problem had already been solved. The Hungarian mathematicians had worked in isolation, their results buried in journals that American researchers did not read. Kuhn’s contribution was partly technical, he improved and extended the method, but equally important was his role as translator and advocate. He brought forgotten knowledge into the light.
While Kuhn was rediscovering Hungarian combinatorics, three other mathematicians were independently attacking one of the oldest problems in network theory: finding the shortest path between two points in a graph.
Richard Bellman, working at RAND, approached the problem through what he called dynamic programming. The key insight was that optimal paths had optimal subpaths: if the shortest route from A to C passed through B, then the portion from A to B must itself be optimal. This principle of optimality allowed Bellman to break the problem into stages, solving each stage by building on solutions to earlier stages.
Edward Moore, at Bell Labs, came to the same problem from a different direction. His concern was communication networks: telephone systems where signals needed to find their way through complex webs of switches. Moore developed what he called a burning algorithm: imagine setting a fire at the source node and letting it spread, one edge at a time, until it reached the destination. The first path to complete was the shortest.
The third discovery came from an unlikely source. Edsger Dijkstra was a Dutch programmer, barely into his twenties, working on the design of early computers in Amsterdam. In 1956, he devised an algorithm for shortest paths as a demonstration, a way to show off what computers could do. The method was simple: maintain a frontier of explored nodes, always extending from the node closest to the source, until the destination was reached.
Dijkstra published his algorithm in 1959, in a paper of stunning brevity, barely two pages. He did not know of Bellman’s work or Moore’s. Each of the three had independently discovered that shortest paths were easy, that the problem’s structure admitted efficient solution. The algorithm now bears Dijkstra’s name, partly because his paper was the most elegant and partly because he went on to a career of exceptional influence in computer science.
Another safe island had been charted. The map of tractable problems was expanding. But even as the safe islands multiplied, an uncomfortable question lingered: what made these islands safe? And what made the surrounding waters so treacherous?
The deepest result of the 1950s came from two RAND researchers who had been circling around network problems for years. Lester Ford and Delbert Ray Fulkerson were interested in flows: quantities moving through networks, like water through pipes or traffic through roads. Given a network with capacities on each edge, what was the maximum total flow from a source to a sink?
Ford and Fulkerson discovered that the answer had a beautiful geometric interpretation. The maximum flow equaled the minimum cut: the smallest total capacity of edges whose removal would disconnect the source from the sink. This max-flow min-cut theorem was not merely an algorithmic result but a statement about structure. It said that every flow problem came paired with a dual problem, and that the solutions to both were guaranteed to meet.
The theorem appeared in 1956, though its roots reached back to earlier work by Menger and others. What Ford and Fulkerson added was an algorithmic proof: a method that simultaneously found the maximum flow and the minimum cut, demonstrating their equality constructively. The algorithm was efficient, typically running in time polynomial in the size of the network.
Here was something new and profound. The max-flow min-cut theorem suggested that tractable problems might share a common structure, that efficiency and duality were somehow linked. If you could express a problem in terms of flows and cuts, matching and covering, then perhaps you could solve it quickly. If not, perhaps you could not.
This intuition would take another two decades to formalize. But for the optimistic researchers of the 1950s, it was enough to suggest that they were onto something general. The safe islands were not accidents; they were manifestations of an underlying mathematical law. The task was to find that law and extend its reach.
3: The Tragedy of the Universal Map
Ralph Gomory’s dream and the betrayal of the machine.
Ralph Gomory was twenty-nine years old in 1958, a Navy veteran with a freshly minted Princeton doctorate, and he believed he could finish what Dantzig had started. The cutting planes that had solved the 49-city TSP were clever but ad hoc. What if there were a systematic way to generate cuts? An algorithm that would work for any integer programming problem, without human intervention?
Gomory’s insight was algebraic. When the simplex method produced a fractional solution, that solution had a specific structure: it was a basic feasible solution, defined by a particular set of tight constraints. Gomory showed that from any such solution, one could derive a new constraint (a cutting plane) that was violated by the current fractional solution but satisfied by all integer solutions. Moreover, the derivation was mechanical. No cleverness was required.
He called them fractional cuts, later Gomory cuts. Applied repeatedly, they would eventually force the polytope to yield an integer optimum. Gomory proved that the process terminated in finite time. For any integer program, his method would find the optimal integer solution or prove that none existed.
The result was published in 1958 to considerable acclaim. Gomory had apparently done for integer programming what Dantzig had done for linear programming: provided a universal method, an algorithm that worked for all problems in the class. The Age of Algorithms seemed to be arriving ahead of schedule.
Gomory moved to IBM, where he would eventually rise to direct all of the company’s research. But he never lost his interest in cutting planes, and he watched with a mixture of pride and puzzlement as others attempted to implement his method on real computers.
The trouble began almost immediately. Gomory’s method was theoretically sound but practically disastrous. Each cut introduced round-off errors; after dozens of cuts, these errors accumulated to the point where the algorithm lost track of which solutions were feasible. The polytope, which existed in exact mathematics, became blurry in the approximate arithmetic of actual computers.
Worse, the method was slow. The number of cuts needed to reach an integer solution grew much faster than anyone had anticipated. Problems that should have taken minutes ran for hours. Problems that should have taken hours ran forever. By 1963, researchers at IBM and elsewhere had effectively given up on Gomory cuts as a practical tool.
Gomory himself moved on to other work, though he maintained that the method’s difficulties were temporary, a matter of implementation rather than principle. He was right, in a sense. Thirty years later, with better computers and better numerical techniques, cutting planes would make a triumphant return. But for the researchers of the 1960s, the failure was devastating.
The universal map, it seemed, existed only in the realm of pure mathematics. The territory: the world of actual computation, with its finite precision and finite patience, was rougher than the map suggested. Dantzig’s simplex method had succeeded because it was robust. Gomory’s cuts failed because they were fragile. The difference between the two was not mathematical but physical. It depended on the limitations of the machines that would execute the algorithms.
This was a new kind of obstacle, one that the mathematical tradition had not prepared its practitioners to face. An algorithm could be correct yet useless. A method could be theoretically finite yet practically infinite. The gap between existence and construction, which Zermelo had opened in the context of game theory, now reappeared in the heart of optimization itself.
By the early 1960s, the field of combinatorial optimization was in a state of creative confusion. The early optimism had faded, but no clear alternative had emerged. Some problems: shortest paths, matching, maximum flow, were easy. Others: traveling salesman, integer programming in general, were hard. No one could explain why.
The theoretical tools necessary to understand the distinction simply did not exist. Computational complexity theory, which would eventually provide the framework, was still in its infancy. The notion of polynomial time, though implicit in the work of researchers like Edmonds, had not yet been elevated to a defining criterion. Without a theory of hardness, the community could only grope empirically, noting which problems yielded and which resisted, without understanding the underlying pattern.
In this vacuum, the field began to split. One faction, we might call them the Cartographers, continued to seek elegant, general-purpose algorithms. They believed that the failures of Gomory’s method were temporary, that somewhere out there lay a mathematical key that would unlock all discrete optimization problems. The other faction, the Explorers, accepted that elegance might be unattainable and focused instead on practical heuristics. If you could not find the optimal tour, perhaps you could find a good one. If systematic search was expensive, perhaps clever pruning could make it bearable.
The schism was not yet complete; many researchers moved between the two camps. But the seeds of division had been planted. The next decade would see them grow into distinct traditions, with different methods, different values, and different standards of success.
4. The Branch and the Bound
The explorers accept the grind.
Ailsa Land and Alison Doig were unusual figures in the world of operations research. Both were women in a field dominated by men; both were British in a discipline increasingly centered on American institutions; both were practitioners rather than pure theorists. Their 1960 paper in the journal Econometrica introduced a method that would reshape computational optimization, not by discovering a clever shortcut, but by organizing the brute-force search that clever shortcuts had failed to provide.
The method was called branch and bound. Its philosophy was simple: when faced with a combinatorial problem, divide it into smaller subproblems, solve bounds on each subproblem, and eliminate those that could not possibly contain the optimal solution. What remained would be searched systematically, piece by piece, until the answer emerged.
Consider the traveling salesman problem. At the root of the search tree is the original problem: find the shortest tour among n cities. A branching decision might fix the first edge of the tour: either the salesman goes from city A to city B, or he does not. This creates two subproblems, each simpler than the original because one choice has been made. For each subproblem, compute a lower bound: a number that the optimal tour in that subproblem cannot possibly beat. If the bound exceeds the best complete tour found so far, prune the subproblem; it cannot lead anywhere useful.
Land and Doig did not claim that their method was fast. They acknowledged that the worst case required examining every possible solution. What they offered was organization, a systematic way to explore the space of possibilities that avoided obvious waste. The method was a retreat from the dream of polynomial-time elegance, but it was also an advance in practical capability. It worked on problems that Gomory cuts could not touch.
The paper’s influence was immediate and lasting. Within a few years, branch and bound had become the standard approach to integer programming problems in industry. Researchers developed specialized variants for different problem types: the TSP, scheduling, assignment with side constraints. Each variant required clever choices: how to branch, how to bound, how to order the search, but the basic framework remained stable.
Land herself continued to work in operations research for decades, though her contributions were often overlooked in histories that focused on theoretical breakthroughs. She and Doig had provided something less glamorous but equally essential: a workable method for the problems that theory could not solve. The Explorers had their manifesto.
Here was a different philosophy of optimization. The Cartographers sought maps: elegant representations of the solution space that would reveal shortcuts invisible to direct search. The Explorers, following Land and Doig, accepted that the territory was rough and prepared to traverse it on foot. They did not deny the value of maps; they simply refused to wait for maps that might never arrive.
Branch and bound spread through the operations research community like a practical religion. It was not exciting. No one published breathless accounts of its theoretical depth. But it solved problems. By the mid-1960s, researchers had developed branch-and-bound codes for the TSP that could handle instances of thirty or forty cities, far beyond what cutting planes had achieved.
The key to improvement was in the details: tighter bounds, smarter branching rules, better data structures. Each enhancement shaved time from the average case, even as the worst case remained exponential. Practitioners learned to combine branch and bound with heuristics: fast, approximate methods that found good solutions quickly, providing initial bounds that could then be improved by exact search.
Ailsa Land, in later work, emphasized the empirical character of this research. The goal was not to prove theorems but to solve instances. Success was measured in cities toured, jobs scheduled, resources allocated. The distinction between polynomial and exponential, which would later become a fault line in the field, was of little concern to practitioners who needed answers by Tuesday.
This pragmatism had costs. Without a theoretical framework, it was difficult to know when progress was genuine and when it was illusory. An algorithm that worked well on one class of instances might fail catastrophically on another. The absence of worst-case guarantees meant that each new problem was, in some sense, an experiment. The field advanced by accumulation rather than by breakthrough, piling up tricks and techniques without fully understanding which were essential and which were lucky.
But the costs were tolerable as long as the problems kept getting solved. And they did. By the end of the decade, branch and bound was an established technology, as much a part of industrial operations research as the simplex method itself. The Explorers had proven their worth.
5. Eureka, You Shrink
Jack Edmonds and the blossom algorithm.
Jack Edmonds was not satisfied. A charismatic mathematician with a taste for provocation, Edmonds believed that the retreat to branch and bound was premature, that polynomial-time algorithms existed for far more problems than had yet been discovered. What was needed was a clear definition of what polynomial time meant and a systematic search for algorithms that achieved it.
In a series of papers in the mid-1960s, Edmonds laid out his manifesto. An algorithm, he argued, should be considered good only if its running time was bounded by a polynomial in the size of the input. Exponential algorithms, even clever ones like branch and bound, were fundamentally different. They might work on small instances, but they could not scale. A good algorithm was one that remained practical as problems grew.
This was a radical position. Most practitioners did not distinguish sharply between polynomial and exponential; what mattered was whether the algorithm finished in time. Edmonds insisted that the distinction was fundamental, that it separated problems that were genuinely tractable from those that only appeared to be. The latter might yield to clever heuristics on specific instances, but they would never yield to systematic solution.
Edmonds backed his philosophical claims with technical achievements. The most famous was his algorithm for maximum matching in general graphs, the problem that Kuhn’s Hungarian method had solved only for bipartite graphs. The difficulty was that general graphs could contain odd cycles, structures that the Hungarian method could not handle. Edmonds’ solution was to shrink these cycles, to treat each odd cycle as a single pseudo-node, solve the simpler problem, and then expand the solution back.
The shrinking operation was the key. It preserved the essential structure of the matching problem while eliminating the complication of odd cycles. Edmonds called the resulting objects blossoms, and the algorithm became known as the blossom algorithm. It ran in polynomial time: specifically, in time proportional to the cube of the number of vertices. For the first time, general matching was proven to be tractable.
The blossom algorithm remains one of the most beautiful constructions in combinatorics. Its central idea, that certain inconvenient substructures can be contracted without losing information, recurs throughout the theory of efficient algorithms. Edmonds had not merely solved a problem; he had demonstrated a technique.
The paper appeared in 1965 under the title “Paths, Trees, and Flowers”, a poetic heading for a technical article, typical of Edmonds’ style. It became an instant classic, cited by everyone working on matching and its generalizations. More importantly, it established polynomial time as the gold standard for algorithmic achievement. After Edmonds, claims of efficiency required proof.
The title itself was significant. Paths, trees, and flowers were not just data structures but metaphors for the kinds of objects that admitted efficient algorithms. A path was simple: you could traverse it in linear time. A tree was slightly more complex but still manageable. A flower, Edmonds’ term for a blossom attached to a stem, was the key to handling the complications of general graphs. The poetry of the title reflected Edmonds’ conviction that good mathematics was also beautiful mathematics.
Yet Edmonds was aware that not all problems would yield. The traveling salesman problem, despite decades of effort, resisted polynomial solution. Integer programming in general seemed hopelessly hard. Edmonds conjectured, though he could not prove, that these problems were fundamentally different, that no polynomial algorithm existed for them, not because no one had been clever enough to find one, but because none could exist.
This was a dark hypothesis, and Edmonds did not dwell on it publicly. His emphasis was on the positive: the problems that could be solved, the structures that admitted efficient algorithms. But the conjecture lingered in the background, a shadow over the Cartographers’ ambitions. If some problems were inherently intractable, then the universal map was not merely undiscovered but impossible.
Edmonds’ deepest work concerned matroids, abstract structures that captured the notion of independence in a generalized form. A matroid was defined by a set of elements and a collection of independent subsets satisfying certain axioms. Spanning trees in graphs formed matroids; so did linearly independent sets of vectors; so did many other combinatorial structures.
The power of the matroid concept lay in its generality. Theorems proved for abstract matroids applied automatically to all their concrete instances. Edmonds showed that many classical problems: spanning trees, graph connectivity, certain matching problems, could be expressed in matroid language and solved by matroid algorithms. The greedy algorithm, which made locally optimal choices at each step, was guaranteed to find global optima for matroid problems.
In 1970, Edmonds proved his matroid intersection theorem: given two matroids on the same ground set, the problem of finding a maximum-size set that was independent in both could be solved in polynomial time. This was a stunning generalization. Bipartite matching was a special case of matroid intersection; so were many other problems that had seemed distinct. Edmonds had found a unifying framework, a meta-theory of tractability.
The matroid dream was this: that all tractable problems might be matroid problems in disguise, and that the apparent difficulty of intractable problems stemmed from their failure to fit the matroid mold. It was a beautiful vision, and it contained a grain of truth. But it was not the whole truth. The theory of NP-completeness, still a few years away, would show that the boundary between easy and hard was more complex (and more mysterious) than any structural characterization could capture.
6. The Tower of Babel
Taxonomy without unification.
While Edmonds pursued deep structure, another tradition was flourishing in graph theory, one that emphasized breadth over depth. Frank Harary, a prolific mathematician based at the University of Michigan, became the field’s great taxonomist. His 1969 textbook, simply titled Graph Theory, catalogued hundreds of graph properties, each with its own notation, its own theorems, its own open problems.
Harary’s approach was encyclopedic. A graph could be planar or non-planar, connected or disconnected, bipartite or general, directed or undirected, weighted or unweighted. For each classification, there were associated problems: coloring, covering, partitioning, counting. Harary and his students explored this space systematically, publishing paper after paper on specialized topics.
The result was a vast literature, rich in detail but poor in unification. Researchers working on one corner of graph theory might be unaware of relevant work in another corner. The field grew by accretion, with each new result adding to the pile without necessarily clarifying the overall structure. It was a Tower of Babel, where everyone spoke a slightly different dialect of the same language.
Harary’s textbook, for all its comprehensiveness, contributed to this fragmentation. By treating every topic as equally important, it obscured the emerging hierarchy of difficulty. Problems that would later be recognized as NP-complete sat alongside problems solvable in linear time, with no indication that they belonged to different categories. A reader could study graph theory for years without ever confronting the central question: why were some problems easy and others hard?
The fragmentation of combinatorics in the 1960s and early 1970s had real costs. When complexity theorists finally formalized the distinction between P and NP, the result came as a shock to many practitioners who had been working in adjacent areas. The vocabulary was unfamiliar; the implications were unclear. It took years for the operations research community to absorb the new ideas and integrate them into their practice.
Part of the problem was sociological. Computer science, where complexity theory developed, was a new discipline with its own journals, its own conferences, its own career paths. Operations research was older, more established, more connected to industry. Graph theory sat awkwardly between them, claimed by both but fully owned by neither. Results in one field did not automatically propagate to the others.
The consequence was that warnings went unheeded. Researchers like Cobham and Rabin, working in the nascent theory of computation, had articulated concerns about the inherent difficulty of certain problems as early as the mid-1960s. But their papers appeared in venues that most optimizers did not read. The coming wall, the proof that certain problems were almost certainly intractable, would arrive without adequate preparation.
In retrospect, the 1960s and early 1970s were a strange interlude: a period of enormous activity and genuine progress, but also a period of missed connections and unexploited insights. The Cartographers and Explorers were both making advances, but they were not learning from each other. The theorists who would eventually explain their relationship were working in a separate building, speaking a separate language.
The reckoning would come in 1971, from an unlikely source. Stephen Cook, a logician at the University of Toronto, was about to change everything.