Skip to content

Hopcroft and Tarjan: Depth-First Search and the Linear-Time Graph

Abstract

In the summer of 1970 a Cornell professor on sabbatical, John Hopcroft (born 1939), and a first-year Stanford graduate student, Robert Tarjan (born 1948), started asking what depth-first search actually does to a graph. The answer, over the next four years, was that a whole class of problems that had needed ingenuity (connected components, biconnectivity, planarity) could be solved in time proportional to the size of the input. Tarjan followed with the inverse-Ackermann analysis of union-find, splay trees and Fibonacci heaps; Hopcroft to the textbooks, with Ullman and Aho, that taught the subject to everyone. They shared the 1986 Turing Award, cited for algorithms and data structures.

John Hopcroft 2009
John Hopcroft at ITMO University, St Petersburg, 24 September 2009. Image: Pavel.mavrin, public domain, via Wikimedia Commons.

Two Routes to Stanford

John Edward Hopcroft was born in Seattle on 7 October 1939 and studied electrical engineering: a BS at Seattle University in 1961, then an MS (1962) and PhD (1964) at Stanford with a dissertation on the synthesis of threshold logic networks. He taught at Princeton for three years, where one of his students was Alfred Aho, and moved to Cornell in 1967, where he has been since. With Jeffrey Ullman he wrote Formal Languages and Their Relation to Automata (1969), the book that turned the theory of automata into a course.

Robert Endre Tarjan was born in Pomona, California, on 30 April 1948, the son of a child psychiatrist who ran a state hospital; his younger brother James became a chess grandmaster. He found Martin Gardner’s columns in Scientific American in the public library, started inventing board games and puzzles, took a BS in mathematics at Caltech in 1969 and arrived at Stanford intending to do artificial intelligence. He decided within a year that AI “was too fuzzy, that it wasn’t mathematical enough,” and took Robert Floyd’s course on algorithmic problem solving instead. In John McCarthy’s LISP course the final project offered planarity testing as a topic; the class knew Kuratowski’s criterion, and nobody got a working program out of it.

What Depth-First Search Does

Hopcroft came to Stanford on sabbatical in the summer of 1970, after Tarjan’s first year, and the two began, in Tarjan’s words, to “develop a theory: what is graph search? What is depth-first search? What can you do with it? What does it do to a graph?” Depth-first search, following one path as far as it goes before backing up, imposes a tree on the graph, and every other edge in the graph turns out to point from a vertex to one of its own ancestors in that tree. That single fact is enough to find the biconnected components of a graph, the pieces that stay connected when any one vertex is removed, in one pass.

Tarjan’s paper “Depth-First Search and Linear Graph Algorithms,” in the second issue of the SIAM Journal on Computing in June 1972, did biconnected and strongly connected components this way, in time linear in the number of vertices and edges; the strongly-connected-components algorithm still carries his name. Planarity took him a year more. The best known method, by Lempel, Even and Cederbaum, was quadratic; Hopcroft and Tarjan’s “Efficient Planarity Testing,” in the Journal of the ACM in October 1974, brought it to linear time, and the problem that had defeated McCarthy’s LISP class became Tarjan’s PhD thesis (1972). Hopcroft was his de facto advisor, but as a visitor could not sign, so Floyd did, and Floyd, “an amazing perfectionist,” took the thesis apart and cost him an extra three months putting it back together. In between, Hopcroft and Richard Karp gave the n^5/2 algorithm for maximum matching in bipartite graphs (1973), which is the other algorithm with Hopcroft’s name on it. The wider story of these results is in Graph Algorithms.

Ackermann’s Function Turns Up

Tarjan followed Hopcroft to Cornell for a year and a half, “enjoying the department, suffering through the weather,” and left for Berkeley the day the snow came back in May. There he took up the union-find structure, the trees with path compression that keep track of which elements belong to which set. Everyone believed the operations took constant time on average. Tarjan showed they did not: the true bound was the inverse of Ackermann’s function, the fastest-growing function in the textbooks turned upside down, so slowly growing that it is at most five for any input that fits in the universe, but not constant. “Efficiency of a Good But Not Linear Set Union Algorithm” (Journal of the ACM, April 1975) was the first time the Ackermann function had appeared in the analysis of a real algorithm; it has since appeared in computational geometry and elsewhere, and the bound was later shown tight in the strongest models of computation.

He was on the Stanford faculty from 1974 to 1980, and his best collaborators, he said, were his students: with Thomas Lengauer the fast dominator algorithm that optimising compilers use, and with Daniel Sleator the self-adjusting binary search tree, the splay tree, whose analysis was published in 1985. A splay tree does no balancing and keeps no bookkeeping; it simply moves each accessed node to the root by rotations, and the amortised analysis shows this is within a constant factor of any fixed tree and, in a sense made precise in the paper, of the best tree that could have been chosen in hindsight. In September 1980 he took a sabbatical at Bell Labs, “the tail end of the heyday,” was made a permanent offer, and stayed until 1989, with a chair at NYU on the side; with Michael Fredman he devised Fibonacci heaps (1987), which cut Dijkstra’s shortest-path algorithm to m + n log n. He has been at Princeton since 1985, with parallel posts at NEC Research, InterTrust, HP and Microsoft Research. The data structures are described in Data Structures.

Splay Tree Search
A splay tree moving each searched node to the root by rotations. Image: EmilyDolson, CC BY-SA 4.0, via Wikimedia Commons.

Hopcroft the Teacher

Hopcroft’s second career was in books. The Design and Analysis of Computer Algorithms (1974), with Aho and Ullman, was the first graduate text to treat algorithms as a subject with its own methods, and its 1983 undergraduate successor Data Structures and Algorithms and the 1979 Introduction to Automata Theory, Languages, and Computation with Ullman, were the standard texts for twenty years (Aho and Ullman). From the 2010s he has spent much of each year in China, where Shanghai Jiao Tong University opened the John Hopcroft Center for Computer Science in 2017 and the government gave him its Friendship Award in 2016. The IEEE gave him and Ullman the von Neumann Medal in 2010.

The Award

The ACM gave the 1986 Turing Award to the two of them jointly, “for fundamental achievements in the design and analysis of algorithms and data structures.” Tarjan had already received the first Nevanlinna Prize of the International Mathematical Union in 1982, created for information science, and was elected to the National Academy of Sciences in 1987 and the National Academy of Engineering in 1988. Hopcroft joined the NAE in 1989.

Dead End: The Linear-Time Ceiling

What Hopcroft and Tarjan proved was that for a large class of graph problems the right answer is “read the input once.” That is a ceiling as well as a floor. Once planarity, components and matching were linear or nearly so, the field’s attention moved to problems where no such answer exists, the NP-hard ones, and to approximation, randomisation and parallelism, where depth-first search is of little help: it is inherently sequential, and whether it can be parallelised efficiently remains unresolved. The technique that made a decade of algorithms fall into place is now a first-year topic, taught in a week, with the names of its inventors attached to two of the algorithms and, otherwise, taken for granted.

📚 Sources