betaFeedback

WorksMathematics

KhK_h-Minor-Free Graphs Have Balanced Separators of Size O(hn)O(h\sqrt{n})

Abstract

We show that every KhK_h-minor-free graph with nn vertices has a balanced separator of size O(hn)O(h\sqrt{n}) for any parameter h∈Nh \in \mathbb{N}, 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 kk large (not necessarily disjoint) subsets of vertices, there is a walk of length O(k/ψ(G))O(k/ψ(G)) hitting every subset, where ψ(G)ψ(G) 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 G=(V,E)G = (V, E), a vertex subset S⊂VS \subset V is a balanced separator if every connected component of G∖SG \setminus S has size at most 3∣V∣/43|V|/4. The Lipton-Tarjan theorem says that any nn-vertex planar graph has a balanced (vertex) separator of size O(n)O(\sqrt{n}). This bound is asymptotically optimal: any balanced separator of the n×n\sqrt{n} \times\sqrt{n}-planar grid must have size Ω(n)\Omega(\sqrt{n}). 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 KhK_h-minor-free graphs. They showed that any nn-vertex KhK_h-minor-free graph has a balanced separator of size O(h3/2n)O(h^{3/2}\sqrt{n}). In particular, for a constant hh, the AST separator has size O(n)O(\sqrt{n}); this applies to planar graphs, which are K5K_5-minor-free. In the regime of constant h≥5h \ge5, their separator bound is also asymptotically optimal, witnessed by the n×n\sqrt{n} \times\sqrt{n}-planar grid.

For non-constant hh, Alon, Seymour, and Thomas [1] conjectured that the bound is not optimal. They pointed out that for 3-regular expander graphs with nn vertices, h=Θ(n1/2)h = \Theta(n^{1/2}), but the bound O(h3/2n)=O(n1/4n)O(h^{3/2}\sqrt{n}) = O(n^{1/4}n), while a (trivial) balanced separator has size nn. This excess of h\sqrt{h} is their basis for the following conjecture.

Conjecture 1 (Alon-Seymour-Thomas Conjecture [1]). Any KhK_h-minor-free graph with nn vertices has a balanced vertex separator of size O(hn)O(h\sqrt{n}) for any h≥3h \ge3.

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 O(hnlog⁡n)O(h\sqrt{n\log n}). For large hh, this improves on the AST bound, but for constant hh, 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 O(hn+f(h))O(h\sqrt{n}+f(h)), where f(h)f(h) is a very fast-growing function. It is possible that the recently improved structure theorem for minor-free graphs [10] may reduce f(h)f(h) to a (very large) polynomial in hh, 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 O(h3log⁡h⋅n)O(h^3\sqrt{\log h}\cdot\sqrt{n}). 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 O(hlog⁡h⋅n)O(h\log h\cdot\sqrt{n}) [15]. This bound matches the barrier of the standard flow-cut approach, since the flow-cut gap can be Ω(log⁡h)\Omega(\log h) (e.g. for 3-regular expanders).

Separator sizeReferenceYearNotes
O(h3/2n)O(h^{3/2}\sqrt{n})[1]1990
O(hnlog⁡n)O(h\sqrt{n\log n})[18]1994
O(h3log⁡h⋅n)O(h^3\sqrt{\log h}\cdot\sqrt{n})[5]2008flow-cut duality
O(hn+f(h))O(h\sqrt{n}+f(h))[14]2010f(h)f(h) is a fast growing function
O(hlog⁡hlog⁡log⁡h⋅n)O(h\log h\log\log h\cdot\sqrt{n})[20]2025
O(hlog⁡h⋅n)O(h\log h\cdot\sqrt{n})[15 Thm. 1]2026optimal flow-cut duality
O(hlog⁡h⋅n)O(h\sqrt{\log h}\cdot\sqrt{n})[15 Thm. 2]2026bypasses flow-cut duality
O(hn)O(h\sqrt{n})This paperAsymptotically optimal [1]

Table 1. Bounds for balanced separators of nn-vertex KhK_h-minor-free graphs.

Recently, Le [15] bypassed the flow-cut duality barrier and obtained a balanced separator of size O(hnlog⁡h)O(h\sqrt{n\log h}). 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 log⁡h\sqrt{\log h} factor is essentially βh\sqrt{\beta_h} where βh=Θ(log⁡h)\beta_h=\Theta(\log h) is the “padding parameter” of KhK_h-minor-free graphs [6]. The bound log⁡h\log h is also optimal for βh\beta_h. As noted in [15], “Erasing log⁡h\sqrt{\log h} entirely seems to require substantially new ideas.”

Our main result is a complete resolution of Conjecture 1.

Theorem 1. Any nn-vertex KhK_h-minor-free graph GG has a 3/43/4-balanced separator of size at most 16hn16h\sqrt{n}.

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 kk 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 G=(V,E)G=(V,E) and a subset S⊆VS\subseteq V of vertices, we define the (outer) boundary ∂S:={v∈V∖S:∃u∈S,uv∈E}\partial S:=\{v\in V\setminus S:\exists u\in S,uv\in E\}, which is the set of vertices in V∖SV\setminus S that have at least one neighbor in SS. We say that GG is a ψ\psi-vertex expander for a parameter ψ>0\psi>0 if, for every S⊆VS\subseteq V such that ∣S∣≤∣V∣/2|S|\leq|V|/2, ∣∂S∣≥ψ∣S∣|\partial S|\geq\psi|S|. That is, every vertex subset of size at most ∣V∣/2|V|/2 has a sufficiently large external neighbor set in GG. We denote by ψ(G)=max⁡{ψ:G is a ψ-vertex expander}\psi(G)=\max\{\psi:G\text{ is a }\psi\text{-vertex expander}\}.

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 G=(V,E)G=(V,E) be a connected graph on nn vertices. Let X1,…,Xk⊂VX_1,\ldots,X_k\subset V be kk subsets of vertices, each of size at least n/kn/k. Then GG has a walk WW of length less than 13k/ψ(G)13k/\psi(G) that intersects every subset: W∩Xi≠∅W\cap X_i\neq\varnothing for every i∈[k]i\in[k].

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 G=(V,E)G=(V,E) be an nn-vertex graph and ℓ>0\ell>0 be a parameter. Let X1,…,XkX_1,\ldots,X_k be kk subsets of vertices of GG. Then there exists either:

  1. a tree TT in GG of at most ℓk\ell k vertices such that T∩Xi≠∅T\cap X_i\ne\varnothing for every i∈[k]i\in[k], or

  2. a subset Z⊆VZ\subseteq V of size ∣Z∣<n/ℓ|Z|<n/\ell such that for every connected component CC of G∖ZG\setminus Z, C∩Xi=∅C\cap X_i=\varnothing for some i∈[k]i\in[k].

Alon, Seymour, and Thomas [1] observed that improving the trade-off between the tree size hℓh\ell and the separator size n/ℓn/\ell would improve their balanced-separator bound (which is O(h3/2n)O(h^{3/2}\sqrt{n})). However, Kotlov [13] later showed that the tradeoff is tight when ℓ\ell is constant, and GG is the hypercube. Subsequent papers either avoid the AST framework entirely [14, 5, 20] or exploit KhK_h-minor-freeness to get a better tradeoff [15]. (Herein, for simplicity, we assume that k=hk=h since this is the most interesting regime.) Specifically, Le [15] uses the optimal padded decomposition for KhK_h-minor-free graphs [6] to construct a tree TT of size O(ℓlog⁡h)O(\ell\log h) (in a very specific setting), improving over the bound O(hℓ)O(h\ell) in Lemma 1. The log⁡h\log h factor is essentially the padding parameter, which is best possible as noted above.

The walk-length bound in Theorem 2 improves the bound on ∣V(T)∣|V(T)| in Lemma 1 to O(ℓ)O(\ell) when ℓ=c⋅h/ψ(G)\ell=c\cdot h/\psi(G) for a sufficiently large constant cc. To see this, assume ∣Xi∣=n/h|X_i|=n/h for every i∈[k]i\in[k], and let Z⊆VZ\subseteq V be any set with ∣Z∣<n/ℓ=ψ(G)⋅n/(c⋅h)|Z|<n/\ell=\psi(G)\cdot n/(c\cdot h). Every union SS of components of G∖ZG\setminus Z with ∣S∣≤n/2|S|\le n/2 has ∂S⊆Z\partial S\subseteq Z, so ∣S∣≤∣Z∣/ψ(G)<n/(c⋅h)|S|\le|Z|/\psi(G)<n/(c\cdot h) by the definition of a vertex expander. Take such an SS of maximum size. By maximality, every other component CC of G∖ZG\setminus Z has ∣C∣>n/2−∣S∣>n/2−n/(c⋅h)|C|>n/2-|S|>n/2-n/(c\cdot h), which is greater than n/(c⋅h)>∣S∣n/(c\cdot h)>|S| for c≥2c\ge2, and therefore ∣C∣>n/2|C|>n/2. So G∖ZG\setminus Z consists of SS and a single component CC, which intersects every XiX_i because ∣V∖C∣=∣S∣+∣Z∣<n/(c⋅h)+ψ(G)⋅n/(c⋅h)=(1+ψ(G))⋅n/(c⋅h)≤n/h=∣Xi∣|V\setminus C|=|S|+|Z|<n/(c\cdot h)+\psi(G)\cdot n/(c\cdot h)=(1+\psi(G))\cdot n/(c\cdot h)\le n/h=|X_i| for any c≥3≥1+ψ(G)c\ge3\ge1+\psi(G). Hence ZZ does not satisfy case 2 of Lemma 1, which requires every component of G∖ZG\setminus Z to miss some XiX_i. Hence, case 2 cannot occur, and case 1 gives a tree TT with at most

hℓ=O(h2/ψ(G))h\ell=O(h^2/\psi(G))

vertices that intersects every XiX_i. However, Theorem 2 gives a tree — more precisely, a spanning tree of the subgraph G[V(W)]G[V(W)] where WW is the walk — of only O(h/ψ(G))O(h/\psi(G)) vertices that intersects every XiX_i, a factor of hh improvement! Note Theorem 2 does not exploit KhK_h-minor-freeness, and yet still gives a factor of hh 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 ∣Xi∣≥n/k|X_i|\ge n/k, whereas Lemma 1 imposes no such requirement. However, the lower bound instance of Kotlov [13] has ∣Xi∣=n/2|X_i|=n/2, so assuming large subsets is not the source of the improvement. The key fact here is that the parameter setting ℓ=c⋅k/ψ(G)\ell=c\cdot k/\psi(G) in the application of Theorem 2 is outside the lower bound regime of Kotlov. Specifically, Kotlov’s lower bound applies to the case ℓ=2\ell=2, k≈2log⁡(n)k\approx2\log(n) and GG is the (discrete) hypercube (in {0,1}log⁡n\{0,1\}^{\log n}). For the hypercube,3 ψ(G)=Θ(1/log⁡n)\psi(G)=\Theta(1/\sqrt{\log n}) [11], and hence our setting of ℓ\ell in Theorem 2 is ℓ=c⋅k/ψ(G)=Θ(log⁡3/2(n))\ell=c\cdot k/\psi(G)=\Theta(\log^{3/2}(n)), 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 ZZ of the current subgraph H⊆GH\subseteq G that cuts off a large subset AA (relative to ∣Z∣|Z|), or (ii) a tree T⊆HT\subseteq H 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 HH is not a vertex expander, while in the (complementary) case (ii), HH 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 n/hn/h, then applies Theorem 2 to find the tree TT. 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 WW in GG, we denote by ∣W∣|W| the length of the walk, which is the number of edges in WW (counted with multiplicity). Let πG(u,v)\pi_G(u,v) denote a shortest path between uu and vv in a graph GG. We use dG(u,v)d_G(u,v) to denote the distance between uu and vv, which is also ∣πG(u,v)∣|\pi_G(u,v)|. For any two walks PP and QQ of GG that share the same endpoint, we denote by P∘QP\circ Q the walk obtained by concatenating PP and QQ at the shared endpoint. We use [n][n] to denote the set {1,2,…,n}\{1,2,\ldots,n\}.

Related work

An orthogonal line of work on balanced separators of KhK_h-minor-free graphs focuses on fast, ideally linear-time algorithms [1, 18, 19, 14, 21, 22, 3]. Here, we assume that the minor size hh 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 hh 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], HH-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 KtK_t minor model of a graph GG is a collection K={C1,C2,…,Ct}\mathcal{K}=\{C_1,C_2,\ldots,C_t\} of vertex-disjoint connected subgraphs of GG, such that for any two different sets Ci,CjC_i,C_j with 1≤i≠j≤t1\leq i\neq j\leq t there exists an edge (u,v)∈E(u,v)\in E where u∈Ciu\in C_i and v∈Cjv\in C_j. Each subgraph in K\mathcal{K} is called a branch set. We use V(K)V(\mathcal{K}) to denote the set of vertices ⋃C∈KC\bigcup_{C\in\mathcal{K}} C.

The algorithm. We describe an algorithm to find an O(hn)O(h\sqrt{n})-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 GG until it finds a balanced separator. It maintains an induced subgraph HH of GG which contains at least 3n/43n/4 vertices; the current separator is the boundary of HH, denoted ∂H\partial H. One should think of HH as the largest connected component of GG after removing the “current separator.” We maintain the invariant that the current separator, i.e. the boundary of HH, always has size O(hn)O(h\sqrt{n}). To this end, the algorithm maintains two additional objects, whose union contains the boundary of HH: (1) a minor model K\mathcal{K} of a clique in GG, such that each branch set C∈KC\in\mathcal{K} has ∣∂H∩C∣≤O(n)|\partial H\cap C|\leq O(\sqrt{n}) and (2) an additional subset XX of vertices, which we separately guarantee has size O(hn)O(h\sqrt{n}). The invariant that ∂H\partial H lies in the union X∪V(K)X\cup V(\mathcal{K}) implies that ∣∂H∣≤O(hn)|\partial H|\leq O(h\sqrt{n}).

In each iteration of the algorithm, we add some vertices to X∪V(K)X\cup V(\mathcal{K}), then set HH to be the largest connected component of H∖(X∪V(K))H\setminus(X\cup V(\mathcal{K})). When the size of HH drops below 3n/43n/4, we return the boundary of HH as our balanced separator. In each iteration, there are three cases that determine which vertices to add to X∪V(K)X\cup V(\mathcal{K}). The first two are simple cases. In the only remaining case, we can exploit the expander walk theorem.

  • Case 1: HH has small expansion.

    Case 1 occurs if HH is not an h/nh/\sqrt{n}-expander. In this case, there is a set of vertices AA whose boundary ZZ contains at most h/n∣A∣h/\sqrt{n}|A|. We add ZZ to XX, and continue to the next iteration. A charging argument4 shows that XX never grows beyond O(hn)O(h\sqrt{n}).

  • **Case 2: Some branch set C∈KC\in\mathcal{K} can be enlarged while preserving ∣∂H∩C∣≤O(n)|\partial H\cap C|\leq O(\sqrt{n}).

For Case 2, we check if there is some branch set CC and radius rr such that we can enlarge CC by growing a radius-rr ball around CC into HH. Such an enlargement is valid so long as CC still satisfies ∣∂H∩C∣≤O(n)|\partial H \cap C| \le O(\sqrt{n}), which is equivalent to asking if there are at most O(n)O(\sqrt{n}) vertices at distance rr from CC (with respect to HH). If there is such a branch set CC and small-boundary ball, then we are in Case 2: we grow CC and update K\mathcal{K}.

  • Case 3. Otherwise, we can apply the walk theorem. If Case 1 does not apply, we know HH is an h/nh/\sqrt{n}-expander. If Case 2 does not apply, we can show that for any branch set C∈KC \in\mathcal{K}, the n/h\sqrt{n}/h-radius ball around CC contains at least n/hn/h vertices in HH. In this case, the hitting walk theorem applies, and we can find a walk WW in HH with O(n)O(\sqrt{n}) vertices that travels within distance n/h\sqrt{n}/h of every C∈KC \in\mathcal{K}. We extend the walk WW so that it is adjacent to every C∈KC \in\mathcal{K}. We have that ∣W∣=O(n)|W| = O(\sqrt{n}). The vertices in WW become a new branch set that we add to K\mathcal{K}.

In each of these three cases, we shrink HH while maintaining the invariant that ∣∂H∣≤O(hn)|\partial H| \le O(h\sqrt{n}). When HH becomes small enough, we terminate and return ∂H\partial H.

The existence of a short hitting walk in Theorem 2. It is well known that a ψ(G)\psi(G)-vertex-expander has diameter O(log⁡n/ψ(G))O(\log n/\psi(G)), which is also tight. Thus, we can construct a walk in Theorem 2 of length O(klog⁡n/ψ(G))O(k\log n/\psi(G)) 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 log⁡n\log n and does not exploit the fact that the subsets are large (of size at least n/kn/k).

Getting rid of this log⁡n\log n-factor is more complicated. The very high-level idea of the proof is to construct a randomized walk WW that performs exactly kk large steps, using shortest-paths between chosen vertices, while selecting exactly one of the sets X1,…,XkX_1,\ldots,X_k 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 {X1,…,Xk}\{X_1,\ldots,X_k\} are pairwise vertex disjoint, and each has size exactly r:=⌈n/k⌉r := \lceil n/k\rceil.

In this special case, the random walk maintains the following invariant: After the tt-th step of the walk, we have selected a uniformly random tt-element subset I⊆[k]I \subseteq[k], and the walk is guaranteed to hit all sets XiX_i with i∈Ii \in I. Moreover, conditioned on I=JI = J (for any fixed tt-element subset J⊆[k]J \subseteq[k]), the last vertex on the walk is distributed uniformly at random among the vertices in the selected sets {v∈Xi:i∈J}\{v \in X_i : i \in J\}.

How should we design the random walk to maintain this invariant? Fix some J⊆[k]J \subseteq[k] and condition on the fact that our selected subset is I=JI = J. We know that the last vertex vtv_t is uniformly distributed among {v∈Xi:i∈J}\{v \in X_i : i \in J\}. Call this distribution pJp_J. To maintain the invariant, we would like to select a uniformly random index i∈[k]∖Ji \in[k] \setminus J and a uniformly random vertex vt+1∈Xiv_{t+1} \in X_i, and then extend the walk WW along a shortest path from vtv_t to vt+1v_{t+1}. Let qJq_J denote the distribution from which vt+1v_{t+1} is sampled. It is not difficult to see that if we sample vt+1v_{t+1} according to qJq_J, we maintain the desired invariant on the random walk.

The simplest way to sample vt+1v_{t+1} from qJq_J is to perform this sampling independently of the current vertex vtv_t (which itself was sampled from pJp_J). However, this turns out to be a bad idea: the expected distance E[d(vt,vt+1)]\mathbb{E}[d(v_t,v_{t+1})] is too large, and we recover the same O(klog⁡n/ψ(G))O(k\log n/\psi(G)) bound. Instead, we can sample from qJq_J in a way that is correlated with pJp_J. We exploit the fact that GG is an expander to show5 that vt+1v_{t+1} can be sampled from qJq_J such that

E[d(vt,vt+1)]≤4kψ(G)t(k−t).\mathbb{E}[d(v_t,v_{t+1})] \le\frac{4k}{\psi(G)\sqrt{t(k-t)}}.

By linearity of expectation and a routine calculation, the expected length of the walk can then be bounded by

E[∣W∣]≤4kψ(G)∑j=1k−11j(k−j)≤4kψ(G)∫0kdtt(k−t)=4πkψ(G)<13kψ(G).(1)\mathbb{E}[|W|] \le\frac{4k}{\psi(G)}\sum_{j=1}^{k-1}\frac{1}{\sqrt{j(k-j)}} \le\frac{4k}{\psi(G)}\int_0^k \frac{dt}{\sqrt{t(k-t)}} = \frac{4\pi k}{\psi(G)} < \frac{13k}{\psi(G)}. \tag*{(1)}

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 pJp_J and qJq_J. In the actual proof, we slightly adjust the definitions of pJp_J and qJq_J to account for overlaps between subsets. Consequently, the proof that E[d(vt,vt+1)]≤4kψ(G)t(k−t)\mathbb{E}[d(v_t, v_{t+1})] \le\frac{4k}{\psi(G)\sqrt{t(k-t)}} 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 G=(V,E)G = (V, E) be a connected graph on nn vertices. Let X1,…,Xk⊂VX_1,\ldots,X_k \subset V be kk subsets of vertices, each of size at least n/kn/k. Then GG has a walk WW of length less than 13k/ψ(G)13k/\psi(G) that intersects every subset: W∩Xi≠∅W \cap X_i \ne\varnothing for every i∈[k]i \in[k].

We prove Theorem 2 by constructing a randomized walk that can be viewed as a randomized greedy process in k−1k - 1 steps. Let X={X1,X2,…,Xk}\mathcal{X} = \{X_1, X_2, \ldots, X_k\}. By discarding vertices from the subsets, we can assume that every subset X∈XX \in\mathcal{X} has size exactly r:=⌈n/k⌉r := \lceil n/k\rceil. For a subset I⊆[k]I \subseteq[k], we denote by XI={Xi:i∈I}\mathcal{X}_I = \{X_i : i \in I\} the set of subsets whose indices are in II.

The algorithm. We start the walk WW at a random vertex v1∈Xiv_1 \in X_i, where XiX_i is sampled uniformly at random from {X1,…,Xk}\{X_1, \ldots, X_k\}. At the beginning of step t∈[k−1]t \in[k - 1], let ItI_t be the set of indices selected so far. We will maintain that ∣It∣=t|I_t| = t, and that the walk WW intersects every subset in XIt\mathcal{X}_{I_t}. Let It‾=[k]∖It\overline{I_t} = [k] \setminus I_t, which is the set of indices not yet selected.

The walk WW currently ends at a vertex we denote as vtv_t; we can show (in Lemma 5) that the distribution of vtv_t conditional on It=JI_t = J (for some subset J⊂[k]J \subset[k]) is:

pJ[v]=∣{i∈J:v∈Xi}∣∣J∣r∀v∈V(2)p_J[v] = \frac{|\{i \in J : v \in X_i\}|}{|J|r} \qquad\forall v \in V \tag*{(2)}

(If all subsets in X\mathcal{X} are vertex-disjoint, then pJ[v]p_J[v] is simply the uniform distribution over vertices in ⋃i∈ItXi\bigcup_{i \in I_t} X_i conditional on It=JI_t = J; the distribution in Equation (2) is simply adjusted for the overlap between the subsets in XIt\mathcal{X}_{I_t}. Intuitively, we select a uniform random set Xi∈XItX_i \in\mathcal{X}_{I_t}, and then select a uniform random vertex in XiX_i.) In the next step, we want the walk WW to get to a random vertex vt+1v_{t+1} in a set in XIt‾\mathcal{X}_{\overline{I_t}}, whose indices have not been selected; vt+1v_{t+1} is distributed according to:

qJ[v]=∣{i∈J‾:v∈Xi}∣∣J‾∣r∀v∈V(3)q_J[v] = \frac{|\{i \in\overline{J} : v \in X_i\}|}{|\overline{J}|r} \qquad\forall v \in V \tag*{(3)}

which is also an adjusted uniform distribution to account for the overlap between the subsets in XIt\mathcal{X}_{I_t}. By moving from vtv_t to vt+1v_{t+1} along the shortest path πG(vt,vt+1)\pi_G(v_t,v_{t+1}), WW 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 vtv_t to vt+1v_{t+1} (sampling from their respective distributions in a correlated manner), so that E[∣πG(vt,vt+1)∣]\mathbb{E}[|\pi_G(v_t,v_{t+1})|] is small. The minimum possible expectation is exactly the Wasserstein distance, defined formally in Definition 1, between pIt[v]p_{I_t}[v] and qIt[v]q_{I_t}[v]. (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 yt∗y_t^* on VV, from which we can sample vt+1v_{t+1}. Finally, we walk from vtv_t to vt+1v_{t+1} and proceed to the next iteration. The pseudocode is given in Algorithm 1.

One iteration of the walk construction on a graph

Figure 1. One iteration of the walk construction on a graph. Each shaded subset contains r=6r = 6 vertices. The red path extends WW from vtv_t to vt+1v_{t+1}. 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 (U,dU)(U,d_U), the Wasserstein distance between two probability distributions p,q:U→[0,1]p,q:U\to[0,1] (so ∑u∈Up[u]=∑u∈Uq[u]=1\sum_{u\in U}p[u]=\sum_{u\in U}q[u]=1) with respect to dUd_U, denoted by WdU(p,q)W_{d_U}(p,q), is the solution of the following linear program.

WdU(p,q):=min⁡x∈RU×U∑u,v∈UdU(u,v)x[u,v]W_{d_U}(p,q):=\min_{x\in\mathbb{R}^{U\times U}}\sum_{u,v\in U}d_U(u,v)x[u,v]
s.t.∑v∈Ux[u,v]=p[u]∀u∈U∑u∈Ux[u,v]=q[v]∀v∈Ux≥0(4)\begin{aligned} \text{s.t.}\quad&\sum_{v\in U}x[u,v]=p[u] && \forall u\in U\\ &\sum_{u\in U}x[u,v]=q[v] && \forall v\in U\\ &x\geq0 \tag*{(4)} \end{aligned}

A simple interpretation of the Wasserstein distance in Definition 1 is this: fix a vertex u∈Uu\in U; if we move uu to vv according to the distribution:

x[u,v]∑v′∈Ux[u,v′]=x[u,v]p[u]\frac{x[u,v]}{\sum_{v'\in U}x[u,v']}=\frac{x[u,v]}{p[u]}

then the expected cost of moving from uu to a random vv is ∑v∈UdU(u,v)x[u,v]p[u]\sum_{v\in U}d_U(u,v)\frac{x[u,v]}{p[u]}. If we move from a random uu sampled from pp to a random vv sampled from qq, then the expected cost is:

∑u∈U(∑v∈UdU(u,v)x[u,v]p[u])p[u]=∑u,v∈UdU(u,v)x[u,v](5)\sum_{u\in U}\left(\sum_{v\in U}d_U(u,v)\frac{x[u,v]}{p[u]}\right)p[u]=\sum_{u,v\in U}d_U(u,v)x[u,v] \tag*{(5)}

That is, finding WdU(p,q)W_{d_U}(p,q) is equivalent to minimizing the expected distance from a random uu to a random vv, distributed according to pp and qq, respectively.

Algorithm 1 WASSERSTEINWALK(G,X:={X1,…,Xk})(G,\mathcal{X}:=\{X_1,\ldots,X_k\})

Input: a connected graph G=(V,E)G=(V,E) and subsets X1,…,Xk⊂VX_1,\ldots,X_k\subset V of size r=⌈n/k⌉r=\lceil n/k\rceil.

Output: a walk WW through GG that intersects every subset in X\mathcal{X}.

  1. sample i∈[k]i\in[k] uniformly, and sample v1∈Xiv_1\in X_i uniformly.

  2. I1←{i}I_1\leftarrow\{i\} and W←{v1}W\leftarrow\{v_1\}.

  3. for t←1t\leftarrow1 to k−1k-1 \hspace{1em} ▹vt\triangleright v_t current endpoint of WW and ItI_t indices visited up to step tt

  4. pIt[v]←∣{i∈It:v∈Xi}∣/(∣It∣⋅r)p_{I_t}[v]\leftarrow|\{i\in I_t:v\in X_i\}|/(|I_t|\cdot r) for all v∈Vv\in V \hspace{1em} ▹\triangleright distribution in Equation (2)

  5. qIt[v]←∣{i∈Iˉt:v∈Xi}∣/(∣Iˉt∣⋅r)q_{I_t}[v]\leftarrow|\{i\in\bar I_t:v\in X_i\}|/(|\bar I_t|\cdot r) for all v∈Vv\in V \hspace{1em} ▹\triangleright distribution in Equation (3)

  6. xt∗←x_t^*\leftarrow optimal solution of Equation (4) for computing Wasserstein distance WdG(pIt,qIt)W_{d_G}(p_{I_t},q_{I_t})

  7. yt∗[v]←xt∗[vt,v]∑v′∈Vxt∗[vt,v′]y_t^*[v]\leftarrow\frac{x_t^*[v_t,v]}{\sum_{v'\in V}x_t^*[v_t,v']} for all v∈Vv\in V \hspace{1em} ▹\triangleright the distribution to sample vt+1v_{t+1}

  8. sample vt+1∈Vv_{t+1}\in V according to yt∗y_t^*

  9. sample it∈{i∈Iˉt:vt+1∈Xi}i_t\in\{i\in\bar I_t:v_{t+1}\in X_i\} uniformly \hspace{1em} ▹\triangleright The walk WW will hit XitX_{i_t}

  10. It+1←It∪{it}I_{t+1}\leftarrow I_t\cup\{i_t\}

  11. W←W∘πG(vt,vt+1)W\leftarrow W\circ\pi_G(v_t,v_{t+1})

  12. 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 πG(vt,vt+1)\pi_G(v_t,v_{t+1}) at the tt-th iteration, as stated in the following lemma.

Lemma 2. At iteration t∈[k−1]t \in[k-1] of Algorithm 1,

E[∣πG(vt,vt+1)∣]≤4kψ(G)t(k−t).(6)\mathbb{E}\left[|\pi_G(v_t,v_{t+1})|\right] \le\frac{4k}{\psi(G)\sqrt{t(k-t)}}. \tag*{(6)}

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 XiX_i has exactly ⌈n/k⌉\lceil n/k\rceil vertices. Let WW be the walk from running Algorithm 1 on GG and {X1,…,Xk}\{X_1,\ldots,X_k\}. By Lemma 2:

E[∣W∣]≤4kψ(G)∑t=1k−11t(k−t)(linearity of expectation)≤4kψ(G)∫0kdxx(k−x)=4πkψ(G)(by the calculation in Equation (8) below)<13kψ(G).(7)\begin{aligned} \mathbb{E}[|W|] &\le\frac{4k}{\psi(G)}\sum_{t=1}^{k-1}\frac{1}{\sqrt{t(k-t)}} \qquad\text{(linearity of expectation)}\\ &\le\frac{4k}{\psi(G)}\int_0^k\frac{dx}{\sqrt{x(k-x)}}\\ &= \frac{4\pi k}{\psi(G)} \qquad\text{(by the calculation in Equation (8) below)}\\ &< \frac{13k}{\psi(G)}. \tag*{(7)} \end{aligned}

The second inequality is because f(x):=1/x(k−x)f(x):=1/\sqrt{x(k-x)} decreases on (0,k/2](0,k/2] and increases on [k/2,k)[k/2,k). It remains to show that

∫0kdxx(k−x)=π.\int_0^k\frac{dx}{\sqrt{x(k-x)}}=\pi.

This follows by substituting x:=ksin⁡2θx:=k\sin^2\theta where θ\theta ranges from 00 to π/2\pi/2. Since dx=2k⋅sin⁡θ⋅cos⁡θ⋅dθdx=2k\cdot\sin\theta\cdot\cos\theta\cdot d\theta and x(k−x)=ksin⁡2θ⋅kcos⁡2θ=ksin⁡θ⋅cos⁡θ\sqrt{x(k-x)}=\sqrt{k\sin^2\theta\cdot k\cos^2\theta}=k\sin\theta\cdot\cos\theta, we have

∫0kdxx(k−x)=∫0π/22ksin⁡θ⋅cos⁡θksin⁡θ⋅cos⁡θ dθ=∫0π/22 dθ=π,(8)\int_0^k\frac{dx}{\sqrt{x(k-x)}}=\int_0^{\pi/2}\frac{2k\sin\theta\cdot\cos\theta}{k\sin\theta\cdot\cos\theta}\,d\theta=\int_0^{\pi/2}2\,d\theta=\pi, \tag*{(8)}

as claimed. Finally, because E[∣W∣]<13kψ(G)\mathbb{E}[|W|]<\frac{13k}{\psi(G)}, there must exist some execution of Algorithm 1 that produces a walk with length less than 13kψ(G)\frac{13k}{\psi(G)}.

Wasserstein distance and vertex expansion

This section proves the following lemma, which bounds the Wasserstein distance between pp and qq in terms of ∥p−q∥2\lVert p-q\rVert_2 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 G=(V,E)G=(V,E) be a connected graph on nn vertices with shortest-path metric dGd_G. If p,q:V→[0,1]p,q:V\to[0,1] are probability distributions, then

WdG(p,q)≤4n⋅∥p−q∥2ψ(G).(9)W_{d_G}(p,q)\le\frac{4\sqrt{n}\cdot\lVert p-q\rVert_2}{\psi(G)}. \tag*{(9)}

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 WdG(p,q)W_{d_G}(p,q) in Equation (4) so long as the weights dU(u,v)d_U(u,v) satisfy the triangle inequality, and it can be stated in the following form for finite metrics.

Lemma 4 (Kantorovich–Rubinstein dual, alternative form [17 Equation (6.2)]).

Wd(p,q)=max⁡f∈RU∑u∈U[p[u]−q[u]]fuW_d(p,q)=\max_{f\in\mathbb{R}^U}\sum_{u\in U}[p[u]-q[u]]f_u

s.t. ∣fu−fv∣≤dU(u,v)∀u,v∈U|f_u-f_v|\le d_U(u,v)\quad\forall u,v\in U.

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 G=(V,E)G=(V,E) be a connected graph on nn vertices with shortest-path metric dGd_G. If f∈RVf\in\mathbb{R}^V satisfies ∣fu−fv∣≤dG(u,v)|f_u-f_v|\le d_G(u,v) for all u,v∈Vu,v\in V, then

∑v∈V(fv−f‾)2≤2n(1+ψ(G)−1)2,where f‾:=1n∑v∈Vfv.\sum_{v\in V}(f_v-\overline{f})^2\le\frac{2n}{\left(\sqrt{1+\psi(G)}-1\right)^2},\qquad\text{where }\overline{f}:=\frac{1}{n}\sum_{v\in V}f_v.

Proof of Lemma 3. Let ff be an optimal solution of the dual program in Lemma 4 where the metric is (V,dG)(V,d_G). We have WdG(p,q)=∑v∈V(pv−qv)fvW_{d_G}(p,q)=\sum_{v\in V}(p_v-q_v)f_v and ∣fu−fv∣≤dG(u,v)|f_u-f_v|\le d_G(u,v) for every u,v∈Vu,v\in V. By Theorem 3:

∑v∈V(fv−f‾)2≤2n(1+ψ(G)−1)2=2n⋅(1+ψ(G)+1)2((1+ψ(G)−1)(1+ψ(G)+1))2=2n⋅(1+ψ(G)+1)2((1+ψ(G))−1)2≤2n⋅(3+1)2ψ(G)2(since ψ(G)≤2)<16nψ(G)2.(10)\begin{aligned} \sum_{v\in V}(f_v-\overline{f})^2\le\frac{2n}{\left(\sqrt{1+\psi(G)}-1\right)^2} \\ &=\frac{2n\cdot\left(\sqrt{1+\psi(G)}+1\right)^2}{\left((\sqrt{1+\psi(G)}-1)(\sqrt{1+\psi(G)}+1)\right)^2} \\ &=\frac{2n\cdot\left(\sqrt{1+\psi(G)}+1\right)^2}{\left((1+\psi(G))-1\right)^2} \\ &\le\frac{2n\cdot(\sqrt{3}+1)^2}{\psi(G)^2}\qquad\text{(since }\psi(G)\le2\text{)} \\ &<\frac{16n}{\psi(G)^2}. \tag*{(10)} \end{aligned}

Since ∑v∈Vp[v]=∑v∈Vq[v]=1\sum_{v\in V}p[v]=\sum_{v\in V}q[v]=1, we have ∑v∈V(p[v]−q[v])⋅f‾=0\sum_{v\in V}(p[v]-q[v])\cdot\overline{f}=0. Therefore,

WdG(p,q)=∑v∈V[p[v]−q[v]]fv=∑v∈V[p[v]−q[v]](fv−f‾)≤∥p−q∥2⋅(∑v∈V(fv−f‾)2)1/2(by Cauchy-Schwarz)≤4n⋅∥p−q∥2ψ(G)(by Equation (11))\begin{aligned} W_{d_G}(p,q)=\sum_{v\in V}[p[v]-q[v]]f_v \\ &=\sum_{v\in V}[p[v]-q[v]](f_v-\overline{f}) \\ &\le\lVert p-q\rVert_2\cdot\left(\sum_{v\in V}(f_v-\overline{f})^2\right)^{1/2}\qquad\text{(by Cauchy-Schwarz)} \\ &\le\frac{4\sqrt{n}\cdot\lVert p-q\rVert_2}{\psi(G)}\qquad\text{(by Equation (11))} \end{aligned}

as claimed. □

Bounding the expected distance

In this subsection, we prove Lemma 2. First, we show that ItI_t is uniformly distributed over the size-tt subsets of [k][k], and that conditional on It=JI_t=J, the endpoint vtv_t has distribution pJp_J. All the probabilities and expectations are over the random choices of the algorithm.

Lemma 5. For every t∈[k−1]t \in[k-1] and every size-tt-subset J⊂[k]J \subset[k], and every vertex a∈Va \in V,

Pr⁡[It=J]=1(kt)andPr⁡[vt=a∣It=J]=∣{i∈J:a∈Xi}∣t⋅r.\Pr[I_t=J]=\frac{1}{\binom{k}{t}} \qquad\text{and}\qquad \Pr[v_t=a\mid I_t=J]=\frac{|\{i\in J:a\in X_i\}|}{t\cdot r}.

Proof. We proceed by induction on tt. The base case t=1t=1 holds by lines 1 and 2 of Algorithm 1. Now assume that t<k−1t<k-1 and that the claim holds for tt. By induction hypothesis, vtv_t is distributed according to pJp_J. Algorithm 1 constructs a coupling between the distributions pJp_J and qJq_J and uses this to sample vt+1v_{t+1}, so vt+1v_{t+1} has distribution qJq_J: formally,

Pr⁡[vt+1=b∣It=J]=∑a∈VXt∗[a,b]=qJ[b]for all b∈V.\Pr[v_{t+1}=b\mid I_t=J]=\sum_{a\in V}X_t^*[a,b]=q_J[b]\qquad\text{for all }b\in V.

Now, notice that (conditional on It=JI_t=J) the algorithm first samples vt+1v_{t+1} according to qJq_J, and then samples iti_t uniformly at random among {i∈[k]∖J:vt+1∈Xi}\{i\in[k]\setminus J:v_{t+1}\in X_i\}. This leads to a key observation: for any i∈[k]∖Ji\in[k]\setminus J and b∈Xib\in X_i,

Pr⁡[it=i∧vt+1=b∣It=J]=qJ[b]⋅1∣{i∈[k]∖J:b∈Xi}∣=1(k−t)r.(11)\Pr[i_t=i\wedge v_{t+1}=b\mid I_t=J]=q_J[b]\cdot\frac{1}{|\{i\in[k]\setminus J:b\in X_i\}|}=\frac{1}{(k-t)r}. \tag*{(11)}

Part 1 of the claim. We prove that It+1I_{t+1} is uniformly distributed. First observe that (conditional on It=JI_t=J), the next selected index iti_t is uniformly distributed among [k]∖J[k]\setminus J. Indeed, we can sum (11) over the rr vertices of XiX_i:

Pr⁡[it=i∣It=J]=∑b∈XiPr⁡[it=i∧vt+1=b∣It=J]=1k−t.\Pr[i_t=i\mid I_t=J]=\sum_{b\in X_i}\Pr[i_t=i\wedge v_{t+1}=b\mid I_t=J]=\frac{1}{k-t}.

The first part of the claim now follows: if we start with ItI_t as a uniform random tt-element subset of [k][k] (which we do, by induction), and add a uniformly random element in [k]∖It[k]\setminus I_t to form It+1I_{t+1}, the set It+1I_{t+1} is a uniformly random (t+1)(t+1)-element subset of [k][k]. That is, Pr⁡[It+1=J′]=1(kt+1)\Pr[I_{t+1}=J']=\frac{1}{\binom{k}{t+1}} for any size-(t+1)(t+1) subset J′⊆[k]J'\subseteq[k].6

Part 2 of the claim. We prove that the distribution of vt+1v_{t+1} has the desired form. Let J′⊂[k]J'\subset[k] be a size-(t+1)(t+1) subset of [k][k] and let a∈Va\in V. Observe that

Pr⁡[It+1=J′∧vt+1=a]=∑i∈J′a∈XiPr⁡[It=J′∖{i}∧vt+1=a∧it=i]\Pr[I_{t+1}=J'\wedge v_{t+1}=a] =\sum_{\substack{i\in J'\\a\in X_i}}\Pr[I_t=J'\setminus\{i\}\wedge v_{t+1}=a\wedge i_t=i]
=∑i∈J′a∈Xi1(kt)⋅1(k−t)⋅r=∣{i∈J′:a∈Xi}∣(kt)⋅(k−t)⋅r.=\sum_{\substack{i\in J'\\a\in X_i}}\frac{1}{\binom{k}{t}}\cdot\frac{1}{(k-t)\cdot r} =\frac{|\{i\in J':a\in X_i\}|}{\binom{k}{t}\cdot(k-t)\cdot r}.

where the second-to-last equality follows from (11). Hence

Pr⁡[vt+1=a∣It+1=J′]=Pr⁡[It+1=J′∧vt+1=a]Pr⁡[It+1=J′]\Pr[v_{t+1}=a\mid I_{t+1}=J'] =\frac{\Pr[I_{t+1}=J'\wedge v_{t+1}=a]}{\Pr[I_{t+1}=J']}
=∣{i∈J′:a∈Xi}∣(kt)⋅(k−t)⋅r⋅(kt+1)=\frac{|\{i\in J':a\in X_i\}|}{\binom{k}{t}\cdot(k-t)\cdot r}\cdot\binom{k}{t+1}
=∣{i∈J′:a∈Xi}∣(t+1)⋅r=\frac{|\{i\in J':a\in X_i\}|}{(t+1)\cdot r}

as claimed. □

Now we prove Lemma 2 restated below.

Lemma 2. At iteration t∈[k−1]t \in[k-1] of Algorithm 1,

E[∣πG(vt,vt+1)∣]≤4kψ(G)t(k−t).(12)\mathbb{E}\left[\left|\pi_G(v_t,v_{t+1})\right|\right] \le\frac{4k}{\psi(G)\sqrt{t(k-t)}}. \tag*{(12)}

Here the expectation is over the random choices of the algorithm.

Proof: By Lemma 5, given It=JI_t=J, we have vt=av_t=a with probability pJ[a]p_J[a]. Then in line 8, we sample vt+1v_{t+1} and:

Pr⁡[vt+1=b∣It=J∧vt=a]=xt∗[a,b]∑vxt∗[a,v]=xt∗[a,b]pJ[a].(13)\Pr[v_{t+1}=b\mid I_t=J\wedge v_t=a]=\frac{x_t^*[a,b]}{\sum_v x_t^*[a,v]}=\frac{x_t^*[a,b]}{p_J[a]}. \tag*{(13)}

Then, we have:

E[dG(vt,vt+1)∣It=J]=∑a,b∈VdG(a,b)⋅pJ[a]⋅xt∗[a,b]pJ[a]=WdG(pJ,qJ)≤4n⋅∥pJ−qJ∥2ψ(G)(by Lemma 3)(14)\begin{aligned} \mathbb{E}[d_G(v_t,v_{t+1})\mid I_t=J] &=\sum_{a,b\in V}d_G(a,b)\cdot p_J[a]\cdot\frac{x_t^*[a,b]}{p_J[a]}\\ &=W_{d_G}(p_J,q_J)\\ &\le\frac{4\sqrt{n}\cdot\lVert p_J-q_J\rVert_2}{\psi(G)} \qquad\text{(by Lemma 3)} \tag*{(14)} \end{aligned}

By averaging over ItI_t (rather than conditioning on It=JI_t=J), we get:

E[dG(vt,vt+1)]≤4nψ(G)⋅E[∥pIt−qIt∥2]≤4nψ(G)⋅E[∥pIt−qIt∥22](by Jensen’s inequality)(15)\begin{aligned} \mathbb{E}[d_G(v_t,v_{t+1})] &\le\frac{4\sqrt{n}}{\psi(G)}\cdot\mathbb{E}\left[\lVert p_{I_t}-q_{I_t}\rVert_2\right]\\ &\le\frac{4\sqrt{n}}{\psi(G)}\cdot\sqrt{\mathbb{E}\left[\lVert p_{I_t}-q_{I_t}\rVert_2^2\right]} \qquad\text{(by Jensen’s inequality)} \tag*{(15)} \end{aligned}

Now we focus on bounding E[∥pIt−qIt∥22]\mathbb{E}\left[\lVert p_{I_t}-q_{I_t}\rVert_2^2\right]. To this end, for each i∈[k]i\in[k], let σi:=1/t\sigma_i:=1/t if i∈Iti\in I_t and σi:=−1/(k−t)\sigma_i:=-1/(k-t) otherwise. Then by the definition of pItp_{I_t} and qItq_{I_t} in Equations (2) and (3), for every v∈Vv\in V,

pIt[v]−qIt[v]=1t∑i:v∈Xiσi.(16)p_{I_t}[v]-q_{I_t}[v]=\frac{1}{t}\sum_{i:v\in X_i}\sigma_i. \tag*{(16)}

By Lemma 5, ItI_t is a uniformly random size-tt subset of [k][k], so each i∈[k]i\in[k] lies in ItI_t with probability t/kt/k, and

E[σi2]=tk⋅1t2+k−tk⋅1(k−t)2=1tk+1k(k−t)=1t(k−t).(17)\mathbb{E}[\sigma_i^2]=\frac{t}{k}\cdot\frac{1}{t^2}+\frac{k-t}{k}\cdot\frac{1}{(k-t)^2}=\frac{1}{tk}+\frac{1}{k(k-t)}=\frac{1}{t(k-t)}. \tag*{(17)}

For distinct i,i′∈[k]i,i'\in[k], considering whether both, neither or exactly one of ii and i′i' lie in ItI_t gives

E[σiσi′]=t(t−1)k(k−1)⋅1t2+(k−t)(k−t−1)k(k−1)⋅1(k−t)2−2t(k−t)k(k−1)⋅1t(k−t)=1k(k−1)(t−1t+k−t−1k−t−2)=−1k(k−1)(1t+1k−t)<0.(18)\begin{aligned} \mathbb{E}[\sigma_i\sigma_{i'}] &=\frac{t(t-1)}{k(k-1)}\cdot\frac{1}{t^2} +\frac{(k-t)(k-t-1)}{k(k-1)}\cdot\frac{1}{(k-t)^2} -\frac{2t(k-t)}{k(k-1)}\cdot\frac{1}{t(k-t)}\\ &=\frac{1}{k(k-1)}\left(\frac{t-1}{t}+\frac{k-t-1}{k-t}-2\right) =-\frac{1}{k(k-1)}\left(\frac{1}{t}+\frac{1}{k-t}\right)<0. \tag*{(18)} \end{aligned}

By Equation (16), we get

E[∥pIt−qIt∥22]=1r2∑v∈VE[(∑i:v∈Xiσi)2]=1r2∑v∈V∑i,i′:v∈Xi∩Xi′E[σiσi′]≤1r2∑v∈V∑i:v∈XiE[σi2](by xref‘Equation (18)‘)=1r2∑i∈[k]E[σi2]⋅∣Xi∣=1r2⋅k⋅1t(k−t)⋅r(by xref‘Equation (17)‘)=kt(k−t)⋅r.(19)\begin{aligned} \mathbb{E}\left[\lVert p_{I_t}-q_{I_t}\rVert_2^2\right] = \frac{1}{r^2}\sum_{v\in V}\mathbb{E}\left[\left(\sum_{i:v\in X_i}\sigma_i\right)^2\right] = \frac{1}{r^2}\sum_{v\in V}\sum_{i,i':v\in X_i\cap X_{i'}}\mathbb{E}[\sigma_i\sigma_{i'}] \\ &\le\frac{1}{r^2}\sum_{v\in V}\sum_{i:v\in X_i}\mathbb{E}[\sigma_i^2]\qquad\text{(by {xref}`Equation (18)`)} \\ &= \frac{1}{r^2}\sum_{i\in[k]}\mathbb{E}[\sigma_i^2]\cdot|X_i| \\ &= \frac{1}{r^2}\cdot k\cdot\frac{1}{t(k-t)}\cdot r\qquad\text{(by {xref}`Equation (17)`)} \\ &= \frac{k}{t(k-t)\cdot r}. \tag*{(19)} \end{aligned}

Plugging Equation (19) into Equation (15), we get:

E[dG(vt,vt+1)]≤4nψ(G)⋅kt(k−t)⋅r≤4k⋅rψ(G)⋅kt(k−t)⋅rsince r≥n/k=4kψ(G)t(k−t).\begin{aligned} \mathbb{E}[d_G(v_t,v_{t+1})]\le\frac{4\sqrt{n}}{\psi(G)}\cdot\sqrt{\frac{k}{t(k-t)\cdot r}} \\ &\le\frac{4\sqrt{k\cdot r}}{\psi(G)}\cdot\sqrt{\frac{k}{t(k-t)\cdot r}}\qquad\text{since }r\ge n/k \\ &= \frac{4k}{\psi(G)\sqrt{t(k-t)}}. \end{aligned}

as claimed. □

The Algorithm

For a subgraph HH of GG and a set of vertices AA of GG, let ∂HA\partial_H A denote the set of vertices of HH that are not in AA but have at least one neighbor in AA. We note that AA might not belong to V(H)V(H); for example, when HH is a subgraph of a larger graph GG and A⊆V(G)A\subseteq V(G) that is not in HH. When A⊆V(H)A\subseteq V(H), we use the notation BH(A,r)B_H(A,r) to denote the ball of radius rr around AA in HH, that is, {v∈V(H):dH(A,v)≤r}\{v\in V(H):d_H(A,v)\le r\}. We will use the following corollary of Theorem 2.

Corollary 1. Suppose that HH is a ψ\psi-vertex expander. Let X={X1,X2,…,Xk}\mathcal{X}=\{X_1,X_2,\ldots,X_k\} be a collection of kk vertex subsets of V(H)V(H) such that ∣Xi∣≥∣V(H)∣/h|X_i|\ge|V(H)|/h and k≤hk\le h. Then there is a procedure SHORTTREE(H, X) that produces a tree T⊆HT\subseteq H such that:

  1. T∩Xi≠∅T\cap X_i\ne\varnothing for every i∈[k]i\in[k].

  2. ∣V(T)∣≤⌈13h/ψ⌉|V(T)|\le\lceil13h/\psi\rceil.

Proof. If k=hk=h, then we can apply Theorem 2 to produce a walk WW, and we can then simply take TT to be a spanning tree of H[V(W)]H[V(W)]. As WW has length strictly less than 13h/ψ13h/\psi, the tree TT has at most ⌈13h/ψ⌉\lceil13h/\psi\rceil vertices. If k<hk<h, then we duplicate XkX_k to get X+={X1,…,Xk,Xk+1=Xk,…,Xh=Xk}\mathcal{X}^{+}=\{X_1,\ldots,X_k,X_{k+1}=X_k,\ldots,X_h=X_k\} and apply Theorem 2 to HH and X+\mathcal{X}^{+}. □

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: HH, X\mathcal{X} and K\mathcal{K}.

  1. HH is an induced subgraph of GG. Except when the algorithm terminates, HH contains at least 3n/43n/4 vertices. One should think of the “current separator” as ∂GH\partial_G H, and HH as the largest connected component7 of GG if we remove ∂GH\partial_G H from GG.

The “current separator” ∂GH\partial_G H will lie in the union of two objects:

  1. X\mathcal{X} is a subset of vertices of GG which the algorithm will keep adding to. We guarantee that ∣X∣≤O(hn)|\mathcal{X}| \le O(h\sqrt{n}).

  1. K\mathcal{K} is a clique minor model found so far, whose branch sets of K\mathcal{K} are disjoint from HH. We guarantee that, for every C∈KC \in\mathcal{K}, we have ∣∂GH∩C∣≤O(n)|\partial_G H \cap C| \le O(\sqrt{n}).

It will hold that X\mathcal{X} and V(K)V(\mathcal{K}) are disjoint from V(H)V(H). See Figure 2.

Figure 2. The subgraph HH. The boundary of HH is contained in the union of X\mathcal{X} (drawn in orange) and the vertices of the K3K_3 minor model {C1,C2,C3}=K\{C_1,C_2,C_3\} = \mathcal{K}.

In every step, the algorithm removes at least one vertex from HH and at most n/2n/2 vertices from HH, adding them to X\mathcal{X} or V(K)V(\mathcal{K}). The algorithm terminates when the size of HH drops below 3n/43n/4, at which point we return ∂GH\partial_G H as the separator.8 Because each step removes at most n/2n/2 vertices, we have n/4≤∣H∣≤3n/4n/4 \le|H| \le3n/4 and thus ∂GH\partial_G H is a balanced separator. To guarantee that ∂GH\partial_G H has size O(hn)O(h\sqrt{n}), we maintain the invariant that ∂GH⊆X∪V(K)\partial_G H \subseteq\mathcal{X} \cup V(\mathcal{K}), that ∣X∣≤O(hn)|\mathcal{X}| \le O(h\sqrt{n}), and that for each branch set C∈KC \in\mathcal{K} we have ∣C∩∂GH∣≤O(n)|C \cap\partial_G H| \le O(\sqrt{n}) (recall that KhK_h-minor-freeness implies that K\mathcal{K} contains at most h−1h-1 branch sets).

Each iteration of the algorithm proceeds as follows. At the start, the algorithm checks whether any connected component of HH has ≥3n/4\ge3n/4 vertices. If not, we terminate and return the current separator ∂GH\partial_G H; otherwise we update HH to be the largest connected component, update K\mathcal{K} by discarding all branch sets that aren’t adjacent to HH, and proceed. Within each iteration, there are three cases; see Figure 3.

The three cases possible in each step of the algorithm

Figure 3. The three cases possible in each step of the algorithm

  • Case 1: HH is not a h/nh/\sqrt{n}-vertex expander.

    By the definition of a vertex expander, there must be a subset of vertices AA such that ∣∂HA∣≤h/n∣A∣|\partial_H A| \le h/\sqrt{n}|A| and ∣A∣≤∣V(H)∣/2|A| \le|V(H)|/2 (the smaller side of the sparse cut). We will update X\mathcal{X} by adding ∂HA\partial_H A to X\mathcal{X}, and removing ∂HA\partial_H A from HH. We can afford adding ∂HA\partial_H A to X\mathcal{X} since we can charge the size of ∂HA\partial_H A to AA. Each vertex gets h/nh/\sqrt{n} charge over the entire process, since AA will be removed from HH (once HH is reassigned to the largest connected component) and so over the entire course of the algorithm, the size of X\mathcal{X} is bounded by (h/n)n=hn(h/\sqrt{n})n = h\sqrt{n}.

  • Case 2: There exists branch set C∈KC \in\mathcal{K} and r≥1r \ge1 with ∣BH(∂HC,r)∣≤n/2|B_H(\partial_H C,r)| \le n/2 and ∣∂HBH(∂HC,r−1)∣≤n|\partial_H B_H(\partial_H C,r-1)| \le\sqrt{n}.

    Then we simply grow CC by adding the entire ball BH(∂HC,r)B_H(\partial_H C,r) to CC, and (correspondingly) deleting BH(∂HC,r)B_H(\partial_H C,r) from HH. This step could blow up the size of CC significantly (up to Ω(n)\Omega(n)). However, since ∣∂HBH(∂HC,r−1)∣≤n|\partial_H B_H(\partial_H C,r-1)| \le\sqrt{n}, after the update we still have that ∣C∩∂GH∣≤n|C \cap\partial_G H| \le\sqrt{n}. The condition ∣BH(∂HC,r)∣≤n/2|B_H(\partial_H C,r)| \le n/2 just guarantees that we remove at most n/2n/2 vertices from HH in this step.

  • Case 3: Otherwise.

    In this case, (i) HH is an h/nh/\sqrt{n}-vertex expander, and (ii) for every branch set C∈KC \in\mathcal{K} and radius r≥1r \ge1, either ∣BH(∂HC,r)∣>n/2|B_H(\partial_H C,r)| > n/2 or ∣∂HBH(∂HC,r−1)∣>n|\partial_H B_H(\partial_H C,r-1)| > \sqrt{n}. If we pick r∗=⌈n/h⌉r^* = \lceil\sqrt{n}/h \rceil, we can show (Claim 1) that ∣BH(∂HC,r∗)∣>n/h|B_H(\partial_H C,r^*)| > n/h. We can now form X←{BH(∂HC,r∗)}C∈K\mathcal{X} \leftarrow\{B_H(\partial_H C,r^*)\}_{C \in\mathcal{K}} and apply Corollary 1 to get a tree TT of size O(n)O(\sqrt{n}) that intersects every set in X\mathcal{X}. We then extract TT so that it is adjacent to every branch set in K\mathcal{K}: for every branch set C∈KC \in\mathcal{K}, we pick an arbitrary vertex xC∈T∩BH(∂HC,r∗)x_C \in T \cap B_H(\partial_H C,r^*), and add to TT the shortest path in HH from xCx_C to a vertex in ∂HC\partial_H C. Note that since r∗=⌈n/h⌉r^* = \lceil\sqrt{n}/h \rceil and ∣K∣≤h|\mathcal{K}| \le h, the total size of all the paths added to TT is at most hr∗=O(n)hr^* = O(\sqrt{n}), so the total size of (a new branch set) TT formed in this step is still O(n)O(\sqrt{n}). We add TT to K\mathcal{K}, and remove TT from HH.

In summary, the algorithm guarantees that ∣X∣=O(hn)|\mathcal{X}| = O(h\sqrt{n}) (Case 1) and for every branch set C∈KC \in\mathcal{K}, either ∣∂GH∩C∣≤n|\partial_G H \cap C| \le\sqrt{n} (Case 2) or directly that ∣C∣=O(n)|C| = O(\sqrt{n}) (Case 3). Moreover, the current separator ∂GH\partial_G H is in X∪V(K)\mathcal{X} \cup V(\mathcal{K}). Since ∣K∣≤h|\mathcal{K}| \le h, the size of the current separator is always O(hn)O(h\sqrt{n}). Once ∣V(H)∣≤3n/4|V(H)| \le3n/4, the current separator is balanced and we simply return it.

Algorithm 2 BALANCEDSEPARATOR(GG) ▷ Find a balanced separator of size O(hn)O(h\sqrt{n})

  1. K←∅\mathcal{K} \gets\varnothing, X←∅X \gets\varnothing, H←GH \gets G

  2. while there is some connected component of HH with ≥3n/4\ge3n/4 vertices do

  3. H←H \gets largest connected component of HH

  4. K←{C∈K:C\mathcal{K} \gets\{C \in\mathcal{K} : C has a neighbor in H}H\}

  5. if HH is not a h/nh/\sqrt{n}-vertex expander then ▷ Case 1

  6. A←A \gets nonempty subset of V(H)V(H) such that ∣A∣≤n/2|A| \le n/2 and ∣∂HA∣≤hn∣A∣|\partial_H A| \le\frac{h}{\sqrt{n}}|A|

  7. X←X∪∂HAX \gets X \cup\partial_H A.

  8. H←H∖∂HAH \gets H \setminus\partial_H A

  9. else if there exists C∈KC \in\mathcal{K} and r≥1r \ge1 with ∣BH(∂HC,r)∣≤n/2|B_H(\partial_H C,r)| \le n/2 and ∣∂HBH(∂HC,r−1)∣≤n|\partial_H B_H(\partial_H C,r-1)| \le\sqrt{n} then ▷ Case 2

  10. B←BH(∂HC,r)B \gets B_H(\partial_H C,r)

  11. C←C∪BC \gets C \cup B.

  12. H←H∖BH \gets H \setminus B

  13. else ▷ ∀C∈K,∀r≥1\forall C \in\mathcal{K},\forall r \ge1: ∣BH(∂HC,r)∣>n/2|B_H(\partial_H C,r)| > n/2 or ∣∂HBH(∂HC,r−1)∣>n|\partial_H B_H(\partial_H C,r-1)| > \sqrt{n} ▷ Case 3

  14. if K=∅\mathcal{K} = \varnothing then

  15. T←T \gets an arbitrary vertex in V(H)V(H)

  16. else

  17. r∗←⌈n/h⌉r^* \gets\lceil\sqrt{n}/h\rceil

  18. X←{BH(∂HC,r∗)}C∈K\mathcal{X} \gets\{B_H(\partial_H C,r^*)\}_{C\in\mathcal{K}} ▷ Claim 1 shows that ∣BH(∂HC,r∗)∣≥n/h|B_H(\partial_H C,r^*)| \ge n/h.

  19. T←SHORTTREE⁡(H,X)T \gets\operatorname{SHORTTREE}(H,\mathcal{X})

  20. for every C∈KC \in\mathcal{K} do

  21. xC←x_C \gets a vertex in T∩BH(∂HC,r∗)T \cap B_H(\partial_H C,r^*)

  22. πxC←\pi_{x_C} \gets a shortest path in HH from xCx_C to a vertex in ∂HC\partial_H C ▷ πxC\pi_{x_C} exists because HH is connected.

  23. T←T∪πxCT \gets T \cup\pi_{x_C} ▷ this makes TT adjacent to C∈KC \in\mathcal{K}.

  24. K←K∪{T}\mathcal{K} \gets\mathcal{K} \cup\{T\}

  25. H←H∖V(T)H \gets H \setminus V(T)

  26. return ∂GH\partial_G H

We now turn to the analysis. First, we show that every set BH(∂HC,r∗)∈XB_H(\partial_H C,r^*) \in\mathcal{X} in line 18 has size at least n/hn/h. This justifies the call to SHORTTREE⁡(H,X)\operatorname{SHORTTREE}(H,\mathcal{X}) in line 19.

Claim 1. Let C∈KC \in\mathcal{K} be a branch set such that for every r≥1r \ge1, either ∣BH(∂HC,r)∣>n/2|B_H(\partial_H C,r)| > n/2 or ∣∂HBH(∂HC,r−1)∣>n|\partial_H B_H(\partial_H C,r-1)| > \sqrt{n}.

Then

∣BH(∂HC,r∗)∣≥n/h≥∣V(H)∣/h(20)\lvert B_H(\partial_H C,r^*)\rvert\ge n/h \ge\lvert V(H)\rvert/h \tag*{(20)}

where r∗=⌈n/h⌉r^*=\lceil\sqrt{n}/h\rceil. Consequently, (H,X)(H,\mathcal{X}) is a valid input to the SHORTTREE procedure on line 19.

Proof: If there exists r∈[0,r∗]r \in[0,r^*] such that ∣BH(∂HC,r)∣≥n/h\lvert B_H(\partial_H C,r)\rvert\ge n/h, then the claim holds, as BH(∂HC,r)⊆BH(∂HC,r∗)B_H(\partial_H C,r) \subseteq B_H(\partial_H C,r^*). Otherwise, by assumption, for r∈[0,r∗−1]r \in[0,r^*-1] we have that ∣∂HBH(∂HC,r)∣>n\lvert\partial_H B_H(\partial_H C,r)\rvert> \sqrt{n}. Observing that BH(∂HC,r∗)B_H(\partial_H C,r^*) contains ∂HBH(∂HC,r)\partial_H B_H(\partial_H C,r) for every r∈[0,r∗−1]r \in[0,r^*-1], we conclude

∣BH(∂HC,r∗)∣≥∑r=0r∗−1∣∂HBH(∂HC,r)∣>r∗n≥n/h\lvert B_H(\partial_H C,r^*)\rvert\ge\sum_{r=0}^{r^*-1}\lvert\partial_H B_H(\partial_H C,r)\rvert> r^*\sqrt{n} \ge n/h

as claimed. Thus, when we call SHORTTREE(H,X)(H,\mathcal{X}) in line 19, it holds that every X∈XX \in\mathcal{X} has ∣X∣≥∣V(H)∣/h\lvert X\rvert\ge\lvert V(H)\rvert/h and that HH is an h/nh/\sqrt{n}-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(G)(G) terminates.

Proof: It suffices to show that every iteration of the while loop removes at least one vertex from HH. Indeed, in Case 1, we remove some nonempty subset ∂HA\partial_H A from HH. In Case 2, we remove some ball BH(∂HC,r)B_H(\partial_H C,r) from HH; this ball is nonempty because it contains ∂HC\partial_H C, which is nonempty because (due to the trimming in line 4) CC has some neighbor in HH. In Case 3, we remove the nonempty set TT from HH. □

We record two simple invariants.

Lemma 7. At the start of every iteration, the following properties hold:

  1. K\mathcal{K} is a clique minor model in GG (of size ∣K∣\lvert\mathcal{K}\rvert). Thus ∣K∣<h\lvert\mathcal{K}\rvert< h.

  2. V(H)V(H) and V(K)V(\mathcal{K}) are disjoint.

Proof: In the beginning of the algorithm, we have K=∅\mathcal{K}=\varnothing, X=∅\mathcal{X}=\varnothing, and H=GH=G, and so the invariants are satisfied trivially.

  1. By induction, assume that K\mathcal{K} is a model of a clique minor in GG 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 K\mathcal{K} during one of the three cases of the algorithm. In Case 1, K\mathcal{K} is unchanged. In Case 2, some C∈KC \in\mathcal{K} is expanded (line 11) to include additional vertices in V(H)V(H). But CC remains disjoint from the other branch sets after the expansion (because, by induction, HH was disjoint from the other branch sets), CC remains adjacent to all other branch sets, and CC remains connected; thus K\mathcal{K} remains a clique minor model. Finally, in Case 3, a new branch set TT is added. If TT is a singleton added by line 15 then the claim holds. In the nontrivial case (lines 17–23), the branch set TT is disjoint from the other C∈KC \in\mathcal{K} because V(T)⊆V(H)V(T) \subseteq V(H) and V(H)V(H) is disjoint from the other branch sets; moreover, TT is adjacent to every other branch set C∈KC \in\mathcal{K} because we added the path πXC\pi_{XC} to TT in line 23.

  1. By induction, assume V(K)V(\mathcal{K}) and V(H)V(H) are disjoint at the start of the current iteration. In this iteration, the set V(H)V(H) shrinks, and some vertices may be added to V(K)V(\mathcal{K}). It suffices to show that every vertex added to V(K)V(\mathcal{K}) in the iteration is removed from V(H)V(H). Indeed, in Case 1, no new vertices are added to V(K)V(\mathcal{K}); in Case 2, the ball B=BH(∂HC,r)B=B_H(\partial_H C,r) is added to V(K)V(\mathcal{K}) and removed from V(H)V(H); and in Case 3, the vertices of the new branch set TT are added to V(K)V(\mathcal{K}) and removed from V(H)V(H). □

We can now prove that the algorithm produces a separator of size O(hn)O(h\sqrt{n}) (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 ∣∂GH∣≤16hn\lvert\partial_G H\rvert\le16h\sqrt{n}. This is a consequence of the following invariants:

  1. ∂GH⊆X∪V(K)\partial_G H \subseteq X \cup V(\mathcal{K})

  1. ∣X∣≤hn|X| \le h\sqrt{n}

  1. For every C∈KC \in\mathcal{K}, we have ∣∂GH∩C∣≤15n|\partial_G H \cap C| \le15\sqrt{n}

Proof: Given the invariants, we can conclude that ∣∂GH∣≤∣X∣+∣∂GH∩V(K)∣≤hn+(h−1)⋅15n≤16hn|\partial_G H| \le|X| + |\partial_G H \cap V(\mathcal{K})| \le h\sqrt{n} + (h - 1)\cdot15\sqrt{n} \le16h\sqrt{n}, where the second-to-last inequality follows from the fact that ∣K∣≤h−1|\mathcal{K}| \le h - 1 (by Lemma 7(1)). It remains to prove the invariants.

  1. We proceed by induction. Assume that ∂GH⊆X∪V(K)\partial_G H \subseteq X \cup V(\mathcal{K}) holds at the start of the while loop (line 3). Observe that for any connected component H′H' of HH, we have ∂GH′⊆∂GH\partial_G H' \subseteq\partial_G H; thus the claim holds after line 3 (when the largest connected component of HH is renamed as HH), and it also holds trivially after line 4 (when all branch sets not adjacent to HH are discarded). In lines 5–25, in each of the three cases HH is modified in the following way: some set of vertices is added to X∪V(K)X \cup V(\mathcal{K}), and these same vertices are removed from HH. When removing a vertex vv from HH, the only possible new vertex that could be added to ∂GH\partial_G H is vv itself. Thus, after each iteration it remains the case that ∂GH⊆X∪V(K)\partial_G H \subseteq X \cup V(\mathcal{K}).

  1. We prove ∣X∣≤hn|X| \le h\sqrt{n} by a charging argument. Note that we only add to XX in line 7: whenever we add ∂HA\partial_H A to XX, we charge the size of ∂HA\partial_H A to ∣A∣|A|. Each vertex in AA gets at most h/nh/\sqrt{n} charge. Now we argue that vertices of A⊂V(H)A \subset V(H) will not be charged again in future iterations. Indeed, after we delete ∂HA\partial_H A from HH in this iteration, any connected component that intersects AA (and is therefore fully contained in AA) contains at most n/2n/2 vertices. But if the algorithm continues, it reassigns HH (in line 3) to be some connected component with at least 3n/43n/4 vertices. Thus vertices in AA are never charged again, and the total size of XX over all iterations is at most (h/n)n=hn(h/\sqrt{n})n = h\sqrt{n}.

  1. At the start of the algorithm, we have K=∅\mathcal{K} = \varnothing 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 HH can change, (2) some set C∈KC \in\mathcal{K} may be modified in Case 2, or (3) a new set C∈KC \in\mathcal{K} may be created in Case 3. We claim that after any of these changes, the claim still holds.

For the first, observe that HH only shrinks over the course of the algorithm (i.e., HH is changed to be some subgraph of itself). As every C∈KC \in\mathcal{K} is disjoint from HH (by Lemma 7(2)), shrinking HH can only cause the set ∂GH∩C\partial_G H \cap C to shrink.

For the second, suppose that Case 2 selects some ball Br=BH(∂HC,r)B_r = B_H(\partial_H C,r) and updates C←C∪BrC \leftarrow C \cup B_r and H←H∖BrH \leftarrow H \setminus B_r. For clarity, let HH and CC denote the sets before the update, and let HnewH_{\mathrm{new}} and CnewC_{\mathrm{new}} denote the sets after the update. We want to show that ∣∂GHnew∩Cnew∣≤n|\partial_G H_{\mathrm{new}} \cap C_{\mathrm{new}}| \le\sqrt{n}. To this end, we first define Br−1=BH(∂HC,r−1)B_{r-1} = B_H(\partial_H C,r-1) and observe that Br∖Br−1=∂HBH(∂HC,r−1)B_r \setminus B_{r-1} = \partial_H B_H(\partial_H C,r-1). We claim that

∂GHnew∩Cnew⊆Br∖Br−1.(21)\partial_G H_{\mathrm{new}} \cap C_{\mathrm{new}} \subseteq B_r \setminus B_{r-1}. \tag*{(21)}

The desired size bound on ∂GHnew∩Cnew\partial_G H_{\mathrm{new}} \cap C_{\mathrm{new}} follows from (21), as by assumption of Case 2 we have ∣Br∖Br−1∣≤n|B_r \setminus B_{r-1}| \le\sqrt{n}. To prove (21), observe that Cnew=C∪BrC_{\mathrm{new}} = C \cup B_r, so it suffices to show that vertices in C∪Br−1C \cup B_{r-1} are not in ∂GHnew\partial_G H_{\mathrm{new}}. Indeed, every vertex in CC has no neighbors in HnewH_{\mathrm{new}}, as every neighbor lying in HH is in ∂HC\partial_H C; similarly, every vertex in Br−1B_{r-1} has no neighbors in HnewH_{\mathrm{new}}, as its neighbors in HH are in BrB_r. So, the only vertices in CnewC_{\mathrm{new}} that could be adjacent to HnewH_{\mathrm{new}} (and thus in ∂GHnew\partial_G H_{\mathrm{new}}) are those in Br∖Br−1B_r \setminus B_{r-1}, as desired.

Finally, for the third case, suppose that Case 3 adds some new branch set TT to K\mathcal{K}. When TT is formed in line 19, by Corollary 1

∣V(T)∣≤13hh/n+1≤13n+1.|V(T)| \le\frac{13h}{h/\sqrt{n}} + 1 \le13\sqrt{n} + 1.

Then TT is extended further in line 23 by adding at most r∗=⌈n/h⌉r^* = \lceil\sqrt{n}/h \rceil vertices per branch set, totaling at most (h−1)⌈n/h⌉≤n−n/h+h−1≤2n−1(h - 1)\lceil\sqrt{n}/h \rceil\le\sqrt{n} - \sqrt{n}/h + h - 1 \le2\sqrt{n} - 1. (If h≥nh \ge\sqrt{n}, our main theorem holds trivially.) Thus, ∣V(T)∣≤15n|V(T)| \le15\sqrt{n}.

Lemma 9 (Balance). At every point during the algorithm, we have ∣H∣≥n/4|H| \ge n/4. Moreover, when the algorithm terminates, every connected component of HH has at most 3n/43n/4 vertices.

Proof. The second statement follows immediately from the while loop termination condition. We now show that ∣H∣≥n/4|H| \ge n/4 always. Indeed, initially we have ∣H∣=n|H| = n. At the beginning of each iteration, after line 3, we have ∣H∣≥3n/4|H| \ge3n/4 by assumption. During the iteration, in steps 4–25 of the algorithm, at most n/2n/2 vertices are removed from HH: in case 1 we remove ∣∂HA∣|\partial_H A| vertices, where ∣∂HA∣≤h/n∣A∣≤∣A∣≤n/2|\partial_H A| \le h/\sqrt{n}|A| \le|A| \le n/2 (note we assume h≤nh \le\sqrt{n} as otherwise our main theorem holds trivially); in Case 2 we remove ∣BH(∂HC,r)∣≤n/2|B_H(\partial_H C,r)| \le n/2 vertices; and in Case 3 we remove ∣V(T)∣|V(T)| vertices, where the proof of Lemma 8(3) shows that ∣V(T)∣≤15n|V(T)| \le15\sqrt{n}, which is ≤n/2\le n/2 if nn is sufficiently large.9 Thus the size of HH is always at least 3n/4−n/2=n/43n/4-n/2=n/4. □

The main theorem follows immediately from Lemmas 8 and 9.

Theorem 1. Any nn-vertex KhK_h-minor-free graph GG has a 3/43/4-balanced separator of size at most 16hn16h\sqrt{n}.

Proof. The algorithm returns ∂GH\partial_G H, which comprises at most 16hn16h\sqrt{n} vertices by Lemma 8. Moreover, every connected component of G∖∂GHG \setminus\partial_G H is either a connected component of HH or is contained in G∖HG \setminus H; as Lemma 9 implies that connected components of HH have size ≤3n/4\le3n/4 and that ∣V(G∖H)∣≤3n/4|V(G \setminus H)| \le3n/4, we conclude that ∂GH\partial_G H is a balanced separator of GG. □

References

  1. [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. [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. [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. [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. [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. [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. [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. [8]Louis Esperet and Jean-Florent Raymond. Polynomial expansion and sublinear separators. European Journal of Combinatorics, 69:49–53, 2018.DOI
  9. [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
  10. [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.
  11. [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
  12. [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
  13. [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
  14. [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.
  15. [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
  16. [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.
  17. [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
  18. [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
  19. [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.
  20. [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.
  21. [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.

Paper details

vlnc:W_7ar87x2f
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.

  • Mathematics

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

View statement
Looking for related papers…
Contents