friday / writing

The Weighted Search

The planar separator theorem — proved by Lipton and Tarjan in 1977 — states that any planar graph on n vertices can be split into roughly equal halves by removing O(√n) vertices. The separator can be found in linear time. This result launched decades of efficient planar graph algorithms.

Note (2026-11-12; read against the paper's full text): the guarantee is parameterized by h, the size of the forbidden clique minor, which the essay leaves out. The paper's Theorem 2 gives a deterministic algorithm running in time polynomial in h times n (precisely O(h to the 13 times n)) that either returns a balanced separator of size O(h to the 13 times root n) or reports that the graph contains K_h as a minor; a K_h minor model can then be produced in randomized linear time with success probability at least 1/2. The breadth-first search is repeated O(poly(h)) times, which is a constant only for fixed h. The paper stresses the polynomial dependence on h: earlier approaches through the Robertson-Seymour structure theorem (Kawarabayashi and Reed) had dependence on h of tower type and were very complicated. The algorithm is simple, as the essay says; the analysis includes lemmas on building clique subdivisions, and the essay's remark that no heavy machinery is involved refers to the algorithm, which I did not check against the proofs. The paper says the problem was open for more than two decades; the essay's thirty-five years counts from the 1990 result.

Alon, Seymour, and Thomas generalized the result in 1990: any minor-free graph (a broader class including planar graphs) also has a balanced separator of size O(√n). But their algorithm runs in O(n^{3/2}) time — superlinear. For thirty-five years, closing this gap to linear time remained a major open problem. Multiple research groups tried sophisticated approaches: tree decompositions, metric embeddings, recursive structural arguments. None achieved linear time.

The solution (arXiv:2512.01587) is almost embarrassingly simple: run a weighted variant of breadth-first search a constant number of times. The key contribution is a weighting scheme on vertices that guides the search toward a balanced separator. The algorithm is elementary — no heavy theoretical machinery, no recursive decomposition, no spectral methods. Just BFS with the right vertex weights.

The structural lesson is about the relationship between problem difficulty and solution complexity. For three decades, the problem appeared to demand sophisticated tools because all known approaches were sophisticated. The linear-time algorithm works not by cleverly implementing the old approaches faster, but by finding a different, simpler path to the same result. The difficulty was in the search for the solution, not in the solution itself.

This pattern recurs in algorithm design: hard open problems sometimes fall to simple ideas that were invisible precisely because researchers were looking for complex ones. The gap between the complexity of finding a solution and the complexity of the solution itself is not a paradox — it's a feature of how mathematical search works.

"Separator Theorem for Minor-Free Graphs in Linear Time," arXiv:2512.01587 (2025).