WorksMathematics
-Minor-Free Graphs Have Balanced Separators of Size
Abstract
We show that every -minor-free graph with vertices has a balanced separator of size for any parameter , resolving the conjecture posed by Alon, Seymour, and Thomas [AST90] in 1990. The proof is elementary, building on the combinatorial framework by Le [Le26]. A key new idea of the proof is the existence of a short hitting walk on vertex expanders: given large (not necessarily disjoint) subsets of vertices, there is a walk of length hitting every subset, where is the vertex expansion. This technical result substantially improves on an analogous lemma by Alon, Seymour, and Thomas [AST90] in an important parameter setting, where the previous lower bound [Kot00] does not apply.
AI Disclosure. The key technical ideas of this paper are due to GPT-6 Astra, with some simplification due to Claude Opus 5.5. A Lean formalization1 of our main result was produced using a combination of GPT-6 Astra and Claude Opus 5.5, and its main definitions and statements have been checked over by the human authors. GPT-6.1 Sol was used to produce some figures from hand-drawn sketches. The human authors claim no role in developing the technical ideas. Our main contribution is verifying correctness, contextualizing the results, completely rewriting the paper to present the key new ideas in the proofs, and attributing existing ideas to prior work (to the best of our knowledge). In particular, we have simplified the proof for understandability, and obtained a slightly worse constant than the formalization in doing so.
Introduction
The separator theorem for planar graphs by Lipton and Tarjan [16] in 1979 is a cornerstone of algorithmic graph theory. Given a graph , a vertex subset is a balanced separator if every connected component of has size at most . The Lipton-Tarjan theorem says that any -vertex planar graph has a balanced (vertex) separator of size . This bound is asymptotically optimal: any balanced separator of the -planar grid must have size . A similar result was soon shown for bounded genus graphs [GHT84], which is also asymptotically tight. A decade later, Alon, Seymour, and Thomas [1] (AST) generalized the planar separator theorem to -minor-free graphs. They showed that any -vertex -minor-free graph has a balanced separator of size . In particular, for a constant , the AST separator has size ; this applies to planar graphs, which are -minor-free. In the regime of constant , their separator bound is also asymptotically optimal, witnessed by the -planar grid.
For non-constant , Alon, Seymour, and Thomas [1] conjectured that the bound is not optimal. They pointed out that for 3-regular expander graphs with vertices, , but the bound , while a (trivial) balanced separator has size . This excess of is their basis for the following conjecture.
Conjecture 1 (Alon-Seymour-Thomas Conjecture [1]). Any -minor-free graph with vertices has a balanced vertex separator of size for any .
University of Massachusetts Amherst. [email protected]. Supported by the NSF CAREER award CCF-2237288 and the NSF grant CCF-2517033.
Independent. [email protected]
https://github.com/jacket sj/formalized-minor-free-separators
Conjecture 1 has received significant attention over the last few decades; see Table 1 for an overview. In 1994, Plotkin, Rao, and Smith [18] constructed a balanced separator of size . For large , this improves on the AST bound, but for constant , their separator size is not optimal. Nearly two decades later, in 2010, Kawarabayashi and Reed [14] announced a separator result based on the Robertson–Seymour structure theorem; their precise bound is later clarified2 to be , where is a very fast-growing function. It is possible that the recently improved structure theorem for minor-free graphs [10] may reduce to a (very large) polynomial in , but even then it does not settle Conjecture 1, and the proof would not be elementary. Around the same time, Biswal, Lee, and Rao introduced a new technique to give another balanced separator of size . Although their bound is worse than the AST bound, their technique brought multicommodity flow-cut duality into the picture. Recent works [20, 15] exploit the optimal padded decomposition [6] to push the flow-cut duality technique much further and obtain a balanced separator of size [15]. This bound matches the barrier of the standard flow-cut approach, since the flow-cut gap can be (e.g. for 3-regular expanders).
Table 1. Bounds for balanced separators of -vertex -minor-free graphs.
Recently, Le [15] bypassed the flow-cut duality barrier and obtained a balanced separator of size . The main idea there is to incorporate the optimal padded decomposition by Conroy and Filtser [6] directly into the combinatorial frameworks by Alon, Seymour, and Thomas [1] and Plotkin, Rao, and Smith [18]. The factor is essentially where is the “padding parameter” of -minor-free graphs [6]. The bound is also optimal for . As noted in [15], “Erasing entirely seems to require substantially new ideas.”
Our main result is a complete resolution of Conjecture 1.
Theorem 1. Any -vertex -minor-free graph has a -balanced separator of size at most .
In Section 1.2, we give a detailed overview of the proof. Here we highlight two new ideas underlying the proof.
The first idea is a bound on the length of a walk intersecting large subsets of vertices in a vertex expander. To formally state the bound, we recall the definition of a vertex expander. Given a connected graph and a subset of vertices, we define the (outer) boundary , which is the set of vertices in that have at least one neighbor in . We say that is a -vertex expander for a parameter if, for every such that , . That is, every vertex subset of size at most has a sufficiently large external neighbor set in . We denote by .
The central new ingredient of the proof of Theorem 1 is the following theorem, which gives a short walk that intersects every set in a given collection of large subsets. Note that these subsets may not be vertex-disjoint.
Theorem 2 (Short Hitting Walk on Expanders).** Let be a connected graph on vertices. Let be subsets of vertices, each of size at least . Then has a walk of length less than that intersects every subset: for every .
To place Theorem 2 in context, we compare it with the following lemma of Alon, Seymour, and Thomas [1].
Lemma 1 (Lemma 2.1 [1]). Let be an -vertex graph and be a parameter. Let be subsets of vertices of . Then there exists either:
a tree in of at most vertices such that for every , or
a subset of size such that for every connected component of , for some .
Alon, Seymour, and Thomas [1] observed that improving the trade-off between the tree size and the separator size would improve their balanced-separator bound (which is ). However, Kotlov [13] later showed that the tradeoff is tight when is constant, and is the hypercube. Subsequent papers either avoid the AST framework entirely [14, 5, 20] or exploit -minor-freeness to get a better tradeoff [15]. (Herein, for simplicity, we assume that since this is the most interesting regime.) Specifically, Le [15] uses the optimal padded decomposition for -minor-free graphs [6] to construct a tree of size (in a very specific setting), improving over the bound in Lemma 1. The factor is essentially the padding parameter, which is best possible as noted above.
The walk-length bound in Theorem 2 improves the bound on in Lemma 1 to when for a sufficiently large constant . To see this, assume for every , and let be any set with . Every union of components of with has , so by the definition of a vertex expander. Take such an of maximum size. By maximality, every other component of has , which is greater than for , and therefore . So consists of and a single component , which intersects every because for any . Hence does not satisfy case 2 of Lemma 1, which requires every component of to miss some . Hence, case 2 cannot occur, and case 1 gives a tree with at most
vertices that intersects every . However, Theorem 2 gives a tree — more precisely, a spanning tree of the subgraph where is the walk — of only vertices that intersects every , a factor of improvement! Note Theorem 2 does not exploit -minor-freeness, and yet still gives a factor of improvement over Lemma 1.
At this point, readers might ask: does Theorem 2 contradict Kotlov’s [13] lower bound, which shows the tightness of Lemma 1? One observation is that Theorem 2 requires , whereas Lemma 1 imposes no such requirement. However, the lower bound instance of Kotlov [13] has , so assuming large subsets is not the source of the improvement. The key fact here is that the parameter setting in the application of Theorem 2 is outside the lower bound regime of Kotlov. Specifically, Kotlov’s lower bound applies to the case , and is the (discrete) hypercube (in ). For the hypercube,3 [11], and hence our setting of in Theorem 2 is , which is much larger than 2. In summary, there is no contradiction.
The second idea is to adapt the algorithm by Le [15], which itself is a combination of two different algorithms [1, 18], so that Theorem 2 can be applied. For readers who are familiar with Le [15] (as well as [1, 18]), in a nutshell, the algorithm is iterative, and every iteration essentially has two major steps: it finds either (i) a small set of vertices of the current subgraph that cuts off a large subset (relative to ), or (ii) a tree of small size that intersects every neighborhood of the current branch sets in the clique minor model. Here in this paper, both steps are reframed in terms of vertex expanders. Specifically, case (i) can be implemented as cutting off the smaller side of a sparse cut if is not a vertex expander, while in the (complementary) case (ii), is a vertex expander. In this case, we split into two smaller cases: one of which extends the neighborhood of each branch set, so its size is at least , then applies Theorem 2 to find the tree . The other smaller case is handled similarly to prior work [1, 15].
On notation. Graphs in this paper are unweighted and connected, unless explicitly noted otherwise. For any walk in , we denote by the length of the walk, which is the number of edges in (counted with multiplicity). Let denote a shortest path between and in a graph . We use to denote the distance between and , which is also . For any two walks and of that share the same endpoint, we denote by the walk obtained by concatenating and at the shared endpoint. We use to denote the set .
Related work
An orthogonal line of work on balanced separators of -minor-free graphs focuses on fast, ideally linear-time algorithms [1, 18, 19, 14, 21, 22, 3]. Here, we assume that the minor size is a fixed constant. In this regime, Bonnet, Korhonen, Le, Li, and Masařík [3] gave a linear-time algorithm, which concludes decades of effort on the running-time question. The dependency on in these works could be exponential [19] or polynomial with a high degree [3].
Another relevant line of work focuses on constructing balanced separators for more general graph classes, such as graphs with polynomial expansion [18, 7, 8], -induced-minor-free graphs [12], or fat-minor-free graphs [4]. In these papers, the separator size, especially its dependency on the minor size (in their respective definitions of graph minors), is not optimal. It would be interesting to see if the short hitting walk in Theorem 2 can be applied to improve the separators in these more general settings.
Proof overview
A minor model of a graph is a collection of vertex-disjoint connected subgraphs of , such that for any two different sets with there exists an edge where and . Each subgraph in is called a branch set. We use to denote the set of vertices .
The algorithm. We describe an algorithm to find an -size separator. (For simplicity, we are concerned only with the existence of the separator and not an efficient construction. The algorithm as we present it does not run in polynomial time.) In describing the algorithm, we assume that the walk-length bound in Theorem 2 holds. The algorithm is basically a reduction to the case where we can apply the walk-length bound. At the end, we give an overview of the proof of Theorem 2.
Just as in [1, 18, 15], our algorithm proceeds by iteratively sweeping a short separator through until it finds a balanced separator. It maintains an induced subgraph of which contains at least vertices; the current separator is the boundary of , denoted . One should think of as the largest connected component of after removing the “current separator.” We maintain the invariant that the current separator, i.e. the boundary of , always has size . To this end, the algorithm maintains two additional objects, whose union contains the boundary of : (1) a minor model of a clique in , such that each branch set has and (2) an additional subset of vertices, which we separately guarantee has size . The invariant that lies in the union implies that .
In each iteration of the algorithm, we add some vertices to , then set to be the largest connected component of . When the size of drops below , we return the boundary of as our balanced separator. In each iteration, there are three cases that determine which vertices to add to . The first two are simple cases. In the only remaining case, we can exploit the expander walk theorem.
Case 1: has small expansion.
Case 1 occurs if is not an -expander. In this case, there is a set of vertices whose boundary contains at most . We add to , and continue to the next iteration. A charging argument4 shows that never grows beyond .
**Case 2: Some branch set can be enlarged while preserving .
For Case 2, we check if there is some branch set and radius such that we can enlarge by growing a radius- ball around into . Such an enlargement is valid so long as still satisfies , which is equivalent to asking if there are at most vertices at distance from (with respect to ). If there is such a branch set and small-boundary ball, then we are in Case 2: we grow and update .
Case 3. Otherwise, we can apply the walk theorem. If Case 1 does not apply, we know is an -expander. If Case 2 does not apply, we can show that for any branch set , the -radius ball around contains at least vertices in . In this case, the hitting walk theorem applies, and we can find a walk in with vertices that travels within distance of every . We extend the walk so that it is adjacent to every . We have that . The vertices in become a new branch set that we add to .
In each of these three cases, we shrink while maintaining the invariant that . When becomes small enough, we terminate and return .
The existence of a short hitting walk in Theorem 2. It is well known that a -vertex-expander has diameter , which is also tight. Thus, we can construct a walk in Theorem 2 of length simply by picking one vertex per subset and connecting them into a walk using shortest paths. This bound is worse than Theorem 2 by a factor of and does not exploit the fact that the subsets are large (of size at least ).
Getting rid of this -factor is more complicated. The very high-level idea of the proof is to construct a randomized walk that performs exactly large steps, using shortest-paths between chosen vertices, while selecting exactly one of the sets in each step. We design the random walk to minimize the expected length of visiting a new subset. For simplicity of the exposition in this overview, we assume that the subsets are pairwise vertex disjoint, and each has size exactly .
In this special case, the random walk maintains the following invariant: After the -th step of the walk, we have selected a uniformly random -element subset , and the walk is guaranteed to hit all sets with . Moreover, conditioned on (for any fixed -element subset ), the last vertex on the walk is distributed uniformly at random among the vertices in the selected sets .
How should we design the random walk to maintain this invariant? Fix some and condition on the fact that our selected subset is . We know that the last vertex is uniformly distributed among . Call this distribution . To maintain the invariant, we would like to select a uniformly random index and a uniformly random vertex , and then extend the walk along a shortest path from to . Let denote the distribution from which is sampled. It is not difficult to see that if we sample according to , we maintain the desired invariant on the random walk.
The simplest way to sample from is to perform this sampling independently of the current vertex (which itself was sampled from ). However, this turns out to be a bad idea: the expected distance is too large, and we recover the same bound. Instead, we can sample from in a way that is correlated with . We exploit the fact that is an expander to show5 that can be sampled from such that
By linearity of expectation and a routine calculation, the expected length of the walk can then be bounded by
as claimed in Theorem 2.
In this overview, we used the pairwise disjointness assumption on the subsets to simplify the definitions of the two distributions and . In the actual proof, we slightly adjust the definitions of and to account for overlaps between subsets. Consequently, the proof that is somewhat more complicated than it would be in the disjoint-subset case.
Short Hitting Walks on Expanders
In this section, we prove Theorem 2, restated below.
Theorem 2 (Short Hitting Walk on Expanders). Let be a connected graph on vertices. Let be subsets of vertices, each of size at least . Then has a walk of length less than that intersects every subset: for every .
We prove Theorem 2 by constructing a randomized walk that can be viewed as a randomized greedy process in steps. Let . By discarding vertices from the subsets, we can assume that every subset has size exactly . For a subset , we denote by the set of subsets whose indices are in .
The algorithm. We start the walk at a random vertex , where is sampled uniformly at random from . At the beginning of step , let be the set of indices selected so far. We will maintain that , and that the walk intersects every subset in . Let , which is the set of indices not yet selected.
The walk currently ends at a vertex we denote as ; we can show (in Lemma 5) that the distribution of conditional on (for some subset ) is:
(If all subsets in are vertex-disjoint, then is simply the uniform distribution over vertices in conditional on ; the distribution in Equation (2) is simply adjusted for the overlap between the subsets in . Intuitively, we select a uniform random set , and then select a uniform random vertex in .) In the next step, we want the walk to get to a random vertex in a set in , whose indices have not been selected; is distributed according to:
which is also an adjusted uniform distribution to account for the overlap between the subsets in . By moving from to along the shortest path , hits a newly selected subset; see Figure 1. If these distributional properties were all we needed, then the algorithm and its analysis could be quite simple. However, we simultaneously need a bound on the expected total length of the walk, which we will accomplish by ensuring each component of the walk is short. In particular, our goal here is to move from to (sampling from their respective distributions in a correlated manner), so that is small. The minimum possible expectation is exactly the Wasserstein distance, defined formally in Definition 1, between and . (This problem has been studied extensively in optimal transport literature, but our construction does not require any deep understanding of this area.) As we will see, the solution to this problem gives us a distribution on , from which we can sample . Finally, we walk from to and proceed to the next iteration. The pseudocode is given in Algorithm 1.

Figure 1. One iteration of the walk construction on a graph. Each shaded subset contains vertices. The red path extends from to . Vertices belonging to two subsets in the same family receive twice the probability mass of vertices belonging to only one.
Definition 1 (Wasserstein distance). For a finite metric space , the Wasserstein distance between two probability distributions (so ) with respect to , denoted by , is the solution of the following linear program.
A simple interpretation of the Wasserstein distance in Definition 1 is this: fix a vertex ; if we move to according to the distribution:
then the expected cost of moving from to a random is . If we move from a random sampled from to a random sampled from , then the expected cost is:
That is, finding is equivalent to minimizing the expected distance from a random to a random , distributed according to and , respectively.
Algorithm 1 WASSERSTEINWALK
Input: a connected graph and subsets of size .
Output: a walk through that intersects every subset in .
sample uniformly, and sample uniformly.
and .
for to \hspace{1em} current endpoint of and indices visited up to step
for all \hspace{1em} distribution in Equation (2)
for all \hspace{1em} distribution in Equation (3)
optimal solution of Equation (4) for computing Wasserstein distance
for all \hspace{1em} the distribution to sample
sample according to
sample uniformly \hspace{1em} The walk will hit
return $W
In Section 2.1, we give a formal bound on the Wasserstein distance using the vertex expansion of graphs. Using this bound, we can bound the expected length of at the -th iteration, as stated in the following lemma.
Lemma 2. At iteration of Algorithm 1,
Here the expectation is over the random choices of the algorithm.
Since proving Lemma 2 requires understanding the relationship between Wasserstein distance and vertex expansion laid out in Section 2.1, we defer it to Section 2.2. Here, we show that Lemma 2 implies Theorem 2.
Proof of Theorem 2. Assume without loss of generality (by discarding elements) that each of the sets has exactly vertices. Let be the walk from running Algorithm 1 on and . By Lemma 2:
The second inequality is because decreases on and increases on . It remains to show that
This follows by substituting where ranges from to . Since and , we have
as claimed. Finally, because , there must exist some execution of Algorithm 1 that produces a walk with length less than .
Wasserstein distance and vertex expansion
This section proves the following lemma, which bounds the Wasserstein distance between and in terms of and the graph expansion. This lemma is the only fact needed to prove Lemma 2, so readers who are interested in the proof of Lemma 2 can skip this section.
Lemma 3. Let be a connected graph on vertices with shortest-path metric . If are probability distributions, then
Although we are not aware of the exact form of Lemma 3 in the literature, it can be easily deduced from two known results. The first is an immediate consequence of the well-known Kantorovich–Rubinstein dual of Wasserstein distance. The Kantorovich–Rubinstein dual is itself equivalent to the routine dual linear program for in Equation (4) so long as the weights satisfy the triangle inequality, and it can be stated in the following form for finite metrics.
The second result is by Bobkov, Houdré and Tetali [2], relating vertex expansion to feasible solutions of the dual program in Lemma 4 applied to shortest-path metrics.
Theorem 3 ([2 Theorem 1]). Let be a connected graph on vertices with shortest-path metric . If satisfies for all , then
Proof of Lemma 3. Let be an optimal solution of the dual program in Lemma 4 where the metric is . We have and for every . By Theorem 3:
Since , we have . Therefore,
as claimed. □
Bounding the expected distance
In this subsection, we prove Lemma 2. First, we show that is uniformly distributed over the size- subsets of , and that conditional on , the endpoint has distribution . All the probabilities and expectations are over the random choices of the algorithm.
Lemma 5. For every and every size--subset , and every vertex ,
Proof. We proceed by induction on . The base case holds by lines 1 and 2 of Algorithm 1. Now assume that and that the claim holds for . By induction hypothesis, is distributed according to . Algorithm 1 constructs a coupling between the distributions and and uses this to sample , so has distribution : formally,
Now, notice that (conditional on ) the algorithm first samples according to , and then samples uniformly at random among . This leads to a key observation: for any and ,
Part 1 of the claim. We prove that is uniformly distributed. First observe that (conditional on ), the next selected index is uniformly distributed among . Indeed, we can sum (11) over the vertices of :
The first part of the claim now follows: if we start with as a uniform random -element subset of (which we do, by induction), and add a uniformly random element in to form , the set is a uniformly random -element subset of . That is, for any size- subset .6
Part 2 of the claim. We prove that the distribution of has the desired form. Let be a size- subset of and let . Observe that
where the second-to-last equality follows from (11). Hence
as claimed. □
Now we prove Lemma 2 restated below.
Lemma 2. At iteration of Algorithm 1,
Here the expectation is over the random choices of the algorithm.
Proof: By Lemma 5, given , we have with probability . Then in line 8, we sample and:
Then, we have:
By averaging over (rather than conditioning on ), we get:
Now we focus on bounding . To this end, for each , let if and otherwise. Then by the definition of and in Equations (2) and (3), for every ,
By Lemma 5, is a uniformly random size- subset of , so each lies in with probability , and
For distinct , considering whether both, neither or exactly one of and lie in gives
By Equation (16), we get
Plugging Equation (19) into Equation (15), we get:
as claimed. □
The Algorithm
For a subgraph of and a set of vertices of , let denote the set of vertices of that are not in but have at least one neighbor in . We note that might not belong to ; for example, when is a subgraph of a larger graph and that is not in . When , we use the notation to denote the ball of radius around in , that is, . We will use the following corollary of Theorem 2.
Corollary 1. Suppose that is a -vertex expander. Let be a collection of vertex subsets of such that and . Then there is a procedure SHORTTREE(H, X) that produces a tree such that:
for every .
.
Proof. If , then we can apply Theorem 2 to produce a walk , and we can then simply take to be a spanning tree of . As has length strictly less than , the tree has at most vertices. If , then we duplicate to get and apply Theorem 2 to and . □
The algorithm. We begin with an informal description of the algorithm. The formal pseudocode is given as Algorithm 2. At every step, the algorithm maintains three important objects: , and .
is an induced subgraph of . Except when the algorithm terminates, contains at least vertices. One should think of the “current separator” as , and as the largest connected component7 of if we remove from .
The “current separator” will lie in the union of two objects:
is a subset of vertices of which the algorithm will keep adding to. We guarantee that .
is a clique minor model found so far, whose branch sets of are disjoint from . We guarantee that, for every , we have .
It will hold that and are disjoint from . See Figure 2.
Figure 2. The subgraph . The boundary of is contained in the union of (drawn in orange) and the vertices of the minor model .
In every step, the algorithm removes at least one vertex from and at most vertices from , adding them to or . The algorithm terminates when the size of drops below , at which point we return as the separator.8 Because each step removes at most vertices, we have and thus is a balanced separator. To guarantee that has size , we maintain the invariant that , that , and that for each branch set we have (recall that -minor-freeness implies that contains at most branch sets).
Each iteration of the algorithm proceeds as follows. At the start, the algorithm checks whether any connected component of has vertices. If not, we terminate and return the current separator ; otherwise we update to be the largest connected component, update by discarding all branch sets that aren’t adjacent to , and proceed. Within each iteration, there are three cases; see Figure 3.

Figure 3. The three cases possible in each step of the algorithm
Case 1: is not a -vertex expander.
By the definition of a vertex expander, there must be a subset of vertices such that and (the smaller side of the sparse cut). We will update by adding to , and removing from . We can afford adding to since we can charge the size of to . Each vertex gets charge over the entire process, since will be removed from (once is reassigned to the largest connected component) and so over the entire course of the algorithm, the size of is bounded by .
Case 2: There exists branch set and with and .
Then we simply grow by adding the entire ball to , and (correspondingly) deleting from . This step could blow up the size of significantly (up to ). However, since , after the update we still have that . The condition just guarantees that we remove at most vertices from in this step.
Case 3: Otherwise.
In this case, (i) is an -vertex expander, and (ii) for every branch set and radius , either or . If we pick , we can show (Claim 1) that . We can now form and apply Corollary 1 to get a tree of size that intersects every set in . We then extract so that it is adjacent to every branch set in : for every branch set , we pick an arbitrary vertex , and add to the shortest path in from to a vertex in . Note that since and , the total size of all the paths added to is at most , so the total size of (a new branch set) formed in this step is still . We add to , and remove from .
In summary, the algorithm guarantees that (Case 1) and for every branch set , either (Case 2) or directly that (Case 3). Moreover, the current separator is in . Since , the size of the current separator is always . Once , the current separator is balanced and we simply return it.
Algorithm 2 BALANCEDSEPARATOR() ▷ Find a balanced separator of size
, ,
while there is some connected component of with vertices do
largest connected component of
has a neighbor in
if is not a -vertex expander then ▷ Case 1
nonempty subset of such that and
.
else if there exists and with and then ▷ Case 2
.
else ▷ : or ▷ Case 3
if then
an arbitrary vertex in
else
▷ Claim 1 shows that .
for every do
a vertex in
a shortest path in from to a vertex in ▷ exists because is connected.
▷ this makes adjacent to .
return
We now turn to the analysis. First, we show that every set in line 18 has size at least . This justifies the call to in line 19.
Claim 1. Let be a branch set such that for every , either or .
Then
where . Consequently, is a valid input to the SHORTTREE procedure on line 19.
Proof: If there exists such that , then the claim holds, as . Otherwise, by assumption, for we have that . Observing that contains for every , we conclude
as claimed. Thus, when we call SHORTTREE in line 19, it holds that every has and that is an -vertex expander, as required by the definition of SHORTTREE. □
This shows that the algorithm is well-defined. We now observe that it terminates.
Lemma 6. The algorithm BALANCEDSEPARATOR terminates.
Proof: It suffices to show that every iteration of the while loop removes at least one vertex from . Indeed, in Case 1, we remove some nonempty subset from . In Case 2, we remove some ball from ; this ball is nonempty because it contains , which is nonempty because (due to the trimming in line 4) has some neighbor in . In Case 3, we remove the nonempty set from . □
We record two simple invariants.
Lemma 7. At the start of every iteration, the following properties hold:
is a clique minor model in (of size ). Thus .
and are disjoint.
Proof: In the beginning of the algorithm, we have , , and , and so the invariants are satisfied trivially.
By induction, assume that is a model of a clique minor in at the start of the current iteration. Discarding some branch sets in line 4 does not affect this property. In the rest of the iteration (lines 5–24), we may modify during one of the three cases of the algorithm. In Case 1, is unchanged. In Case 2, some is expanded (line 11) to include additional vertices in . But remains disjoint from the other branch sets after the expansion (because, by induction, was disjoint from the other branch sets), remains adjacent to all other branch sets, and remains connected; thus remains a clique minor model. Finally, in Case 3, a new branch set is added. If is a singleton added by line 15 then the claim holds. In the nontrivial case (lines 17–23), the branch set is disjoint from the other because and is disjoint from the other branch sets; moreover, is adjacent to every other branch set because we added the path to in line 23.
By induction, assume and are disjoint at the start of the current iteration. In this iteration, the set shrinks, and some vertices may be added to . It suffices to show that every vertex added to in the iteration is removed from . Indeed, in Case 1, no new vertices are added to ; in Case 2, the ball is added to and removed from ; and in Case 3, the vertices of the new branch set are added to and removed from . □
We can now prove that the algorithm produces a separator of size (Lemma 8), and that this separator is balanced (Lemma 9). Our main theorem follows.
Lemma 8 (Size bound). At the start and end of every iteration of the while loop, we have . This is a consequence of the following invariants:
For every , we have
Proof: Given the invariants, we can conclude that , where the second-to-last inequality follows from the fact that (by Lemma 7(1)). It remains to prove the invariants.
We proceed by induction. Assume that holds at the start of the while loop (line 3). Observe that for any connected component of , we have ; thus the claim holds after line 3 (when the largest connected component of is renamed as ), and it also holds trivially after line 4 (when all branch sets not adjacent to are discarded). In lines 5–25, in each of the three cases is modified in the following way: some set of vertices is added to , and these same vertices are removed from . When removing a vertex from , the only possible new vertex that could be added to is itself. Thus, after each iteration it remains the case that .
We prove by a charging argument. Note that we only add to in line 7: whenever we add to , we charge the size of to . Each vertex in gets at most charge. Now we argue that vertices of will not be charged again in future iterations. Indeed, after we delete from in this iteration, any connected component that intersects (and is therefore fully contained in ) contains at most vertices. But if the algorithm continues, it reassigns (in line 3) to be some connected component with at least vertices. Thus vertices in are never charged again, and the total size of over all iterations is at most .
At the start of the algorithm, we have and the claim holds trivially. There are three things that can occur during the course of the algorithm that could affect whether the claim holds: (1) the set can change, (2) some set may be modified in Case 2, or (3) a new set may be created in Case 3. We claim that after any of these changes, the claim still holds.
For the first, observe that only shrinks over the course of the algorithm (i.e., is changed to be some subgraph of itself). As every is disjoint from (by Lemma 7(2)), shrinking can only cause the set to shrink.
For the second, suppose that Case 2 selects some ball and updates and . For clarity, let and denote the sets before the update, and let and denote the sets after the update. We want to show that . To this end, we first define and observe that . We claim that
The desired size bound on follows from (21), as by assumption of Case 2 we have . To prove (21), observe that , so it suffices to show that vertices in are not in . Indeed, every vertex in has no neighbors in , as every neighbor lying in is in ; similarly, every vertex in has no neighbors in , as its neighbors in are in . So, the only vertices in that could be adjacent to (and thus in ) are those in , as desired.
Finally, for the third case, suppose that Case 3 adds some new branch set to . When is formed in line 19, by Corollary 1
Then is extended further in line 23 by adding at most vertices per branch set, totaling at most . (If , our main theorem holds trivially.) Thus, .
Lemma 9 (Balance). At every point during the algorithm, we have . Moreover, when the algorithm terminates, every connected component of has at most vertices.
Proof. The second statement follows immediately from the while loop termination condition. We now show that always. Indeed, initially we have . At the beginning of each iteration, after line 3, we have by assumption. During the iteration, in steps 4–25 of the algorithm, at most vertices are removed from : in case 1 we remove vertices, where (note we assume as otherwise our main theorem holds trivially); in Case 2 we remove vertices; and in Case 3 we remove vertices, where the proof of Lemma 8(3) shows that , which is if is sufficiently large.9 Thus the size of is always at least . □
The main theorem follows immediately from Lemmas 8 and 9.
Theorem 1. Any -vertex -minor-free graph has a -balanced separator of size at most .
Proof. The algorithm returns , which comprises at most vertices by Lemma 8. Moreover, every connected component of is either a connected component of or is contained in ; as Lemma 9 implies that connected components of have size and that , we conclude that is a balanced separator of . □
References
- [1]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
- [2]Sergey G. Bobkov, Christian Houdré, and Prasad Tetali. λ∞, vertex isoperimetry and concentration. Comb., 20(2):153–172, 2000. URL: https://doi.org/10.1007/s004930070018, doi:10.1007/S004930070018.
- [3]É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
- [4]Édouard Bonnet, Hung Le, Marcin Pilipczuk, and Michał Pilipczuk. Coarse balanced separators in fat-minor-free graphs, 2026. URL: https://arxiv.org/abs/2604.11318, arXiv:2604.11318, doi:10.48550/arXiv.2604.11318.
- [5]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.
- [6]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.
- [7]Zdenek Dvořák and Sergey Norin. Strongly sublinear separators and polynomial expansion. SIAM Journal on Discrete Mathematics, 30(2):1095–1101, 2016.DOI
- [8]Louis Esperet and Jean-Florent Raymond. Polynomial expansion and sublinear separators. European Journal of Combinatorics, 69:49–53, 2018.DOI
- [10][GSW25] Maximilian Gorsky, Michał T. Seweryn, and Sebastian Wiederrecht. Polynomial bounds for the graph minor structure theorem. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science—FOCS 2025, pages 1961–1978. IEEE Comput. Soc. Press, Los Alamitos, CA, 2025. doi:10.1109/FOCS63196.2025.00104.DOI
- [11][Har66] L.H. Harper. Optimal numberings and isoperimetric problems on graphs. Journal of Combinatorial Theory, 1(3):385–393, 1966. URL: http://dx.doi.org/10.1016/S0021-9800(66)80059-5, doi: 10.1016/S0021-9800(66)80059-5.
- [12][KL24] Tuukka Korhonen and Daniel Lokshtanov. 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.DOI
- [13][Kot00] Andrei Kotlov. Bulky subgraphs of the hypercube. European Journal of Combinatorics, 21(4):503–507, May 2000. doi:10.1006/eujc.1999.0362.DOI
- [14][KR10] 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
- [15][Le26] Hung Le. A separator for minor-free graphs beyond the flow barrier. arXiv preprint arXiv:2605.05494, 2026. URL: https://arxiv.org/abs/2605.05494.
- [16][LT79] 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
- [17][PC19] Gabriel Peyré and Marco Cuturi. Computational optimal transport with applications to data sciences. Foundations and trends® in machine learning, 11(5-6):355–607, 2019.
- [18][PRS94] 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
- [19][RW09] 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
- [20][Spa25] 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.
- [21][Wul11] 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.
- [22][Wul14] Christian Wulff-Nilsen. Faster separators for shallow minor-free graphs via dynamic approximate distance oracles. In International Colloquium on Automata, Languages, and Programming, ICALP ’14, pages 1063–1074. Springer, 2014. doi:10.1007/978-3-662-43948-7_88.
