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.

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).