The planar separator theorem by Lipton and Tarjan [FOCS '77, SIAM Journal on Applied Mathematics '79] states that any planar graph with $n$ vertices has a balanced separator of size $O(\sqrt{n})$ that can be found in linear time. This landmark result kicked off decades of research on designing linear or nearly linear-time algorithms on planar graphs. In an attempt to generalize Lipton-Tarjan's theorem to nonplanar graphs, Alon, Seymour, and Thomas [STOC '90, Journal of the AMS '90] showed that any minor-free graph admits a balanced separator of size $O(\sqrt{n})$ that can be found in $O(n^{3/2})$ time. The superlinear running time in their separator theorem is a key bottleneck for generalizing algorithmic results from planar to minor-free graphs. Despite extensive research for more than two decades, finding a balanced separator of size $O(\sqrt{n})$ in (linear) $O(n)$ time for minor-free graphs remains a major open problem. Known algorithms either give a separator of size much larger than $O(\sqrt{n})$ or have superlinear running time, or both. In this paper, we answer the open problem affirmatively. Our algorithm is very simple: it runs a vertex-weighted variant of breadth-first search (BFS) a constant number of times on the input graph. Our key technical contribution is a weighting scheme on the vertices to guide the search for a balanced separator, offering a new connection between the size of a balanced separator and the existence of a clique-minor model. We believe that our weighting scheme may be of independent interest.

翻译：Lipton与Tarjan的平面图分离器定理[FOCS '77, SIAM Journal on Applied Mathematics '79]指出，任何具有$n$个顶点的平面图都存在一个规模为$O(\sqrt{n})$的平衡分离器，且可在线性时间内找到。这一里程碑式成果开启了数十年来关于平面图线性或近线性时间算法设计的研究。为将Lipton-Tarjan定理推广至非平面图，Alon、Seymour与Thomas[STOC '90, Journal of the AMS '90]证明了任何无小图均存在规模为$O(\sqrt{n})$的平衡分离器，且可在$O(n^{3/2})$时间内找到。其分离器定理中的超线性运行时间是算法结果从平面图推广至无小图的关键瓶颈。尽管经过二十余年的广泛研究，为无小图在（线性）$O(n)$时间内找到规模为$O(\sqrt{n})$的平衡分离器仍是一个重大开放问题。现有算法要么给出远大于$O(\sqrt{n})$规模的分离器，要么具有超线性运行时间，或两者兼有。本文肯定地回答了这一开放问题。我们的算法极为简洁：在输入图上运行常数次顶点加权变种的广度优先搜索（BFS）。我们的核心技术贡献在于提出了一种顶点加权方案，以引导平衡分离器的搜索，为平衡分离器规模与团小图模型存在性之间建立了新的联系。我们相信该加权方案可能具有独立的研究价值。