Separator Theorem for Minor-Free Graphs in Linear Time

Authors:
Open Access
Publisher website
Google Scholar
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(√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(√n) that can be found in O(n3/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(√n) in (linear) O(n) time for minor-free graphs has remained a major open problem. Known algorithms either give a separator of size much larger than O(√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.
Funding Information
  • University of Warsaw (Excellence Initiative – Research University (IDUB))
  • National Science Foundation (CCF-2517033)
  • National Science Foundation (CCF-2237288)
  • French National Research Agency (ANR-21-CE48- 0014)
  • HORIZON EUROPE Marie Sklodowska-Curie Actions (101206430)
  • Villum Fonden (54451)
  • Basic Algorithms Research Copenhagen, University of Copenhagen (not available)
  • Narodowe Centrum Nauki (2021/43/D/ST6/03312)

This publication has 30 references indexed in Scilit: