A graph is as hard as its largest cycle

This ladder has now measured two ways of computing shortest paths that avoid Dijkstra’s queue, and each rests on a property of the graph. The bound with a precondition showed that Dijkstra’s algorithm needs non-negative arcs and that Bellman–Ford, which does not, pays for that freedom with $V \cdot E$ work. The precondition that removes the queue showed that on a graph with no cycles at all the queue can be replaced by a topological order and a single relaxation pass, negative arcs included, for $V + E$.

Those two results sit at opposite ends of a range, and most directed graphs are in the middle: they have cycles, but not everywhere. Two passes or one measured the algorithms that find where the cycles are — the strongly connected components, the maximal groups of vertices each reachable from every other — and noted that collapsing each component to a single vertex leaves a graph with no cycles.

That suggests a method, and this page measures it. If every cycle lies inside a component, then the expensive machinery Bellman–Ford brings is only needed inside components. Between components the graph is acyclic, and the one-pass method applies. So: find the components, visit them in topological order, run Bellman–Ford inside each component on its own vertices and arcs, and then relax the arcs leaving it once. The cost should be governed by the size of the components rather than the size of the graph — a graph should be only as hard as its largest cycle.

The instance, and three methods on it #

The graph is built from $k$ strongly connected components of equal size. Inside a component the arcs form a cycle through all its vertices plus random chords, with costs from zero to five, so every component is genuinely strongly connected and its internal arcs are non-negative. Between components the arcs run only from earlier components to later ones, so the condensation is acyclic, and they cost between minus four and five — so the graph has negative arcs and Dijkstra’s algorithm is not an option. Every vertex is reachable from the source.

Three methods run on it:

• Bellman–Ford, every pass. $V-1$ passes over every arc. This is the textbook statement and the bound.
• Bellman–Ford, early exit. Passes over every arc until a pass changes no distance. This is what every implementation actually ships.
• Components first. Tarjan’s algorithm to find the components, then components in topological order, early-exit Bellman–Ford inside each, and one pass over each component’s outgoing arcs.

All three are required to return identical distances, and they do on every graph below. The counted work is the sum of this field’s four primitives — adjacency scans, relaxations, queue comparisons and vertex visits — so the component method is charged for the traversal that finds the components.

Components first against the component count #

The full Bellman–Ford line is flat at three million because it ignores structure entirely: 1,023 passes over 1,536 arcs, whatever the arcs connect. It is the bound, drawn, and it is 40 times the early exit’s cost and 80 to 200 times the component method’s.

The early exit is a different algorithm in practice and the same one in theory. It stops after the number of passes that the longest chain of improvements actually needs, which on this graph is a few dozen rather than a thousand. But its cost does not track the component structure: it wanders between 47,000 and 81,000 as the component count changes, because the number of passes it needs depends on how the improvements propagate through vertex numbers, not on how large the cycles are.

The component method’s cost falls as the components get smaller. With two components of 512 vertices it does 34,115 units; with sixty-four components of 16 it does 15,104. That is the claim in the title, measured: a thousand vertices cut into small cycles are cheap in proportion to how small the cycles are.

Where the work went #

The breakdown explains the factor of two between the component method and the early exit at eight components, and it is not where a first guess would put it.

The early exit made 29 passes over all 1,536 arcs: 44,544 scans. The component method made 119 passes in total — but each pass was over one component’s arcs, about a hundred and ninety of them, and the passes were spread across eight components at about fifteen each. Fifteen passes over an eighth of the graph, eight times, is cheaper than twenty-nine passes over the whole graph, and the difference is the saving.

Put differently, the early exit’s pass count is set by the longest chain of improvements anywhere in the graph, and it pays that count on every arc. The component method pays each component’s own chain length on that component’s arcs only. A long chain in one component does not make any other component’s passes more expensive.

The relaxations tell the same story with a different ratio. Both methods relax an arc every time they scan it and find an improvement; the component method finds proportionally fewer improvements to make, because it enters each component with its incoming distances already final. The early exit, working over the whole graph at once, repeatedly improves distances in later components that will be improved again once earlier components settle.

None of the three methods touches a priority queue, which is worth saying because it removes the usual suspect. The queue decides the class found that on a sparse graph a shortest-path search’s cost is mostly its queue; here there is no queue at all, and the whole of the difference between the methods is in how many times each arc is scanned.

Against the size of the graph #

Against $V$, with the number of components held at eight, the components grow with the graph, so the component method should grow at the rate Bellman–Ford does inside a component of $V/8$ vertices. It grows from 4,781 to 92,474 over an eightfold increase in $V$ — about a factor of nineteen — while the early exit grows by twenty-six and the full method by sixty-four.

So the gap widens with the graph, but slowly. That is expected: with a fixed number of components, each component is a constant fraction of the graph and still contains cycles of length proportional to $V$. The component method removes the cost of cycles that do not exist between components; it cannot remove the cost of cycles that do exist inside them.

A result that belonged to the numbering #

The two plates above were drawn with the vertices relabelled at random, and there is a reason that needs its own plate. The first version of this measurement did not relabel them.

On the graph as generated, component 0 held vertices 0 to 127, component 1 held 128 to 255, and so on, and every arc between components ran from a lower-numbered component to a higher one. That means index order was already a topological order of the condensation. Bellman–Ford scans vertices in index order within each pass, so on this numbering a single pass pushes improvements forward through every component in the right order, and the early exit needs four passes where the shuffled graph needs twenty-nine.

On that graph the component method is no better than the early exit — worse, with two components — because the early exit was being handed the component method’s key insight for free by the order the vertices were written down in. The measurement said the method did not work. It was a measurement of the numbering.

That is a trap worth naming, because nothing in the output reveals it. The distances were right, the counts were exact, and the curves were smooth. What was wrong was that an algorithm whose cost depends on the order it scans vertices in was being measured on inputs whose vertex order happened to be optimal for it. The order is the algorithm is this collection’s theme for exactly this, and Bellman–Ford’s early exit is a clean case of it: its pass count is not a property of the graph but of the graph and its numbering, and a generator that numbers vertices as it builds them produces a flattering order by default.

Relabelling at random removes the accident.

The accident has an exact description, and it predicts both plates. Within a pass, Bellman–Ford relaxes vertices in index order, so an improvement that travels along an arc from a lower-numbered vertex to a higher-numbered one is propagated in the same pass, while one that travels along an arc to a lower-numbered vertex waits for the next. A shortest path therefore needs one pass plus one for every arc along it that points backwards in the numbering. On a random numbering about half the arcs of any path point backwards, so the pass count is about half the number of arcs in the longest shortest path — twenty-nine passes here. On the numbering the generator produced, arcs between components never point backwards, so only the arcs inside a component can, and the pass count collapses to four.

That makes the early exit’s cost a function of three things — the graph, the source, and the numbering — and the third is the one that is never reported alongside a measurement. The component method replaces the third with a numbering it computes, which is why its plates look alike whichever order the vertices arrive in. A real graph’s vertex numbering is some mixture of both — often correlated with structure, since identifiers assigned at creation time follow how the graph grew — and the honest statement is that the early exit’s cost ranges between the two plates, while the component method’s cost does not depend on the numbering at all, because it computes the order it needs.

Smaller components on a larger graph #

On a graph four times larger the pattern repeats with a wider gap. The early exit’s cost barely responds to the component structure — it is within a factor of one and a half across a sixty-four-fold change in component size — while the component method’s cost falls by a factor of three as the components shrink from a thousand vertices to sixteen.

The component method’s floor is visible too. Even with components of sixteen vertices it does 66,288 units, because it still traverses the whole graph once to find the components and scans every arc between components once. That floor is linear in the graph, which is the acyclic method’s cost, and it is approached as the components become trivial.

The last plate holds the number of components at sixty-four and grows the graph, so each component grows from eight vertices to sixty-four. The ratio between the methods is about 4.7 at the small end and 3.0 at the large end — narrowing, because the components are getting larger and the component method’s inner Bellman–Ford is getting more expensive in proportion.

That is the title’s claim at its most literal. The component method’s cost is controlled by the size of the largest component, so it wins most when components are small relative to the graph, and its advantage shrinks when they grow. On a graph with one giant component containing most of the vertices — which many real graphs have — it would do no better than Bellman–Ford on that component plus a linear overhead.

The growth rates on these plates can be read as classes, with the usual caution. Over an eightfold increase in $V$ the every-pass method grew by 64, which is $V^2$ exactly, as it must be when $E$ is proportional to $V$. The component method grew by nineteen and the early exit by twenty-six — both between linear and quadratic, and both over too short a range to name a class with confidence. Fitting a class to measurements sets out what a ratio test over a range like this can and cannot distinguish, and three doublings is at the edge of what it can.

Which real graphs have small components #

Whether the method matters depends on the component structure real directed graphs have, and the two common shapes sit at opposite ends of the plates.

Dependency graphs are nearly acyclic. A graph of which module imports which, which task must precede which, or which cell of a spreadsheet reads which, is meant to have no cycles, and when it has them they are small — a few modules that import each other, a handful of mutually recursive functions. The component method is ideal here: almost every component is a single vertex, the method is almost exactly the acyclic one-pass relaxation, and the small cycles are handled locally without any pass over the rest of the graph. A cost that is negative on some arcs — a saving, a credit, a gain — is natural in exactly these settings, which is where a shortest-path method that tolerates negative arcs is wanted.

Graphs of links and interactions have a giant component. Directed graphs of web links and of who-follows-whom have been measured to have one strongly connected core holding a large share of all vertices, with long tails of small components leading into and out of it. On such a graph the component method pays Bellman–Ford on the core and saves only the tails, so its advantage is bounded by how much of the graph lies outside the core.

Counting on a graph established that this field reports work on stated graph families rather than on graphs in general, for exactly this reason: the answer to “which method is faster” changes with the family, and a family that has not been named is a family the answer does not apply to.

What the method is, stated as a bound #

The measured behaviour has a clean statement. Let the components have $V_i$ vertices and $E_i$ internal arcs. The component method costs $O(V + E)$ to find the components and relax the arcs between them, plus the Bellman–Ford cost inside each component, which is at most $O(V_i \cdot E_i)$ and in practice the early exit’s pass count for that component times $E_i$. So the total is

$$O\Big(V + E + \sum_i V_i E_i\Big),$$

which is between the acyclic bound $O(V+E)$, when every component is a single vertex, and Bellman–Ford’s $O(VE)$, when the whole graph is one component. Two parameters, one bound, no order found that this field’s bounds are written in two parameters that cannot express which graphs are easy; this bound needs the whole distribution of component sizes, which is a third kind of parameter again, and two parameters are not enough either is the rung that argued such parameters are the rule rather than the exception.

What this leaves out #

The condensation is given as acyclic by construction. It always is — collapsing strongly connected components cannot leave a cycle — but a negative cycle inside a component makes shortest paths undefined, and the component method detects it exactly where Bellman–Ford does, inside the component, by a pass that still improves after $V_i - 1$ passes. The graphs here have non-negative arcs inside components, so no such cycle exists, and a graph that had one would end the computation rather than change its cost.

Only 5 of the 1,024 vertices end at a negative distance. The negative arcs are between components and their costs are drawn around zero, so most of their effect is cancelled by positive arcs further along. That does not change the work — Bellman–Ford’s passes are driven by improvements, not by signs — but it means these instances exercise the negative-arc machinery lightly, and a graph whose negative arcs dominated would be a separate measurement of the same methods.

Tarjan’s algorithm is counted like any other traversal. Two passes or one found that the choice between Tarjan’s and Kosaraju’s component algorithms costs about a factor of three in traversal work; that factor applies to the component method’s floor and not to its inner passes, and on these graphs it would move the component method’s cost by a few thousand units.

Where this ladder goes next: the potential that makes Dijkstra safe #

The component method made negative arcs cheap by removing the cycles the expensive algorithm was paying for. There is a second way to make them cheap, and it removes the negativity instead.

Run Bellman–Ford once from a new vertex joined to every other vertex by an arc of cost zero. The distances it computes, $\pi(v)$, have the property that $w(u,v) + \pi(u) - \pi(v) \ge 0$ for every arc. Replace every arc’s cost by that quantity. Every path’s cost changes by a constant that depends only on its endpoints, so shortest paths do not move — and every arc is now non-negative, so Dijkstra’s algorithm applies. That is Johnson’s method, and it pays one Bellman–Ford to buy any number of Dijkstra searches.

The rung that follows is that reweighting, and it turns out to be the same object as something this ladder is about to measure in a different guise: A* with a consistent estimate is Dijkstra’s algorithm on exactly this kind of reweighted graph, with the potential supplied by the caller rather than computed. Measured together, the two show when a potential is worth computing — once per graph, against once per query — and what happens to the guarantee when a supplied potential is not quite a potential.