- Atlas
- Computer Science
- Graph Algorithms
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
- Matching Theory 1931-Present
- Classical Combinatorial Optimization 1955-Present
- Network Flow and Cut Theory 1955-Present
- Greedy algorithms and matroid theory 1956-Present
- Shortest-Path Label-Setting and Relaxation 1956-Present
- Graph traversal and connectivity 1960-Present
- NP-completeness and computational intractability 1971-Present
- Approximation algorithm 1975-Present
- Parameterized complexity 1988-Present
- Randomized graph algorithms 1990-Present
- Spectral graph theory 1990-Present
- Dynamic and streaming graph algorithms 1995-Present
- Link analysis and network ranking 1997-Present
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
- Graph theory (introduction, History), Wikipedia
- Graph (discrete mathematics), Wikipedia
- Eulerian path, Wikipedia
- Dijkstra's algorithm (introduction, History), Wikipedia
- Ford–Fulkerson algorithm, Wikipedia
- Kruskal's algorithm, Wikipedia
- Prim's algorithm, Wikipedia
- Parameterized complexity (FPT), Wikipedia
- Karger's algorithm, Wikipedia
- Spectral graph theory, Wikipedia
- Laplacian matrix, Wikipedia
- 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.
- 1931-Present
- 1955-Present
Classical Combinatorial Optimization
How do we find the cheapest or best combinatorial structure?
- 1955-Present
Network Flow and Cut Theory
How much can flow through a network, and where is the bottleneck?
- 1956-Present
Greedy algorithms and matroid theory
When does taking the locally best step give the best overall result?
- 1956-Present
Shortest-Path Label-Setting and Relaxation
What is the cheapest route between two points?
- 1960-Present
Graph traversal and connectivity
What is reachable from where, and how is a network connected?
- 1971-Present
NP-completeness and computational intractability
Which problems can never be solved efficiently?
- 1975-Present
Approximation algorithm
How close to optimal can we get when exactness is out of reach?
- 1988-Present
Parameterized complexity
When does a hard problem become easy if some part is small?
- 1990-Present
Randomized graph algorithms
Can coin flips make an algorithm faster or simpler?
- 1990-Present
Spectral graph theory
What do eigenvalues and eigenvectors reveal about a network?
- 1995-Present
Dynamic and streaming graph algorithms
How do we keep answers current as a graph keeps changing?
- 1997-Present
Link analysis and network ranking
Which nodes in a network deserve the most importance?
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.
Approximation algorithm grew out of NP-completeness and computational intractability
Approximation algorithms arose directly as a response to NP-completeness: once exact solution was shown intractable, the field asked for provably near-optimal answers, with the 2-approximation for vertex cover as an early template.
Parameterized complexity grew out of NP-completeness and computational intractability
Parameterized complexity grew out of NP-completeness by asking whether hard problems become tractable when a parameter such as solution size is small, refining the coarse tractable/intractable split.
Carried by Rod Downey; Michael Fellows.
Classical Combinatorial Optimization influenced by Matching Theory
Kuhn's Hungarian algorithm for bipartite matching was built on the Kőnig–Egerváry theorems of matching theory, and matching became one of the core problems of classical combinatorial optimization alongside flow and spanning trees.
Carried by Harold Kuhn; Dénes Kőnig; Jenő Egerváry.
NP-completeness and computational intractability influenced by Classical Combinatorial Optimization
Karp's 1972 list of NP-complete problems was drawn directly from the canonical problems of classical combinatorial optimization, such as the traveling salesman problem and clique, showing that its natural questions were intractable.
Carried by Richard Karp.
Approximation algorithm influenced by Network Flow and Cut Theory
The primal-dual method, developed for network flow and matching in the 1950s–60s, was revived in the 1990s as a systematic engine for deriving approximation guarantees, notably for vertex cover and related covering problems.
Randomized graph algorithms influenced by Approximation algorithm
Randomized rounding turned linear-programming relaxations, the same relaxations used in approximation algorithms, into integral solutions probabilistically, linking randomization to approximation guarantees.
Link analysis and network ranking influenced by Spectral graph theory
PageRank and HITS were computed as principal eigenvectors of modified adjacency matrices, applying spectral graph theory's eigenvector methods to ranking web pages.
Carried by Sergey Brin; Lawrence Page; Jon Kleinberg.
Approximation algorithm influenced by Shortest-Path Label-Setting and Relaxation
Shortest-path relaxation techniques were carried into approximation algorithms, for example in computing near-optimal solutions to routing and Steiner-type problems via distance labels.
Dynamic and streaming graph algorithms influenced by Graph traversal and connectivity
Traversal and connectivity primitives, such as spanning-forest maintenance, were adapted to dynamic and streaming models where edges arrive or change over time.
Parameterized complexity rival of Approximation algorithm
Approximation and parameterization developed as parallel responses to intractability in the late 1980s and 1990s, competing over how best to make NP-hard graph problems practically solvable.
Carried by Rod Downey; Michael Fellows.
Dynamic and streaming graph algorithms influenced by Randomized graph algorithms
Randomized sampling and sketching methods from randomized graph algorithms were adapted to single-pass streaming and dynamic models, where randomness substitutes for stored structure.
Dynamic and streaming graph algorithms influenced by Spectral graph theory
Spectral techniques such as Laplacian-based partitioning and sparsification were carried into dynamic and streaming settings to maintain or approximate graph structure under updates.
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.
Matching Theory grew out of Graph Theory in Combinatorics
Matching theory grew directly out of graph theory: matchings are sets of independent edges, and König's and Egerváry's work on matchings in bipartite graphs in the early 1930s founded the subfield within graph theory.
Carried by Dénes Kőnig; Jenő Egerváry.
Matching Theory grew out of Graph Theory in Networks
Matching theory is a branch of graph theory, and the computer-science graph theory tradition carries the same matching algorithms and results; the subfield is defined within graph theory as such.
Carried by Dénes Kőnig.
Network Flow and Cut Theory grew out of Graph Theory in Combinatorics
Network flow theory is a branch of graph theory: flows and cuts are defined on directed graphs, and the max-flow min-cut theorem is a graph-theoretic result.
Carried by Lester Ford; Delbert Fulkerson.
Network Flow and Cut Theory grew out of Graph Theory in Networks
Network flow and cut theory is a branch of graph theory, and the computer-science graph theory tradition carries the same flow and cut algorithms and results.
Carried by Lester Ford; Delbert Fulkerson.
Network Flow and Cut Theory grew out of Algorithmic and combinatorial optimisation on graphs in Graph Theory
Network flow and cut theory is a branch of algorithmic graph optimization: Ford and Fulkerson's max-flow min-cut work built directly on the graph-theoretic optimization tradition.
Carried by Lester Ford; Delbert Fulkerson.
Greedy algorithms and matroid theory grew out of Matroid in Matroid Theory
Greedy algorithms and matroid theory is a branch of matroid theory, deriving the greedy-optimality criterion from the matroid axioms.
Carried by Jack Edmonds; Richard Rado.
Greedy algorithms and matroid theory grew out of Matroid in Combinatorics
Greedy algorithms and matroid theory is a branch of matroid theory: the optimality of greedy algorithms is proved from the matroid exchange axioms.
Carried by Jack Edmonds; Richard Rado.
Shortest-Path Label-Setting and Relaxation influenced by Dynamic Programming in Operations Research
Dynamic programming, developed by Bellman from 1952, directly produced the Bellman-Ford shortest-path relaxation algorithm and the optimal-substructure view of shortest paths.
Carried by Richard Bellman.
Graph traversal and connectivity grew out of Graph Theory in Combinatorics
Graph traversal and connectivity is a branch of graph theory: connectivity, blocks and traversal orderings are graph-theoretic notions.
Carried by Robert Tarjan.
Graph traversal and connectivity grew out of Graph Theory in Networks
Graph traversal and connectivity is a branch of graph theory, and the computer-science graph theory tradition carries the same traversal and connectivity algorithms.
Carried by Robert Tarjan.
Approximation algorithm grew out of Complexity and Approximation Theory in Mathematical Optimization
Approximation algorithms grew directly out of complexity and approximation theory: NP-hardness results motivated the search for provably near-optimal polynomial-time algorithms, and the approximation ratio framework was formulated in that setting. The framework is a branch of the approximation-theory programme.
Carried by David S. Johnson.
Parameterized complexity grew out of Computational complexity theory in Combinatorial Optimization
Parameterized complexity grew out of computational complexity theory, generalising NP-hardness by asking how hardness depends on a parameter and introducing the W-hierarchy as a refinement of NP. Downey and Fellows built directly on the classical complexity framework.
Carried by Rodney Downey; Michael Fellows.

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 AlgorithmsRelated fields
Fields its ideas are linked to
- Graph Theory 9 links
- Randomized Algorithms 5 links
- Combinatorial Optimization 4 links
- Combinatorics 4 links
- Networks 4 links
- Matroid Theory 3 links
- Algorithms 2 links
- Approximation Algorithms 2 links
- Complexity Theory 2 links
- Linear Algebra 1 link
- Distributed Algorithms 1 link
- Streaming Algorithms 1 link
More in Algorithms
- Algorithms
- Approximation Algorithms
- Computational Geometry
- Data Structures
- Distributed Algorithms
- Online Algorithms
- Parallel Algorithms
- Parameterized Algorithms
- Randomized Algorithms
- Streaming Algorithms
- String Algorithms
See where Graph Algorithms sits on the Map of Human Knowledge