A Separator for Minor-Free Graphs Beyond the Flow Barrier
Hung Le · 2026
Read A Separator for Minor-Free Graphs Beyond the Flow Barrier by Hung Le (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-05494.txt.
Introduction
Hung Le settles a question about cutting graphs into balanced pieces. A separator is a small set whose removal splits a graph evenly, and for graphs avoiding a fixed minor, smaller separators mean faster algorithms. In 1990, Alon, Seymour, and Thomas gave the first good bound and conjectured a tighter one.
Le first matches the best flow-based bound with a simpler combination of known tools. Then he breaks the barrier that flow methods seemed to impose, shrinking the separator further. His key move adds a low-diameter decomposition to the old framework, cutting a key cost by a large factor.
Catalog record
| CREATOR | Hung Le |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.05494
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Separator for Minor-Free Graphs Beyond the Flow Barrier Hung Le Abstract In 1990, Alon, Seymour, and Thomas [ 1 ] gave the first balanced separator of size O ( h 3 / 2 n ) O(h^{3/2}\sqrt{n}) for any K h K_{h} -minor-free graph, which has had numerous algorithmic applications. They conjectured that the size of the balanced separator can be reduced to O ( h n ) O(h\sqrt{n}) , which is asymptotically tight. Two decades later, Kawarabayashi and Reed [ 8 ] constructed a separator of size O ( h n + f ( h ) ) O(h\sqrt{n}+f(h)) based on the graph minor structure theorem, where f ( h ) f(h) is an extremely fast-growing function typically seen in the structure theorem; their separator’s size is only better than that of Alon, Seymour, and Thomas for a very small value of h h . Recently, Spalding-Jamieson [ 20 ] constructed a separator of size O ( h log h log log h n ) O(h\log h\log\log h\sqrt{n}) ; the technique is rooted in concurrent flow-sparsest cut duality. Spalding-Jamieson’s separator comes very close to O ( h log h n ) O(h\log h\sqrt{n}) , which is the barrier for techniques based on the flow-cut duality. In this work, we first observe that plugging in the recent padded decomposition by Filtser and Conroy [ 4 ] into the flow-based algorithm of Korhonen and Lokshtanov [ 10 ] yields a balanced separator of size O ( h log h n ) O(h\log h\sqrt{n}) , matching the flow barrier. This result motivates the question of whether the flow barrier can be broken, which would be a stepping stone toward resolving the conjecture of Alon, Seymour, and Thomas [ 1 ] . The main result of our work is a positive answer to this question: we construct a balanced separator of size O ( h log h n ) O(h\sqrt{\log h}\sqrt{n}) . Surprisingly, perhaps, our algorithm is still based on the iterative framework of Alon, Seymour, and Thomas [ 1 ] , although a key component of their algorithm within this framework, called the neighborhood bound, was shown to be tight [ 12 ] . Our new idea is to incorporate a low-diameter decomposition into the framework, which allows us to reduce the neighborhood bound by a factor of h h , at the cost of a factor log h \log h . As a result, we improve the h \sqrt{h} factor to log h \sqrt{\log h} in the final separator’s size. Erasing log h \sqrt{\log h} entirely seems to require substantially new ideas. 1 Introduction The two most powerful structural results in minor-free graphs that have numerous algorithmic applications are the graph minor structure theorem [ 19 ] and the separator theorem [ 1 ] . The structure theorem says roughly that one can decompose a K_{h} -minor-free graph into a tree structure of pieces which are simple, with the simplicity is parameterized by a function f(h) , an extremely fast-growing function [ 19 ] . A recent breakthrough [ 7 ] reduces f(h) to a polynomial function of h , though the proof remains very complicated, spanning hundreds of pages, and the degree of the polynomial remains impractically large. Specifically, f(h)=O(h^{2300}) . Determining the exact polynomial dependency of f(h) on h (which could well be very practical) and/or giving a simpler construction remains a long-standing open problem [ 15 ] . On the other hand, separator theorems often have very small dependence on h , and their proofs are often much simpler. A balanced separator of a graph G=(V,E) is a subset X\subseteq V such that the largest connected component of G\setminus X has size at most 2n/3 . Alon, Seymour, and Thomas [ 1 ] were the first to show that any K_{h} -minor-free graph admits a balanced separator of size O(h^{3/2}\sqrt{n}) , which can be found in polynomial time of O(m\sqrt{nh}) . Regarding the dependence on h of the separator size, they remarked: “We think that the expression h^{3/2}n^{1/2} […] is not the best possible, and that O(hn^{1/2}) is the correct answer, but have not been able to decide this. […] Every 3-regular expander with n vertices is a graph with no K_{h} -minor for h=cn^{1/2} , and with no separator of size dn , for appropriately chosen positive constants c and d ; and hence the estimate O(hn^{1/2}) would be the best possible.” A few years later, Plotkin, Rao, and Smith [ 16 ] constructed a balanced separator of size O(hn\sqrt{\log n}) which has an optimal dependence on h but a larger dependence on n . This separator size is suboptimal in the regime h=O(1) , which includes well-studied classes, such as planar graphs and graphs with constant genus. Nevertheless, the bound by Plotkin, Rao, and Smith is strong evidence supporting the Alon-Seymour-Thomas conjecture. Conjecture 1 (Alon-Seymour-Thomas Conjecture [ 1 ] ) For any h\geq 3 and n\geq 1 , any K_{h} -minor-free graph of n vertices has a balanced separator of size at most c\cdot h\sqrt{n} for some positive constant c . This conjecture saw very little progress for almost 20 years, until Kawarabayashi and Reed claimed a solution in a FOCS 2010 conference paper [ 8 ] . However, as recently remarked by [ 23 ] , one of the authors later clarified in a talk [ 9 ] that the precise bound is O(hn^{1/2}+f(h)) where f(h) is the function in the graph minor structure theorem. The full version of their paper remains unpublished. And it is unclear if the recent breakthrough on the structure theorem [ 7 ] can be applied to reduce f(h) to a polynomial in h . Even if it does, then f(h) remains a very large polynomial of h , which gives a vacuous bound when h=n^{1/2300} . Moreover, the construction would not be elementary, which has been regarded as the key advantage of separator theorems [ 1 , 16 , 23 ] over the structure theorem. In any case, 1 remains open in its full generality. In a different direction, Biswal, Lee, and Rao [ 2 ] studied spectral partitioning algorithms for K_{h} -minor-free graphs. Their technique gave a different algorithm for constructing a balanced separator of size O(h^{3}\sqrt{n\log h}) based on the duality between concurrent flow and (uniform) sparsest cut. While this separator bound is worse than that of Alon, Seymour, and Thomas [ 1 ] by a factor of h^{3/2}\sqrt{\log h} , their framework made an important link between padded decomposition and balanced separators via concurrent flow. As of their writing, the best padding parameter was \beta(h)=O(h^{2}) . Recently, Spalding-Jamieson [ 20 ] studied reweighted spectral graph partitioning for special classes of graphs, and noticed that using the recent padded decomposition by Conroy and Filtser [ 4 ] , which has \beta(h)=O(\log h) , the separator bound can be improved to O(h\log(h)\log\log h\sqrt{n}) (Corollary 1.6. in [ 20 ] ). We note that the proof by Spalding-Jamieson [ 20 ] via the spectral technique is somewhat complicated. Here, we