Graph Algorithms

Abstract

A graph is the mathematics of “things connected to things”, and its history keeps repeating one pattern: a concrete, often mundane problem (crossing bridges, wiring villages, bombing railways, ranking web pages) produces an abstraction that outlives the problem by centuries. This article follows that pattern from Euler’s 1736 walk through Königsberg, via a Moravian electrification study and a classified Cold War report on the Soviet rail network, to Edmonds’s definition of what an efficient algorithm even is, and on to PageRank, the graph computation that built Google. Half of modern infrastructure (routing, scheduling, matching, search, social networks, chip layout) runs on results in this lineage.

Seven Bridges

Graph theory has an unusually precise birthday and a deliberately trivial birth problem. The Prussian city of Königsberg had seven bridges linking two riverbanks and two islands, and its citizens amused themselves with a puzzle: could you take a walk crossing every bridge exactly once? In 1736 Leonhard Euler proved you could not, and the proof is the founding move of the field: he threw away the geography. Only the pattern of connections matters, landmasses become points, bridges become links, and the walk exists only if at most two points have an odd number of links. Königsberg had four. Euler solved every instance of the problem forever, in a paper about no useful subject whatsoever, and the abstraction he discarded the map for is the one your phone now searches every time it plans a route. (The city is Kaliningrad today, and not all seven bridges survived the Second World War; the puzzle outlived both the name and the bridges.)

For two centuries graph theory stayed recreational mathematics: puzzles, map coloring, chess knights. It became engineering the moment there were networks worth optimizing.

Electrifying Moravia

The first graph algorithm in the modern sense was written for a power company. In 1926 the Czech mathematician Otakar Borůvka was asked how to lay out an electricity network connecting the towns of western Moravia at minimum total cable length. His solution constructed what is now called the minimum spanning tree, and his algorithm (grow cheapest connections from every component simultaneously) is still competitive. Vojtěch Jarník refined it in 1930 in a letter to Borůvka. Then the entire line of work was forgotten outside Czechoslovakia and rediscovered in the American 1950s: Joseph Kruskal (1956) and Robert Prim (1957) published the two textbook MST algorithms, Prim’s being exactly Jarník’s, and Edsger Dijkstra reinvented it again in 1959. The episode is a standing lesson in how thoroughly a result can vanish when it is published in Czech, in a regional journal, about cables.

Dijkstra’s own contribution came out of a demonstration problem. Needing something the public could grasp for a 1956 demo of the ARMAC computer, he picked shortest paths between Dutch cities and designed the algorithm in twenty minutes at an Amsterdam café, without pencil or paper (the scene is in Fun Fact: Dijkstra’s Twenty Minutes). Published in 1959 as a three-page note, Dijkstra’s algorithm is the ancestor of the routing in every GPS device and of the OSPF and IS-IS protocols that steer traffic inside the internet; extended with a heuristic sense of direction it becomes A*, the pathfinder in every video game. For networks with negative edge weights there is the Bellman-Ford algorithm, from Richard Bellman’s dynamic-programming school, still doing duty inside the internet’s BGP ancestor protocols.

Cold War Flows

The theory of network flow was born classified. In 1955, RAND Corporation analysts T. E. Harris and F. S. Ross wrote a secret report for the US Air Force modeling the Soviet and East European railway system as a network: 44 nodes, 105 edges, each rail link labeled with its capacity. The question was not how much freight the Soviets could move (though the model answered that too) but the dual question: which links to destroy, at least cost, to cut East from West? The report identified what it called “the bottleneck”. At RAND, Lester Ford and Delbert Fulkerson turned the problem into mathematics in 1956: their algorithm computes the maximum flow through any capacitated network, and their max-flow min-cut theorem proves the bottleneck intuition exact. The maximum sustainable flow equals the capacity of the thinnest cut; the shipping question and the interdiction question are the same question. The Harris-Ross report stayed secret until 1999, when it was declassified at the request of the historian of the field, Alexander Schrijver.

Stripped of its target, max-flow became one of the most reused tools in computing: airline scheduling, image segmentation, sports elimination, matching organ donors to patients. Few algorithms have a cleaner record of swords into ploughshares.

Paths, Trees, and Flowers

In 1965 Jack Edmonds published a polynomial-time algorithm for maximum matching in general graphs, the “blossom algorithm”, in a paper titled “Paths, Trees, and Flowers”. The result matters; the digression matters more. Edmonds spent a section arguing, against the indifference of the time, that the line between a “good” algorithm and a useless one should be drawn at polynomial running time: an algorithm that takes n² or n³ steps scales, one that takes 2ⁿ steps is an illusion of a solution. The distinction seemed philosophical in 1965. Six years later it became the substrate of the P versus NP question, and “polynomial time” remains the field’s working definition of efficient. Graph theory thus supplied complexity theory with its founding vocabulary, and many of the first problems shown NP-complete (Hamiltonian cycle, clique, graph coloring, the traveling salesman) were the graph puzzles the recreational era had left unsolved, now explained: nobody had found fast algorithms because, most likely, none exist.

The 1970s turned graph algorithms into a systematic discipline, largely on one technique. Robert Tarjan, alone and with John Hopcroft, showed that depth-first search organizes a graph so effectively that problems previously requiring cleverness (finding strongly connected components, 1972; testing whether a graph can be drawn without crossings, 1974) fall out in linear time. Hopcroft and Tarjan shared the 1986 Turing Award; the citation was, in effect, for making graph algorithms fast enough to be infrastructure.

The Web as a Graph

The largest graph computation in history began as a Stanford student project. In 1996 Larry Page and Sergey Brin treated the World Wide Web as a directed graph, pages as nodes and hyperlinks as edges, and asked which nodes the link structure itself considers important. Their answer, PageRank, models a random surfer who follows links forever (with an occasional bored jump to a random page) and ranks each page by the fraction of eternity the surfer spends there: mathematically, an eigenvector of the web’s link matrix, computable by iterating over a graph with billions of edges. Built into the search engine described in their 1998 paper, it out-ranked every keyword-counting rival and became Google (the fuller story is in Larry Page and Sergey Brin). Euler’s move, discard everything but the connections, turned out to be worth on the order of a trillion dollars.

The web era also made graphs the lens for society itself: the “six degrees of separation” folklore became testable network science in the late 1990s, and the social graph became the asset class behind Facebook and its successors. Graph algorithms now route packets, rank pages, suggest friends, schedule crews, verify chips, and match kidneys. The citizens of Königsberg wanted a nicer Sunday walk; they founded the mathematics of the connected world instead.