Graph Algorithms

Graph algorithms are procedures for computing with networks of points and the links between them.

13 frameworks, from 1931 to today · Algorithms · Computer Science

still a working view ended · each leads to its entry below

Overview

Graph algorithms are procedures for computing with networks of points and the links between them12. A graph is just that: a set of vertices (points) and edges (connections), which can stand for cities and roads, people and friendships, web pages and hyperlinks, or tasks and prerequisites12. The field matters because an enormous range of practical questions—what is the shortest route, who is connected to whom, how should jobs be scheduled, which pages deserve ranking—turn out to be graph questions, and the difference between a clever method and a naive one is often the difference between a computation finishing in seconds and not finishing at all. The history of graph algorithms is the story of finding those clever methods, proving what they can and cannot do, and discovering that some of the most natural questions about graphs are, in a precise sense, intractable.

Foundations in puzzles and networks, 1736–1930s

The subject begins with a puzzle. In 1736 Leonhard Euler asked whether one could walk through the city of Königsberg crossing each of its seven bridges exactly once13. He answered no, and in doing so gave the first theorem about graphs: a closed walk using every edge once exists only if every vertex has even degree (an even number of edges meeting it). This is the origin of Eulerian paths, and it established the habit of reasoning about connectivity and degree rather than about geography3.

For nearly two centuries the work stayed mathematical. Gustav Kirchhoff used graphs to analyze electrical circuits in the 1840s, and in 1857 Arthur Cayley connected trees—graphs with no cycles—to the counting of chemical isomers. The four-color problem, posed in 1852, drove a century of graph theory. But these were theorems, not algorithms in the modern sense; nobody was measuring the cost of a computation.

Shortest paths and the birth of efficient procedures, 1950s–1960s

The modern field crystallizes in the 1950s, when computers made the cost of a procedure a practical concern. The central problem was shortest paths: given a network with edge lengths, find the cheapest route between vertices. Edsger Dijkstra published his algorithm in 19594. It grows a set of vertices whose shortest distance is settled, always extending to the nearest unsettled vertex, and it works when edge lengths are nonnegative. The idea—repeatedly "relaxing" an edge by checking whether going through one vertex gives a cheaper route to another—became the template for a whole family of label-setting and label-correcting methods. Independently, in the mid-1950s, Lester Ford and Richard Bellman developed what is now called the Bellman–Ford algorithm, which tolerates negative edge lengths and can detect negative cycles.

The same decade produced matching theory and network flow. In 1955 Harold Kuhn described an algorithm for finding maximum matchings in bipartite graphs—graphs whose vertices split into two sides with edges only across—crediting the Hungarian mathematicians Dénes Kőnig and Jenő Egerváry, and the method is still called the Hungarian algorithm. In 1956 Lester Ford and Delbert Fulkerson gave the first algorithm for the maximum flow problem: how much can be pushed from a source to a sink through a network of capacitated pipes. Their approach, the augmenting-path method, repeatedly finds a path with spare capacity and pushes flow along it5. The max-flow min-cut theorem—that the maximum flow equals the capacity of the tightest bottleneck separating source from sink—tied flow to cuts and became one of the most reused results in the field.

Traversal, greedy methods, and the shape of hardness, 1960s–1970s

Two simple ideas from this era underpin much later work. Depth-first search, formalized in the 1960s and standard by the early 1970s (John Hopcroft and Robert Tarjan gave it a rigorous linear-time treatment in 1973), explores a graph by going as deep as possible before backtracking. It is almost embarrassingly simple, yet it yields connectivity tests, cycle detection, topological sorting of directed acyclic graphs, and the identification of strongly connected components—maximal sets of vertices each reachable from the others.

Greedy algorithms—building a solution by always taking the locally best option—found their theory in the same period. Joseph Kruskal (1956) and Robert Prim (1957) gave algorithms for the minimum spanning tree, the cheapest set of edges connecting all vertices67. In 1971 Jack Edmonds showed that greedy methods work exactly when the underlying structure is a matroid, a combinatorial abstraction of independence; this explained why spanning trees and certain scheduling problems yield to greed but most others do not.

Then came the shock. In 1971 Stephen Cook proved that satisfiability is NP-complete, and in 1972 Richard Karp showed that a list of natural combinatorial problems—including the traveling salesman problem, graph coloring, and finding a clique of a given size—are all NP-complete: no known efficient algorithm solves them, and solving any one efficiently would solve them all. This reframed graph algorithms. Some problems, like shortest paths and spanning trees, are tractable; others, like the salesman's tour, appear not to be. The field split into those who sought better exact methods and those who asked what could be done when exactness is out of reach.

Coping with hardness: approximation, parameterization, and randomization, 1970s–1990s

Approximation algorithms accept a near-optimal answer with a proven guarantee. The vertex cover problem—choose the fewest vertices touching every edge—admits a simple 2-approximation by taking both endpoints of any uncovered edge. In the 1990s the field matured: the primal-dual method, borrowed from linear programming, and LP rounding gave systematic ways to derive guarantees, and semidefinite programming produced the celebrated 0.878-approximation for maximum cut by Michel Goemans and David Williamson in 1995. Hardness of approximation, developed from the early 1990s, showed that some problems cannot be approximated well unless major complexity conjectures fail.

Parameterized complexity, developed by Rod Downey and Michael Fellows from the late 1980s, asked a different question: if a problem is hard in general, is it tractable when some parameter—say, the size of the solution sought—is small? The vertex cover problem, NP-hard overall, is solvable in time exponential only in the cover size, which is often tiny in practice8. This "fixed-parameter tractability" gave a fine-grained map of where hardness actually lives.

Randomized graph algorithms use coin flips to gain speed or simplicity. Randomized contraction, developed by David Karger in the early 1990s, finds a minimum cut by repeatedly contracting random edges, with a proof that success is likely after enough repetitions9. Randomized rounding turned linear-programming solutions into integral ones probabilistically. These methods traded certainty for efficiency and became standard tools.

Spectral methods, ranking, and the modern data deluge, 1990s–present

Spectral and algebraic methods treat a graph through its matrix—the adjacency or Laplacian matrix—and use eigenvalues and eigenvectors to reveal structure1011. The connection runs back to Kirchhoff and to Marc Kac's 1966 question "Can one hear the shape of a drum?", but it became an algorithmic engine in the 1990s: spectral partitioning splits graphs into well-separated clusters, and the Laplacian's spectrum measures connectivity. These ideas now underlie clustering, graph drawing, and the analysis of large networks.

Link analysis and network ranking arrived with the web. In the late 1990s Sergey Brin and Lawrence Page's PageRank ranked web pages by a random-surfer model—a page is important if important pages link to it—computed as the principal eigenvector of a modified adjacency matrix. Around the same time Jon Kleinberg's HITS algorithm distinguished "hubs" and "authorities." Both are spectral ideas in disguise, and both made graph algorithms central to the infrastructure of the internet.

The scale of modern data forced new models. Dynamic graph algorithms maintain answers as edges are inserted or deleted, rather than recomputing from scratch12. Streaming algorithms process edges one at a time in a single pass with limited memory, estimating quantities like connectivity or triangle counts. Together these respond to graphs—social networks, road maps, transaction logs—too large to store or revisit.

Where the field stands

Today graph algorithms is a mature but restless field. Shortest paths, spanning trees, flows, and matchings are solved by algorithms whose efficiency is well understood, and these classical methods remain in daily use inside routing systems, schedulers, and compilers. Approximation, parameterization, and randomization form the standard toolkit for the problems that resist exact solution, and spectral and algebraic techniques connect the field to numerical linear algebra and machine learning. The open questions are sharp: whether the apparent hardness of NP-complete graph problems can be circumvented or is fundamental; how to compute on graphs that arrive too fast to store; how to maintain answers under constant change; and how far the algebraic view can be pushed. Each descends directly from a puzzle about bridges, a route-finding procedure from 1959, or a proof from 1972 that some questions may simply be too hard to answer quickly.

References

  1. Graph theory (introduction, History), Wikipedia
  2. Graph (discrete mathematics), Wikipedia
  3. Eulerian path, Wikipedia
  4. Dijkstra's algorithm (introduction, History), Wikipedia
  5. Ford–Fulkerson algorithm, Wikipedia
  6. Kruskal's algorithm, Wikipedia
  7. Prim's algorithm, Wikipedia
  8. Parameterized complexity (FPT), Wikipedia
  9. Karger's algorithm, Wikipedia
  10. Spectral graph theory, Wikipedia
  11. Laplacian matrix, Wikipedia
  12. Dynamic connectivity, Wikipedia

The frameworks of Graph Algorithms

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1931-Present

    Matching Theory

    How do we pair up vertices as much as possible?

    Fly to its tower in Nousfarer

  2. 1955-Present

    Classical Combinatorial Optimization

    How do we find the cheapest or best combinatorial structure?

    Fly to its tower in Nousfarer

  3. 1955-Present

    Network Flow and Cut Theory

    How much can flow through a network, and where is the bottleneck?

    Fly to its tower in Nousfarer

  4. 1956-Present

    Greedy algorithms and matroid theory

    When does taking the locally best step give the best overall result?

    Fly to its tower in Nousfarer

  5. 1956-Present
  6. 1960-Present

    Graph traversal and connectivity

    What is reachable from where, and how is a network connected?

    Fly to its tower in Nousfarer

  7. 1971-Present
  8. 1975-Present

    Approximation algorithm

    How close to optimal can we get when exactness is out of reach?

    Fly to its tower in Nousfarer

  9. 1988-Present

    Parameterized complexity

    When does a hard problem become easy if some part is small?

    Fly to its tower in Nousfarer

  10. 1990-Present

    Randomized graph algorithms

    Can coin flips make an algorithm faster or simpler?

    Fly to its tower in Nousfarer

  11. 1990-Present

    Spectral graph theory

    What do eigenvalues and eigenvectors reveal about a network?

    Fly to its tower in Nousfarer

  12. 1995-Present

    Dynamic and streaming graph algorithms

    How do we keep answers current as a graph keeps changing?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Matching TheoryClassical Combinatorial OptimizationNetwork Flow and Cut TheoryGreedy algorithms and matroid theoryShortest-Path Label-Setting and Relax…Graph traversal and connectivityNP-completeness and computational int…Approximation algorithmParameterized complexityRandomized graph algorithmsSpectral graph theoryDynamic and streaming graph algorithmsLink analysis and network ranking

Beyond the field

Where Graph Algorithms's ideas came from in other fields, and what they led to there: the strongest 12 of 51 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Graph Algorithms is a planet in Nousfarer

Its city has a tower for each of these 13 frameworks. Land, walk in, and climb one concept at a time.

Land on Graph Algorithms

Related fields

Fields its ideas are linked to

More in Algorithms

See where Graph Algorithms sits on the Map of Human Knowledge