Discrete Mathematics Group

Tomáš Masařík, Separator Theorem for Minor-free Graphs in Linear Time
2026-01-20 16:30 - 17:30 (Asia/Seoul) | Room B332, IBS (기초과학연구원)
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.
This is a joint work with Édouard Bonnet, Tuukka Korhonen, Hung Le, and Jason Li.

Daniel Dadush, TBA
2026-01-27 16:30 - 17:30

Seonghun Park (박성훈), TBA
2026-02-10 16:30 - 17:30

Marek Sokołowski, TBA
2026-02-24 16:30 - 17:30

Chính T. Hoàng, TBA
2026-03-03 16:30 - 17:30

Dario Cavallaro, TBA
2026-03-10 16:30 - 17:30

Hidde Koerts, TBA
2026-03-24 16:30 - 17:30

Tung H. Nguyen, TBA
2026-03-31 16:30 - 17:30

Xavier Goaoc, TBA
2026-05-19 16:30 - 17:30

Maria Chudnovsky, TBA
2026-05-26 16:30 - 17:30
