The budget cannot finish the tree

Long loops pay before the factor starts priced the trade a network’s spanning tree makes. A resistor network’s flow can be solved on its loops: every spanning tree gives a basis for the null space of the network’s incidence matrix, one loop per arc not on the tree, and the loop equations $Z^{\mathsf T}HZ$ are the reduced system. The tree the resistances choose found that the tree of least total resistance makes those equations well conditioned, by keeping every heavy arc off the tree so that each loop closes through lighter ones; spread resistances make the loops easy found the conditioning improving as the resistances spread. The cost is in the loops’ length. Following the light arcs wherever they wander, the least tree’s loops run to forty arcs where a breadth-first tree’s run to twelve, and a direct solver pays for that: the loop matrix is denser, and its Cholesky factor under minimum degree costs up to twice the breadth-first tree’s work.

The essay then tried a middle tree — Kruskal on resistances rounded to bands of $\beta$ decades, so that coarse bands let breadth-first order decide within them — and found none in the middle: any band narrow enough to keep the conditioning paid nearly all the extra work. It proposed attacking the length directly instead. “A tree built by Kruskal on exact resistances but refusing any arc whose fundamental loop would exceed a stated length, falling back to the next arc, attacks the cost directly. The prediction with a sign is that on the 10 × 10 grid at four decades a budget of twice the breadth-first tree’s longest loop, 24 arcs, keeps the median conditioning within twice the least tree’s and cuts at least a third of its extra work — that a length budget is a middle tree where a resistance band is not.”

The first half holds and the second does not, and the way the second fails is built into the attempt: a greedy order that refuses arcs has to take them back before it can call the result a tree, and the arcs it takes back are the expensive ones.

A greedy budget, and what it has to do at the end #

Kruskal’s algorithm takes the arcs in order of resistance, lightest first, and adds each one that joins two parts of the tree not yet connected. The budget adds one check. When an arc would join two parts, every grid arc already running between those two parts will become an off-tree arc whose loop is the tree path between its ends plus itself — and that path is fixed the moment the parts are joined, because a tree path never changes once it exists. If any of those loops would exceed the budget, the arc is refused and set aside, and the next arc in order is tried.

At the end something has to be done with the parts the budget would not join. A spanning tree must span: the network has a hundred nodes and the tree needs ninety-nine arcs. So the set-aside arcs are added, in order, wherever they still join two parts. Those are the “fall back to the next arc” the prediction described, exhausted.

The budgets measured are 8, 12, 16, 24 and 32 arcs, on the earlier essay’s five draws of the 10 by 10 network with resistances spread log-uniformly over four decades. The breadth-first tree’s longest loop is 12 arcs at the median, as the prediction assumed, and the least tree’s is 40.

The budget keeps the conditioning and saves nothing #

At the predicted budget of 24 arcs the median conditioning is 1.04 times the least tree’s, comfortably inside the factor of two. The median share of the least tree’s extra work is 1.00. The tree costs exactly what the least tree costs. At 32 arcs the same: 1.00 and 1.00. Neither budget binds enough to matter — on three draws in five the tree they build is the least tree with at most one arc changed.

The budgets that do bind are worse on both counts. At 16 arcs the conditioning is 2.1 times the least tree’s at the median and the work share 1.31 — more work than the least tree, not less. At 12 arcs, 3.7 and 1.55. At 8, 1.85 at the median with one draw at 57 times, and a share of 1.11. Not one budget from 8 to 32 has a median share below one. The resistance bands, drawn beside them, at least move along a trade — narrow bands keep the conditioning and pay the work, wide bands save the work and lose the conditioning — even if nothing lands in the middle. The budgets do not trade at all: they sit at the least tree’s work or above it.

Why: the parts the budget will not join #

The tree on the dial shows the mechanism. At a budget of 16, Kruskal grows parts of the tree along the light arcs as usual until two large parts meet — and every arc that could join them would close some loop across the seam longer than 16, because each part has grown long and winding. All such arcs are refused. When the order runs out the parts are still separate, and one of the refused arcs has to be added to finish the tree. It closes loops across the whole seam at once, and the longest is 42 arcs: longer than the least tree’s own. Nineteen of the eighty-one loops exceed the budget the tree was built under.

Across the five draws every budget from 8 to 16 needs set-aside arcs on every draw — two or three at a budget of 8, one or two at 12 and 16 — and the budget of 24 needs one on three draws of five. Every finished tree breaks its budget, and the median longest loop stays between 36 and 42 arcs at every budget. The budget bounds the loops the greedy order chooses to make; it cannot bound the loops the tree is forced to make at the end, and those are the long ones.

A budget enforced to the end would have to give up the order. A tree whose every loop is at most 16 arcs certainly exists — the breadth-first tree’s are at most 12 — but finding one that also follows the light arcs as far as it can is no longer a greedy problem. Kruskal’s correctness for minimum spanning trees rests on an exchange argument that a length constraint breaks: a light arc refused now may be the only way to join two parts later, and by then joining them costs more than it would have.

What the binding budgets break #

The conditioning the binding budgets lose has a precise cause, and it is the property the least tree is built on. A minimum spanning tree keeps every off-tree arc the heaviest on its own loop. A budget tree breaks that wherever it refused a light arc and later had to close a loop through something heavier. Counted on every budget tree, those violations account for the loss exactly. Every tree with none — all the trees at a budget of 32 but one, and two of five at 24 — keeps the least tree’s conditioning to within a tenth. The draw that lost a factor of 57 at a budget of 8 has twenty off-tree arcs lighter than some arc on their own loop, the worst seventy times lighter; the draw that lost a factor of ten at a budget of 12 has six, the worst nine times lighter; every tree that lost a factor of five or more has a violation of more than five.

That is the tree the resistances choose read backwards. There, the least tree’s conditioning was explained by the cycle property keeping each loop’s diagonal dominated by its own heavy arc; here, breaking the property for a handful of loops lets a heavy arc sit inside a light loop, where it couples that loop strongly to every other loop through it, and the scaled loop equations lose their diagonal dominance at exactly those rows. A budget that shortens loops by breaking the property pays twice: in conditioning for the violations, and in work for the set-aside arcs that bring long loops back.

How long the loops have to be #

That leaves the question the prediction rested on: how much shorter could the least tree’s loops be, without losing what makes its loop equations well conditioned?

The conditioning comes from the cycle property. The least tree is a minimum spanning tree, so every arc off it is the heaviest arc on its own loop; each loop’s other arcs are lighter, and the loop equations, scaled to a unit diagonal, have small off-diagonal entries because each loop’s diagonal is dominated by its own heavy arc. A tree that kept that property for an off-tree arc must close the arc’s loop through arcs lighter than it — so the shortest such loop is the shortest path between the arc’s ends through lighter arcs, plus the arc itself. That length is forced. No tree that keeps the property can give the arc a shorter loop.

On the first draw 42 of the 81 loops lie exactly on the forced length. The rest are longer — some by a factor of ten — and the total is 928 arcs against a forced total of 426. So there is slack, about as much again as the forced length, and all of it is in the half of the loops that are not already tight.

The other draws agree: 33 to 42 of 81 loops at the forced length, and a total 1.76 to 2.18 times the forced total. The median loop is 1.0 to 1.5 times its own forced length; the ninetieth-percentile loop three and a half to six times.

So the least tree’s loops are not long by accident. Half of them are as short as the conditioning permits. The other half are longer than they need to be for their own arc — but the forced lengths are lower bounds for each arc separately, and no single tree can meet them all at once, because a tree that routes one heavy arc’s loop through the shortest light path may have used arcs another heavy arc’s shortest path needed. The slack is real and it is shared, and how much of it any one tree can recover is a different and harder question than any greedy order answers.

The work is the length, squared #

Everything above treats loop length as the cost, and it is worth checking that the factor’s work really follows it rather than some other property of the tree. Over every tree built in this essay and the last — six budgets and seven bands on five draws, sixty-five trees — the factor work and the total loop length have a correlation of 0.91 on logarithmic axes, and the work grows as the 2.07th power of the length. The total length runs from 558 arcs to 1,064; the work from 7,900 to 39,000.

A square is what the structure suggests. Each loop is a row of the loop matrix, and two loops share an entry wherever they share an arc, so a loop twice as long meets about twice as many others; the loop matrix’s nonzeros grow like the square of the mean length, and the factor’s fill under minimum degree follows its nonzeros. The order decides the memory found four orderings of one matrix giving factors from 1,026 to 1,739 entries, and the least fill there is that the least possible fill is a property of the graph that no ordering beats. Here the graph itself is what the tree decides, and a longer loop is a denser graph before any ordering is chosen. The fill that is not independent found structure hidden in fill that looked dense; the loop matrix has none of that to offer, because its density is the loops’ overlap.

The square also says what a better tree would be worth. Cutting the least tree’s total loop length by the third the slack allows — from twice the forced total to about one and a third times it — would cut the factor work by more than half, which is more than the prediction asked of the budget. The prize is there. It is the route to it that a greedy order does not have.

What the two failures have in common #

The banded family and the budgeted family failed for related reasons. Bands coarsen what the tree reads; a band narrow enough to keep the heavy arcs off the tree reads the resistances almost exactly and builds almost exactly the least tree. Budgets constrain what the tree builds; a budget loose enough to finish without fallback never binds, and a budget tight enough to bind cannot be finished without breaking it. In both cases the long loops come back because they are the price of the property the conditioning comes from — half of them forced by it outright.

The basis nobody chose on purpose put the general version: a null-space method has to choose a basis, every choice is correct, and the choices differ by orders of magnitude in conditioning and in cost. Orthogonal is a number is the other end of the same choice for a dense problem, where an orthonormal basis costs fill and arithmetic and buys perfect conditioning. On a network the loop basis is sparse by construction and its conditioning depends on which loops — and the loops that condition well are the long ones.

What five draws do not show #

Every network is a 10 by 10 grid at four decades. On grids with more structure — corridors of light arcs, or resistances that vary smoothly rather than independently — the light paths would be straighter, the forced lengths shorter, and a budget might bind less destructively. The budget is enforced greedily with fallback at the end; a budget enforced by search, or by a different repair such as re-rooting the parts before joining them, is not tried. The violation count explains the conditioning lost on these trees and is not shown to predict it on others: a single violation in a loop that few other loops cross would cost much less than one in a loop at the centre of the grid, and which loops a budget breaks depends on where its seams fall. And the forced length is a per-arc bound; the least total loop length any tree with the cycle property can achieve lies between the forced total and the least tree’s, and where is not measured.

Still open: the shortest tree that keeps the property, and corridors #

The least total length the property allows. Among spanning trees whose every off-tree arc is the heaviest on its own loop, there is one with the least total loop length. The prediction with a sign is that on these five draws a local search over single-arc exchanges that preserve the property reaches a total within 1.3 times the forced total on every draw, from the least tree’s 1.8 to 2.2 — and that its factor work falls by at least a third of the way to the breadth-first tree’s, because the loops it shortens are the long ones the work is in.

Resistances in corridors. The least tree winds because light arcs are scattered. The prediction is that on a network whose light arcs are drawn along a few straight corridors — resistances a decade lower on two rows and two columns — the least tree’s loops are within 1.3 times their forced length at the median and its factor work within a fifth of the breadth-first tree’s, so that the trade the budget could not make is made by the network.