arxiv: 2605.05494 · v2 · submitted 2026-05-06 · 💻 cs.DS

Recognition: no theorem link

A Separator for Minor-Free Graphs Beyond the Flow Barrier

Hung Le

Authors on Pith no claims yet

Pith reviewed 2026-05-12 02:09 UTC · model grok-4.3

classification 💻 cs.DS

keywords balanced separatorsminor-free graphsK_h-minor-freegraph separatorslow-diameter decompositioniterative frameworkalgorithmic graph theory

0 comments

The pith

A balanced separator of size O(h sqrt(log h) sqrt(n)) exists for every K_h-minor-free graph.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to build a smaller balanced separator in graphs that exclude a fixed minor by modifying an older iterative construction rather than using flow techniques. This produces a separator whose size is O(h sqrt(log h) sqrt(n)), which is asymptotically better than the previous O(h log h sqrt(n)) bound. A reader would care because balanced separators are a basic tool for dividing graphs into pieces and then solving problems recursively; any improvement directly speeds up many algorithms on minor-free graphs and narrows the gap to the long-standing conjecture of an O(h sqrt(n)) separator.

Core claim

By inserting a low-diameter decomposition into the Alon-Seymour-Thomas iterative framework, the neighborhood bound can be reduced by a factor of h while paying only a logarithmic factor in h, which improves the overall separator size from O(h^{3/2} sqrt(n)) to O(h sqrt(log h) sqrt(n)).

What carries the argument

low-diameter decomposition inserted into the Alon-Seymour-Thomas iterative separator framework to shrink the neighborhood bound by a factor of h

If this is right

Many divide-and-conquer algorithms on K_h-minor-free graphs obtain improved running times from the smaller separator.
The result supplies a concrete stepping-stone toward the O(h sqrt(n)) bound conjectured by Alon, Seymour, and Thomas.
Flow-cut duality is no longer the only viable route to separator theorems in minor-free graphs.
The same decomposition idea may be reusable inside other iterative separator constructions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Decomposition-based methods can surpass the limits previously reached by pure flow techniques.
The same framework tweak might produce better separators in other minor-closed graph families.
Repeated applications could eventually remove the remaining logarithmic factors and reach the conjectured optimum.
The construction suggests that neighborhood-size arguments in iterative schemes are more flexible than earlier tightness results indicated.

Load-bearing premise

A low-diameter decomposition can be plugged into the Alon-Seymour-Thomas framework so that the neighborhood bound drops by a factor of h without new size overheads that erase the gain.

What would settle it

Any K_h-minor-free graph on n vertices whose smallest balanced separator is larger than c h sqrt(log h) sqrt(n) for a fixed constant c would show the claimed size is impossible.

Figures

Figures reproduced from arXiv: 2605.05494 by Hung Le.

**Figure 1.** Figure 1: Each Li is the i-th layer of the BFS tree rooted at v, starting from L0 = {v}. • (Step 2) If every branch set C ∈ K has a neighbor in U ∪ M+ℓ , then we can add a new branch set of size O(hℓ log(h)) to K, consisting of at most h shortest paths, each of length at most ∆+(log h+1)ℓ+ℓ = O(ℓ log h). • (Step 3) If |B| ≤ n/h, which means at least one layer among ℓ layers in M+ℓ∩B has size at most n/(ℓh). Then we … view at source ↗

**Figure 2.** Figure 2: Each Li is the i-th layer of the BFS tree rooted at v, starting from L0 = {v}. Here ∆ = ℓ log and ℓ ∗ = (log h + 1)ℓ. Step 1: Low-diameter Decomposition. Let ∆ = ℓ log(h). We apply the LDD in Lemma 1 to H with parameter ∆ to find a subset S ⊆ V(H) of size |S| = O(log(h)n/∆) = O(n/ℓ) such that every connected component of H \ S has a weak diameter at most ∆. If every connected component has size at most 2n/… view at source ↗

read the original abstract

In 1990, Alon, Seymour, and Thomas gave the first balanced separator of size $O(h^{3/2}\sqrt{n})$ for any $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\sqrt{n})$, which is asymptotically tight. Two decades later, Kawarabayashi and Reed constructed a separator of size $O(h\sqrt{n} + f(h))$ based on the graph minor structure theorem, where $f(h)$ is an extremely fast-growing function typically seen in the structure theorem. Recently, Spalding-Jamieson constructed a separator of size $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 \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 into the flow-based algorithm of Korhonen and Lokshtanov yields a balanced separator of size $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. The main result of our work is a positive answer to this question: we construct a balanced separator of size $O(h \sqrt{\log h} \sqrt{n})$. Surprisingly, perhaps, our algorithm is still based on the iterative framework of Alon, Seymour, and Thomas, although a key component of their algorithm within this framework, called the neighborhood bound, was shown to be tight. 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$, at the cost of a factor $\log h$. As a result, we improve the $\sqrt{h}$ factor to $\sqrt{\log h}$ in the final separator's size.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper improves the separator bound for K_h-minor-free graphs to O(h √(log h) √n) by inserting a low-diameter decomposition into the Alon-Seymour-Thomas iterative framework.

read the letter

The main point is a concrete improvement on balanced separators in K_h-minor-free graphs. The new bound O(h √(log h) √n) beats the flow-cut barrier that limited recent work and moves closer to the Alon-Seymour-Thomas conjecture of O(h √n). The authors first note that Filtser-Conroy padded decompositions inside the Korhonen-Lokshtanov flow method already reach O(h log h √n). They then return to the older AST iterative approach, which had a tight neighborhood bound, and show how to add the low-diameter decomposition to shrink that bound by roughly h while paying only a log h factor overall. This is new because it avoids both the huge functions from the graph minor structure theorem and the flow duality limit. The construction is algorithmic and explicit, which is useful for anyone running divide-and-conquer on these graphs. The soft spot is the integration step itself. The original neighborhood bound is known to be tight, so the gain depends on the decomposition strictly limiting which vertices contribute to the separator at each iteration without extra overhead from recursion or re-balancing. The abstract sketches the idea but does not give the full accounting of iteration count, component sizes, and diameter control, so that part needs careful checking in the proof. Readers working on separators, minor-free graphs, or approximation algorithms that use balanced cuts will get value from the improved exponent. The paper is coherent on its own terms and shows honest engagement with the prior literature. I would send it to peer review.

Referee Report

2 major / 2 minor

Summary. The manuscript claims an O(h √(log h) √n)-size balanced separator for K_h-minor-free graphs. It first obtains O(h log h √n) by substituting the Filtser-Conroy padded decomposition into the Korhonen-Lokshtanov flow-based algorithm, then improves this by inserting a low-diameter decomposition into the Alon-Seymour-Thomas iterative framework to shrink the neighborhood bound by a factor of h at the cost of only a log h factor.

Significance. If correct, the result breaks the flow-cut duality barrier for separators in minor-free graphs and constitutes measurable progress toward the Alon-Seymour-Thomas conjecture of an O(h √n) bound. The construction is explicit and algorithmic, relying on known decomposition primitives and the classical iterative framework rather than the graph-minor structure theorem; this is a clear strength.

major comments (2)

[Abstract (main result paragraph) and the description of the iterative construction] The central improvement rests on the claim that a low-diameter decomposition can be inserted into the AST iterative framework so that the neighborhood bound shrinks by a factor of h while incurring only a log h overhead overall. Because the unmodified neighborhood bound is known to be tight, the manuscript must supply a precise accounting (in the recursive construction) showing that the diameter/padding properties strictly limit the vertices whose neighborhoods contribute to the separator at each step, that re-application across recursion levels does not accumulate extra log h factors, and that balance maintenance does not cancel the gain. The abstract provides no such accounting.
[Section describing the flow-based preliminary result] The preliminary O(h log h √n) bound obtained by combining the Filtser-Conroy decomposition with the Korhonen-Lokshtanov flow algorithm is presented as motivation. The manuscript should clarify whether this combination is a direct, parameter-free substitution or requires additional error terms, and whether any of its analysis is reused in the main AST-based argument.

minor comments (2)

[Notation and abstract] Notation for the minor parameter h and the separator size should be uniform across the abstract, introduction, and technical sections.
[Introduction] The tightness statement for the unmodified AST neighborhood bound should be accompanied by a precise citation to the relevant prior work.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation of our results and for the constructive comments that highlight opportunities to improve clarity. We address each major comment below.

read point-by-point responses

Referee: [Abstract (main result paragraph) and the description of the iterative construction] The central improvement rests on the claim that a low-diameter decomposition can be inserted into the AST iterative framework so that the neighborhood bound shrinks by a factor of h while incurring only a log h overhead overall. Because the unmodified neighborhood bound is known to be tight, the manuscript must supply a precise accounting (in the recursive construction) showing that the diameter/padding properties strictly limit the vertices whose neighborhoods contribute to the separator at each step, that re-application across recursion levels does not accumulate extra log h factors, and that balance maintenance does not cancel the gain. The abstract provides no such accounting.

Authors: The full recursive accounting appears in Section 3 of the manuscript. The low-diameter decomposition (with its padding radius) restricts neighborhood contributions to vertices inside the diameter bound, yielding the factor-h reduction in the per-step bound. The single log h overhead is incurred only from the decomposition's level structure; because each recursive call reapplies the decomposition independently to a balanced subgraph whose size decreases geometrically, the overhead does not compound across levels. Balance is inherited directly from the original AST selection rule. While the body contains this analysis, the abstract does not summarize it; we will revise the abstract to include a concise outline of these properties. revision: yes
Referee: [Section describing the flow-based preliminary result] The preliminary O(h log h √n) bound obtained by combining the Filtser-Conroy decomposition with the Korhonen-Lokshtanov flow algorithm is presented as motivation. The manuscript should clarify whether this combination is a direct, parameter-free substitution or requires additional error terms, and whether any of its analysis is reused in the main AST-based argument.

Authors: The substitution is direct and parameter-free: the Filtser-Conroy padded decomposition replaces the prior decomposition inside the Korhonen-Lokshtanov flow algorithm, introducing no extra error terms. Its analysis is not reused in the main AST-based construction, which relies on a separate iterative framework augmented by low-diameter decompositions; the preliminary bound serves solely as motivation. We will insert an explicit clarifying sentence in the relevant section. revision: yes

Circularity Check

0 steps flagged

No significant circularity; explicit algorithmic construction from independent priors

full rationale

The derivation is an explicit algorithmic procedure: it invokes the Filtser-Conroy padded decomposition and the Korhonen-Lokshtanov flow algorithm to reach the flow barrier, then inserts the same decomposition into the Alon-Seymour-Thomas iterative framework to shrink the neighborhood bound by a factor of h at the cost of log h. No quantity is defined in terms of the target separator size, no parameter is fitted to the claimed O(h √(log h) √n) bound, and the central improvement is not justified solely by self-citation. The cited results (AST 1990, Filtser-Conroy, Korhonen-Lokshtanov) are external and the new integration step is presented as a constructive modification rather than a tautology or renaming. The paper therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on standard properties of K_h-minor-free graphs that admit low-diameter decompositions and on the correctness of the 1990 iterative framework; no new free parameters or invented entities are introduced.

axioms (1)

domain assumption K_h-minor-free graphs admit low-diameter decompositions whose clusters have controlled neighborhood sizes
Invoked to reduce the neighborhood bound inside the Alon-Seymour-Thomas iteration

pith-pipeline@v0.9.0 · 5689 in / 1242 out tokens · 41260 ms · 2026-05-12T02:09:03.625794+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

[1]

A separator theorem for nonplanar graphs.Journal of the American Mathematical Society, 3(4):801–808, 1990

Noga Alon, Paul Seymour, and Robin Thomas. A separator theorem for nonplanar graphs.Journal of the American Mathematical Society, 3(4):801–808, 1990. Announced at STOC ’90

work page 1990
[2]

Eigenvalue bounds, spectral partitioning, and metrical deformations via flows.Journal of the ACM (JACM), 57(3):1–23, 2010

Punyashloka Biswal, James R Lee, and Satish Rao. Eigenvalue bounds, spectral partitioning, and metrical deformations via flows.Journal of the ACM (JACM), 57(3):1–23, 2010. 13

work page 2010
[3]

Bollobás, P .A

B. Bollobás, P .A. Catlin, and P . Erdös. Hadwiger’s conjecture is true for almost every graph.European Journal of Combinatorics, 1(3):195–199, 1980

work page 1980
[4]

How to protect yourself from threatening skeletons: Optimal padded decompositions for minor-free graphs

Jonathan Conroy and Arnold Filtser. How to protect yourself from threatening skeletons: Optimal padded decompositions for minor-free graphs. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, pages 2281–2292, 2025

work page 2025
[5]

Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee. Improved approximation algorithms for minimum-weight vertex separators. InProceedings of the 37th Annual ACM Symposium on Theory of Computing, STOC ’05, page 563–572, 2005

work page 2005
[6]

The order of the largest complete minor in a random graph.Random Structures & Algorithms, 33(2):127–141, May 2008

Nikolaos Fountoulakis, Daniela Kühn, and Deryk Osthus. The order of the largest complete minor in a random graph.Random Structures & Algorithms, 33(2):127–141, May 2008

work page 2008
[7]

Seweryn, and Sebastian Wiederrecht

Maximilian Gorsky , Michał T . Seweryn, and Sebastian Wiederrecht. Polynomial bounds for the graph minor structure theorem. InProceedings of te 66th Annual Symposium on Foundations of Computer Science, FOCS ’023, page 1961–1978, 2025. Arxiv link:https://arxiv.org/pdf/2504.02532

work page arXiv 1961
[8]

A separator theorem in minor-closed classes

Ken-ichi Kawarabayashi and Bruce Reed. A separator theorem in minor-closed classes. InProceedings of the 51st Annual Symposium on Foundations of Computer Science, FOCS ’10, pages 153–162. IEEE, 2010

work page 2010
[9]

A separator theorem in minor-closed class of graphs, 2011

Kenichi Kawarabayashi. A separator theorem in minor-closed class of graphs, 2011. Talk at KAIST Graph Theory Day . Accessed: 2026-05-04,https://youtu.be/xTEwQ6KgBdU?si=ZFII4GZWAIC_ywfj&t=1470

work page 2011
[10]

Induced-minor-free graphs: Separator theorem, subexponential algorithms, and improved hardness of recognition

Tuukka Korhonen and Daniel Lokshtanov. Induced-minor-free graphs: Separator theorem, subexponential algorithms, and improved hardness of recognition. InProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5249–5275, 2024

work page 2024
[11]

A lower bound for the hadwiger number of a graph as a function of the average degree of its vertices.Diskret

Alexandr Kostochka. A lower bound for the hadwiger number of a graph as a function of the average degree of its vertices.Diskret. Analiz. Novosibirsk, 38:37–58, 1982

work page 1982
[12]

Bulky subgraphs of the hypercube.European Journal of Combinatorics, 21(4):503–507, May 2000

Andrei Kotlov. Bulky subgraphs of the hypercube.European Journal of Combinatorics, 21(4):503–507, May 2000

work page 2000
[13]

Separator theorems

Hung Le. Separator theorems. https://minorfree.github.io/sep-theorems/, July 2023. Accessed: 2026-05-05

work page 2023
[14]

Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.Journal of the ACM, 46(6):787–832, November 1999

Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.Journal of the ACM, 46(6):787–832, November 1999

work page 1999
[15]

Graph minor theory.Bulletin of the American Mathematical Society, 43(1):75–86, October 2005

László Lovász. Graph minor theory.Bulletin of the American Mathematical Society, 43(1):75–86, October 2005

work page 2005
[16]

Serge Plotkin, Satish Rao, and Warren D. Smith. Shallow excluded minors and improved graph decompositions. InProceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’94, pages 462–470, 1994

work page 1994
[17]

On average distortion of embedding metrics into the line and into l1

Yuri Rabinovich. On average distortion of embedding metrics into the line and into l1. InProceedings of the 35th Annual ACM Symposium on Theory of Computing, STOC ’03, page 456–462, 2003

work page 2003
[18]

Bruce Reed and David R. Wood. A linear-time algorithm to find a separator in a graph excluding a minor. ACM Transactions on Algorithms, 5(4):1–16, 2009

work page 2009
[19]

Graph minors

Neil Robertson and Paul D Seymour. Graph minors. XVI. Excluding a non-planar graph.Journal of Combina- torial Theory, Series B, 89(1):43–76, 2003

work page 2003
[20]

Reweighted spectral partitioning works: A simple algorithm for vertex separators in special graph classes, 2025

Jack Spalding-Jamieson. Reweighted spectral partitioning works: A simple algorithm for vertex separators in special graph classes, 2025. Arxiv link:https://arxiv.org/abs/2506.01228. 14

work page arXiv 2025
[21]

Separator theorems for minor-free and shallow minor-free graphs with applications

Christian Wulff-Nilsen. Separator theorems for minor-free and shallow minor-free graphs with applications. InProceedings of the 52nd Annual Symposium on Foundations of Computer Science, FOCS ’11, pages 37–46. IEEE, 2011

work page 2011
[22]

Faster separators for shallow minor-free graphs via dynamic approximate distance oracles

Christian Wulff-Nilsen. Faster separators for shallow minor-free graphs via dynamic approximate distance oracles. InInternational Colloquium on Automata, Languages, and Programming, ICALP ’14, pages 1063–1074. Springer, 2014

work page 2014
[23]

Separator theorem for minor-free graphs in linear time, 2025

Édouard Bonnet, Tuukka Korhonen, Hung Le, Jason Li, and Tomáš Masaˇrík. Separator theorem for minor-free graphs in linear time, 2025. To appear in STOC 26,https://arxiv.org/abs/2512.01587. 15

work page arXiv 2025