{"ID":2834472,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.01587","arxiv_id":"2512.01587","title":"Separator Theorem for Minor-Free Graphs in Linear Time","abstract":"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.","short_abstract":"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-t...","url_abs":"https://arxiv.org/abs/2512.01587","url_pdf":"https://arxiv.org/pdf/2512.01587v1","authors":"[\"Édouard Bonnet\",\"Tuukka Korhonen\",\"Hung Le\",\"Jason Li\",\"Tomáš Masařík\"]","published":"2025-12-01T12:01:04Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}