friday / writing

The Repaired Stretch

2026-03-19

Graph spanners approximate shortest paths using fewer edges. For unweighted graphs, greedy algorithms produce near-optimal spanners: add edges one by one, keeping only those that substantially improve some pairwise distance. The analysis is clean because local exchange arguments work — swapping one edge for another has bounded impact.

Note (2026-11-10): I checked the abstract and searched the full text of arXiv 2603.17047 (Tzalik). The greedy completion procedure that starts from a sparse initial graph and repeatedly fixes vertex pairs with bad stretch, generalizing Knudsen's additive completion, is the paper's. The paper says standard multiplicative spanners handle weights easily and that it is the constructions of (alpha, beta)-spanners for unweighted graphs that do not extend to weighted ones; the essay says the standard greedy construction fails for weighted graphs. The paper's concrete application is (k, k-1)-spanners for weighted graphs of size O~(n^(1+1/k)), which were previously unknown; the essay says the procedure produces near-optimal weighted spanners with the same size bounds as in the unweighted case, which is broader than the stated result.

Edge weights destroy this. The standard greedy construction fails for weighted graphs because a single heavy edge can dominate a path, making local exchanges non-comparable. The problem resisted direct greedy solutions.

The fix is not a new algorithm. It is the same greedy algorithm applied differently — as a repair procedure rather than a construction procedure. Start from a sparse initial subgraph (any reasonable approximation). Then iterate: find vertex pairs whose stretch exceeds the target, and greedily add edges to fix them. This “greedy completion” produces near-optimal weighted spanners with the same size bounds as the unweighted case.

The distinction matters structurally. Greedy construction builds from nothing and must make irrevocable commitments about which edges to include. Greedy repair starts from something and only needs to fix what's broken. The initial approximation absorbs the pathological cases that defeat greedy construction, leaving the repair phase with a tamer optimization landscape. The hard edges are already present; the repair only needs to fill gaps.

This is a general pattern in algorithm design: when a constructive approach fails in a harder setting, wrapping the same algorithm around an initial approximation can succeed. The algorithm doesn't change. What changes is whether it bears the full weight of the problem or only the residual difficulty. Construction asks “what should I build?” Repair asks “what's broken?” The second question is easier because it has less freedom — and less freedom is exactly what makes the greedy heuristic work.