betaFeedback

WorksComputer Science

Flow-Optimal Separators for Minor-Free and Induced-Minor-Free Graphs in Linear Time via Follow the Regularized Leader

Abstract

We give a new algorithm for finding balanced separators in minor-free and induced-minor-free graphs. A key technical idea is a new connection to online learning: we formulate a continuous, non-convex optimization problem and solve it using the Follow the Regularized Leader (FTRL) framework. Our implementation of each FTRL step yields a purely combinatorial algorithm that assigns and adjusts vertex weights over multiple rounds. For graphs with nn vertices and mm edges, we obtain the following results. (1) For HH-induced-minor-free graphs, we find a balanced separator of size O(log⁡(∣V(H)∣)∣V(H)∣+∣E(H)∣m)O(\log(|V(H)|)\sqrt{|V(H)|+|E(H)|}\sqrt{m}) in expected linear time for fixed HH. As a corollary, we find balanced separators of size O(m)O(\sqrt{m}) in string graphs in expected linear time, without requiring string representations. (2) For KhK_h-minor-free graphs, we find a balanced separator of size O(hlog⁡hn)O(h\log h\sqrt{n}) in expected linear time for fixed hh. Our algorithm unifies two long lines of work on separators in minor-free graphs, dating back to Alon, Seymour, and Thomas (1990): one optimizing separator size and the other optimizing running time. It also gives a natural interpretation of the vertex weighting scheme in a recent linear-time algorithm by Bonnet, Korhonen, Le, Li, and Masarik (2026). The separator bounds for both graph classes are flow-optimal: techniques based on flow-cut duality, including ours, cannot yield balanced separators of asymptotically smaller size.

AI Disclosure. The key high-level ideas, especially the online learning perspective, of this work were human-devised, but many of them were fleshed out and developed using LLM assistance. GPT 5.5 and GPT 5.6-Sol played useful roles in our initial developments for the presentation using FTRL, while GPT 6-Astra improved our initial running time in § 6. Other models, namely GPT 6.1-Sol and Claude Opus 5.5 have been used to proofread. The presentation and the write-up are by the human authors only. Of course, we take full responsibility for our results.

Introduction

Separator theorems are cornerstones of modern algorithmic graph theory. They facilitate divide-and-conquer algorithms on graphs, a basic technique in algorithm design. Furthermore, research in separator theorems often reveals deep and unexpected connections between different areas of math and computer science, some of which we will mention here.

Balanced separators of sparse graphs. In 1979, Lipton and Tarjan [24] constructed a balanced separator of size O(n)O(\sqrt{n}) for nn-vertex planar graphs, and showed various algorithmic applications of their result [25]. Their main technique is to use the duality of the (planar) embedding, which was also used in a subsequent (and more general) balanced separator result for surface-embedded graphs [15]. A decade later, Alon, Seymour and Thomas [4] showed how to get around using (planar or surface) embeddings and constructed a balanced separator for any KhK_h-minor-free graph of size O(h3/2n)O(h^{3/2}\sqrt{n}) in time O(mhn)O(m\sqrt{hn}). Both the (dependence on hh of the) separator size and the running time are not optimal, and have hence motivated two long lines of work that remain active to this day.

One line of work seeks to reduce the separator size to O(hn)O(h\sqrt{n}), while treating the running time as a secondary concern. Kawarabayashi and Reed [18] used Robertson-Seymour decomposition and claimed to obtain a separator of size O(hn+f(h))O(h\sqrt{n}+f(h)) for some function ff of hh. At around the same time, Biswal, Lee and Rao [6] devised a new technique for constructing balanced separators via a connection to flow-cut duality. Though their separator’s size is worse than that of Alon, Seymour and Thomas [4], subsequent results [32, 21] followed this technique, along with recent advances with padded decomposition for KhK_h-minor-free graphs by Conroy and Filtser [7], to bring the separator size to a nearly-optimal bound of O(hlog⁡hn)O(h\log h\sqrt{n}). This bound is optimal for a class of techniques relying on flow-cut duality and hence O(hlog⁡hn)O(h\log h\sqrt{n}) becomes a barrier. Recently, Le [21] broke this barrier by combining two combinatorial approaches of Alon, Seymour and Thomas [4] and Plotkin, Rao, and Smith [30]. During the final stages of our own work on this paper, this line of work was fully resolved by a superset of the authors on this paper, with AI assistance, by building on Le’s techniques [8]. However, a common theme in this entire line of work is that the running time does not improve on that of Alon, Seymour and Thomas [4]. It is possible that heavy machinery from recent dynamic graph algorithms could improve the running time, though it is unclear what new insights one could gain. Often, a lack of good running-time bounds points to our lack of structural understanding of minor-free graphs.

A second line of work focuses mostly on the regime of h=O(1)h=O(1) and aims to improve the running time to linear, often at the cost of a larger separator, both in terms of hh and nn. Reed and Wood [31] gave the first linear-time algorithm for finding a balanced separator of size Oh(n2/3)O_h(n^{2/3}). However, the dependence on nn is not optimal. And the dependence on hh in both the running time and the separator’s size is 2O(h2)2^{O(h^2)}, so even a very small value of hh, say h=log⁡(n)h=\log(n), makes both extremely large. For linear-time algorithms, this algorithm remained the state of the art until very recently; Bonnet, Korhonen, Le, Li, and Masařík [5] gave an O(poly⁡(h)⋅n)O(\operatorname{poly}(h)\cdot n) time algorithm that gives a separator of size O(poly⁡(h)⋅n)O(\operatorname{poly}(h)\cdot\sqrt{n}). Their algorithm achieves optimal dependence on nn while losing only a poly⁡(h)\operatorname{poly}(h) factor instead of an exponential factor in hh. Notably, they introduce a novel technique for constructing balanced separators: it assigns weights to the graph’s vertices, and at each step, if the algorithm fails to output a balanced separator, it adjusts the vertex weights for the next step. On the other hand, the poly⁡(h)\operatorname{poly}(h) factors in both the running time and the separator’s size are quite large: O(h13)O(h^{13}).

The two aforementioned lines of work, while productive in pursuing their own goals, diverge in their techniques and bounds: either the running time is too big (even for a fixed hh) or the separator size is too big. Achieving the best of both is left as an open problem by Bonnet et al. [5]:

Question 1. Can we construct a balanced separator of (nearly) optimal size in time O(poly⁡(h)n)O(\operatorname{poly}(h)n) for KhK_h-minor-free graphs?

At the conceptual level, Question 1 asks for a unification of the two long lines of work on separators for KhK_h-minor-free graphs over the last few decades.

Beyond minor-free graphs, Plotkin, Rao, and Smith [30] introduced the notion of shallow minor-free graphs. Roughly speaking, KhK_h is an ℓ\ell-shallow minor of GG if the minor model of KhK_h in GG can be formed from (disjoint) subgraphs of radius at most ℓ\ell. Plotkin, Rao, and Smith [30] adapted the separator theorem of Alon, Seymour, Thomas [4] to show that ℓ\ell-shallow KhK_h-minor-free graphs have balanced separators of size O(n/ℓ+ℓh2log⁡n)O(n/\ell+\ell h^2\log n). The concept of shallow minors and the Plotkin-Rao-Smith separator theorem are the basis of the (award-winning) theory of graph sparsity by Nešetřil and Ossona de Mendez [28]. One key result, among others, in this theory is a precise characterization of the classes of graphs that have strongly sublinear separators of the form O(n1−α)O(n^{1-\alpha}) for a constant α∈(0,1)\alpha\in(0,1) [28, 10, 13]: these are exactly graphs with polynomial expansion.3

Balanced separators for dense graphs. The graph classes mentioned so far are sparse: for instance, every nn-vertex KhK_h-minor-free graph has O(n)O(n) edges, where big-O hides the dependency on the class parameter. Many structural graph classes of practical interest are dense. For example, unit disk graphs, which are the intersection graphs of unit disks on the plane, can contain a large clique. This example is generalized by the class of all geometric intersection graphs in the plane, also known as string graphs. Despite their density, string graphs are K5(1)K_{5}^{(1)}-induced-minor-free [1], where K5(1)K_{5}^{(1)} is the graph obtained from K5K_5 by subdividing each edge once. Here, a graph HH is an induced minor of a graph GG if HH can be obtained from GG by a sequence of vertex deletions and edge contractions4. In a remarkable recent work, Korhonen and Loksh­tanov [16] gave a separator theorem for all induced-minor-free graphs.

Theorem 1 (Korhonen and Lokshtanov [16]). Any HH-induced-minor-free graph GG with nn vertices and mm edges has a balanced separator of size O(log⁡n∣V(H)∣+∣E(H)∣m)O(\log n\sqrt{|V(H)|+|E(H)|}\sqrt{m}) that can be constructed in polynomial time.

The m\sqrt{m} factor is best possible: KnK_n has m=Θ(n2)m=\Theta(n^2) edges, and every balanced separator of KnK_n has size Ω(n)=Ω(m)\Omega(n)=\Omega(\sqrt{m}). Their proof introduced a novel flow-based technique that also yielded the nearly optimal bound for balanced separators of minor-free graphs via the flow-based techniques mentioned above [21]. In the same paper, Korhonen and Lokshtanov [16] gave many algorithmic applications of Theorem 1; see Corollary 1.2 of [16]. In these applications, computing the balanced separator is the first step. However, though polynomial, the running time is far from linear because it requires computing a concurrent flow between Ω(n2)\Omega(n^2) pairs of vertices. A recent work [11] improved the separator size by Korhonen and Lokshtanov [16] to O(log⁡(∣V(H)∣+∣E(H)∣)∣V(H)∣+∣E(H)∣m)O(\log(|V(H)|+|E(H)|)\sqrt{|V(H)|+|E(H)|}\sqrt{m}) which is also nearly optimal. The key new idea in this work [11] is an embedding of vertex-weighted induced-minor-free graphs into the line with a small average distortion. In other words, a direct (vertex) flow-cut gap bound. Such an embedding can be used to replace a padded decomposition subroutine in the work of Korhonen and Lokshtanov [16]. The techniques of both works run in polynomial time (for a relatively large polynomial), so the overall question of fast running time for such results remains:

Question 2. Can we construct a balanced separator of (nearly) optimal size O(log⁡∣V(H)∣∣V(H)∣+∣E(H)∣m)O(\log|V(H)|\sqrt{|V(H)|+|E(H)|}\sqrt{m}) in time O(poly⁡(∣V(H)∣)(m+n))O(\operatorname{poly}(|V(H)|)(m+n))?

Our results

Our main results affirmatively answer both Question 1 and Question 2: we give linear-time algorithms for finding nearly-optimal balanced separators of both KhK_h-minor-free graphs (for a fixed hh) and HH-induced-minor-free graphs (for a fixed graph HH).

Theorem 2. Let GG be KhK_h-minor-free with nn vertices and mm edges. There is a randomized algorithm that returns a 3/4-balanced separator of size O(hlog⁡hn)O(h\log h\sqrt{n}) in expected O(h7(m+n))O(h^7(m+n)) time.

Theorem 3. Let GG be HH-induced-minor-free with nn vertices and mm edges. There is a randomized algorithm that returns a 3/4-balanced separator of size O(log⁡∣V(H)∣m(∣V(H)∣+∣E(H)∣))O(\log|V(H)|\sqrt{m(|V(H)|+|E(H)|)}) in expected O(∣V(H)∣7(m+n))O(|V(H)|^7(m+n)) time.

Our Theorem 2 not only answers Question 1 but also unifies the two lines of work on balanced separators for minor-free graphs since Alon, Seymour, and Thomas [4]. Each of our separator sizes are only log⁡h\log h away from the optimal bound, and both are optimal for techniques that rely on flow-cut duality, including ours. In particular, both are tight for 3-regular expander graphs, which are KΩ(n)K_{\Omega(\sqrt{n})}-minor-free. Table 1 compares our results with previous work.

Sparse GraphsDense Graphs
YearReferenceSeparator sizeRunning timeYearReferenceSeparator sizeRunning time
KhK_h-minor-free graphsString graphs
1990[4]O(h3/2n)O(h^{3/2}\sqrt{n})O(mhn)O(m\sqrt{hn})2010[14]O(m3/4log⁡m)O(m^{3/4}\sqrt{\log m})Not stated
1994[30]O(hnlog⁡n)O(h\sqrt{n\log n})O(hmnlog⁡n)O(hm\sqrt{n\log n})2014[27]O(mlog⁡m)O(\sqrt{m}\log m)poly⁡(n)\operatorname{poly}(n)
2008[6]O(hnlog⁡h)O(h\sqrt{n\log h})poly⁡(n)\operatorname{poly}(n)2017[22]O(mlog⁡m)O(\sqrt{m}\log m)poly⁡(n)\operatorname{poly}(n)
2009[31]O(h2(h2)n2/3)O(h^{2(h^2)}n^{2/3})2O(h2)n2^{O(h^2)}n2026[11]O(m)O(\sqrt{m})poly⁡(n)\operatorname{poly}(n)
2010[18]*O(hn+f(h))O(h\sqrt{n}+f(h))O(g(h)n1+ε)O(g(h)n^{1+\varepsilon})2026[20]O(m)O(\sqrt{m})O((m+n)1+ε)O((m+n)^{1+\varepsilon})
2011[34]O(poly⁡(h)n4/5+ε)O(\operatorname{poly}(h)n^{4/5+\varepsilon})O(poly⁡(h)n)O(\operatorname{poly}(h)n)This paperO(m)O(\sqrt{m})O(m+n)O(m+n)
2011[34]O(hnlog⁡n)O(h\sqrt{n\log n})O(poly⁡(h)n5/4+ε)O(\operatorname{poly}(h)n^{5/4+\varepsilon})HH-induced-minor-free graphs, hV=∣V(H)∣h_V=|V(H)|, hE=∣E(H)∣h_E=|E(H)|
2025[32]†O(hlog⁡hlog⁡log⁡hn)O(h\log h\log\log h\sqrt{n})poly⁡(n)\operatorname{poly}(n)2024[16]O((hV+hE)mlog⁡n)O(\sqrt{(h_V+h_E)m}\log n)poly⁡(n)\operatorname{poly}(n)
2026[5]O(h13n)O(h^{13}\sqrt{n})O(h13n)O(h^{13}n)2026[11]O((hV+hE)mlog⁡hV)O(\sqrt{(h_V+h_E)m}\log h_V)poly⁡(n)\operatorname{poly}(n)
2026[21]O(hlog⁡hn)O(h\log h\sqrt{n})poly⁡(n)\operatorname{poly}(n)This paperO((hV+hE)mlog⁡hV)O(\sqrt{(h_V+h_E)m}\log h_V)O(hV7(m+n))O(h_V^7(m+n))
2026[21]O(hnlog⁡n)O(h\sqrt{n\log n})O(hlog⁡n+h4m)O(h\sqrt{\log n}+h^4m)
2026[20]O(hlog⁡hn)O(h\log h\sqrt{n})O((m+n)1+ε)O((m+n)^{1+\varepsilon})
2026[8]O(hn)O(h\sqrt{n})Not stated
This paperO(hlog⁡hn)O(h\log h\sqrt{n})O(h7(m+n))O(h^7(m+n))

Table 1. Table 1. Balanced separator bounds for graphs with nn vertices and mm edges. Here ε>0\varepsilon>0 is an arbitrary fixed constant, and f(h)f(h), g(h)g(h) are fast-growing functions from the graph minor structure theorem. Our running times are in expectation. *Full proof unavailable (see [5, 21] for more nuanced discussions). †A corollary, distinct from the main algorithm the paper studies.

References

  1. [1][ABPT25] Pierre Aboulker, Édouard Bonnet, Timothé Picavet, and Nicolas Trotignon. Induced disjoint paths without an induced minor. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), volume 334 of Leibniz International Proceedings in Informatics (LIPIcs), pages 4:1–4:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ICALP.2025.4.DOI
  2. [2][AHR08] Jacob Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In Proceedings of the 21st Annual Conference on Learning Theory (COLT), pages 263–273, 2008.
  3. [3][AK16] Sanjeev Arora and Satya Kale. A combinatorial, primal-dual approach to semidefinite programs. J. ACM, 63(2), May 2016. doi:10.1145/2837020.DOI
  4. [4][AST90] 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. doi:10.1090/ S0894-0347-1990-1065053-0.DOI
  5. [5][BKL+26] Édouard Bonnet, Tuukka Korhonen, Hung Le, Jason Li, and Tomáš Masařík. Separator theorem for minor-free graphs in linear time. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, pages 61–71, 2026.DOI
  6. [6][BLR10] Punyashloka Biswal, James R. Lee, and Satish Rao. Eigenvalue bounds, spectral partitioning, and metrical deformations via flows. J. ACM, 57(3), 2010. Announced at FOCS ’08. doi:10.1145/1706591.1706593.DOI
  7. [7][CF25] Jonathan Conroy and Arnold Filtser. How to protect yourself from threatening skeletons: Optimal padded decompositions for minor-free graphs. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, pages 2281–2292, 2025. doi:10.1145/3717823.3718252.DOI
  8. [8][CLS26] Jonathan Conroy, Hung Le, and Jack Spalding-Jamieson. k_h-minor-free graphs have balanced separators of size o(h√n), 2026. URL: https://arxiv.org/abs/2611.00663, arXiv:2611.00663.
  9. [9]Robert B. Dial. Algorithm 360: Shortest-path forest with topological ordering [H]. Communications of the ACM, 12(11):632–633, 1969. doi:10.1145/363269.363610.DOI
  10. [10]Zdeněk Dvořák and Sergey Norin. Strongly sublinear separators and polynomial expansion. SIAM Journal on Discrete Mathematics, 30(2):1095–1101, 2016. doi:10.1137/15M1017569.DOI
  11. [11]James Davies, Paweł Rzążewski, Jack Spalding-Jamieson, and Bartosz Walczak. Revisiting separators in string graphs, region intersection graphs, and induced-minor-free graphs. In Proceedings of the 2027 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2027. URL: https://arxiv.org/abs/2610.23792.
  12. [12]Guy Even, Joseph Naor, Satish Rao, and Baruch Schieber. Fast approximate graph partitioning algorithms. SIAM Journal on Computing, 28(6):2187–2214, 1999.
  13. [13]Louis Esperet and Jean-Florent Raymond. Polynomial expansion and sublinear separators. European Journal of Combinatorics, 69:49–53, 2018. doi:10.1016/j.ejc.2017.09.003.DOI
  14. [14]Jacob Fox and János Pach. A separator theorem for string graphs and its applications. Combinatorics, Probability and Computing, 19(3):371–390, 2010.
  15. [15]John R Gilbert, Joan P Hutchinson, and Robert Endre Tarjan. A separator theorem for graphs of bounded genus. Journal of Algorithms, 5(3):391–407, 1984. doi:10.1016/0196-6774(84)90019-1.
  16. [16]Tuukka Korhonen and Daniel Loksh­tanov. Induced-minor-free graphs: Separator theorem, subexponential algorithms, and improved hardness of recognition. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’24, pages 5249–5275, 2024. doi:10.1137/1.9781611977912.188.
  17. [17]Jonathan A Kelner, James R Lee, Gregory N Price, and Shang-Hua Teng. Metric uniformization and spectral bounds for graphs. Geometric and Functional Analysis, 21(5):1117–1143, 2011.
  18. [18]Ken-ichi Kawarabayashi and Bruce Reed. A separator theorem in minor-closed classes. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science, FOCS ’10, pages 153–162. IEEE, 2010. doi:10.1109/FOCS.2010.22.DOI
  19. [19]Benedikt Kolbe and Jack Spalding-Jamieson. On eigenvalue bounds for bounded genus graphs and minor-free graphs, 2026. URL: https://arxiv.org/abs/2608.27179, arXiv:2608.27179.
  20. [20]Vladimir Kolmogorov and Jack Spalding-Jamieson. A fast approximation algorithm for the minimum balanced vertex separator in a graph, 2026. URL: https://arxiv.org/abs/2603.15782, arXiv:2603.15782.
  21. [21]Hung Le. A separator for minor-free graphs beyond the flow barrier. arXiv preprint arXiv:2605.05494, 2026.
  22. [22]James R. Lee. Separators in Region Intersection Graphs. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:8, Dagstuhl, Germany, 2017. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.1, doi:10.4230/LIPIcs.ITCS.2017.1.DOI
  23. [23]Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM (JACM), 46(6):787–832, 1999.
  24. [24]Richard J. Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177–189, 1979. doi:10.1137/0136016.DOI
  25. [25]Richard J. Lipton and Robert Endre Tarjan. Applications of a planar separator theorem. SIAM Journal on Computing, 9(3):615–627, 1980. Announced at FOCS ’77. doi:10.1137/0209046.DOI
  26. [26]Lap Chi Lau, Kam Chuen Tung, and Robert Wang. Fast algorithms for directed graph partitioning using flows and reweighted eigenvalues. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 591–624. SIAM, 2024.arxiv.org/abs/2306.09128
  27. [27]Jiří Matoušek. Near-optimal separators in string graphs. Combinatorics, Probability and Computing, 23(1):135–139, 2014.arxiv.org/abs/1302.6482
  28. [28]Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms, volume 28 of Algorithms and Combinatorics. Springer, Berlin, Heidelberg, 2012. doi:10.1007/978-3-642-27875-4.DOI
  29. [29]Francesco Orabona. Online learning: A modern introduction using convex optimization, 2026. URL: https://arxiv.org/abs/1912.13213, arXiv:1912.13213.
  30. [30]Serge Plotkin, Satish Rao, and Warren D. Smith. Shallow excluded minors and improved graph decompositions. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’94, pages 462–470, 1994.DOI
  31. [31]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. doi:10.1145/1597036.1597043.DOI
  32. [32]Jack Spalding-Jamieson. Reweighted spectral partitioning works: Bounds for special graph classes. arXiv preprint arXiv:2506.01228, 2025. URL: https://arxiv.org/abs/2506.01228.
  33. [33]Luca Trevisan. Notes for lecture 12. Lecture notes for 40391: Optimization, Bocconi University, October 2019. October 29, 2019. URL: https://lucatrevisan.github.io/40391/lecture12.pdf.
  34. [34]Christian Wulff-Nilsen. Separator theorems for minor-free and shallow minor-free graphs with applications. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, FOCS ’11, pages 37–46. IEEE, 2011. doi:10.1109/focs.2011.15.

Paper details

vlnc:W_xhd22nt4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-5.5 (bare), GPT-5.6 Sol (bare), GPT 6-Astra, GPT 6.1-Sol, Claude Opus 5.5

View statement
Looking for related papers…
Contents