A Separator for Minor-Free Graphs Beyond the Flow Barrier
May 06, 2026
Abstract
In 1990, Alon, Seymour, and Thomas [1] gave the first balanced separator of size \(O(h^{3/2}\sqrt{n})\) for any \(K_h\)-minor-free graph, which has had numerous algorithmic applications. They conjectured that the size of the balanced separator can be reduced to \(O(h\sqrt{n})\), which is asymptotically tight. Two decades later, Kawarabayashi and Reed [2] constructed a separator of size \(O(h\sqrt{n} + f(h))\) based on the graph minor structure theorem, where \(f(h)\) is an extremely fast-growing function typically seen in the structure theorem; their separator’s size is only better than that of Alon, Seymour, and Thomas for a very small value of \(h\). Recently, Spalding-Jamieson [3] constructed a separator of size \(O(h\log h \log\log h \sqrt{n})\); the technique is rooted in concurrent flow-sparsest cut duality. Spalding-Jamieson’s separator comes very close to \(O(h\log h \sqrt{n})\), which is the barrier for techniques based on the flow-cut duality.
In this work, we first observe that plugging in the recent padded decomposition by Filtser and Conroy [4] into the flow-based algorithm of Korhonen and Lokshtanov [5] yields a balanced separator of size \(O(h\log h \sqrt{n})\), matching the flow barrier. This result motivates the question of whether the flow barrier can be broken, which would be a stepping stone toward resolving the conjecture of Alon, Seymour, and Thomas [1]. The main result of our work is a positive answer to this question: we construct a balanced separator of size \(O(h \sqrt{\log h} \sqrt{n})\). Surprisingly, perhaps, our algorithm is still based on the iterative framework of Alon, Seymour, and Thomas [1], although a key component of their algorithm within this framework, called the neighborhood bound, was shown to be tight [6]. Our new idea is to incorporate a low-diameter decomposition into the framework, which allows us to reduce the neighborhood bound by a factor of \(h\), at the cost of a factor \(\log h\). As a result, we improve the \(\sqrt{h}\) factor to \(\sqrt{\log h}\) in the final separator’s size. Erasing \(\sqrt{\log h}\) entirely seems to require substantially new ideas.
1 Introduction↩︎
The two most powerful structural results in minor-free graphs that have numerous algorithmic applications are the graph minor structure theorem [7] and the separator theorem [1]. The structure theorem says roughly that one can decompose a \(K_h\)-minor-free graph into a tree structure of pieces which are simple, with the simplicity is parameterized by a function \(f(h)\), an extremely fast-growing function [7]. A recent breakthrough [8] reduces \(f(h)\) to a polynomial function of \(h\), though the proof remains very complicated, spanning hundreds of pages, and the degree of the polynomial remains impractically large. Specifically, \(f(h) = O(h^{2300})\). Determining the exact polynomial dependency of \(f(h)\) on \(h\) (which could well be very practical) and/or giving a simpler construction remains a long-standing open problem [9]. On the other hand, separator theorems often have very small dependence on \(h\), and their proofs are often much simpler.
A of a graph \(G = (V,E)\) is a subset \(X\subseteq V\) such that the largest connected component of \(G\setminus X\) has size at most \(2n/3\). Alon, Seymour, and Thomas [1] were the first to show that any \(K_h\)-minor-free graph admits a balanced separator of size \(O(h^{3/2}\sqrt{n})\), which can be found in polynomial time of \(O(m\sqrt{nh})\). Regarding the dependence on \(h\) of the separator size, they remarked:
“We think that the expression \(h^{3/2}n^{1/2}\) [...] is not the best possible, and that \(O(hn^{1/2})\) is the correct answer, but have not been able to decide this. [...] Every 3-regular expander with \(n\) vertices is a graph with no \(K_h\)-minor for \(h = cn^{1/2}\), and with no separator of size \(dn\), for appropriately chosen positive constants \(c\) and \(d\); and hence the estimate \(O(hn^{1/2})\) would be the best possible.”
A few years later, Plotkin, Rao, and Smith [10] constructed a balanced separator of size \(O( h n\sqrt{\log n})\) which has an optimal dependence on \(h\) but a larger dependence on \(n\). This separator size is suboptimal in the regime \(h = O(1)\), which includes well-studied classes, such as planar graphs and graphs with constant genus. Nevertheless, the bound by Plotkin, Rao, and Smith is strong evidence supporting the Alon-Seymour-Thomas conjecture.
Conjecture 1 (Alon-Seymour-Thomas Conjecture [1]). For any \(h\geq 3\) and \(n\geq 1\), any \(K_h\)-minor-free graph of \(n\) vertices has a balanced separator of size at most \(c \cdot h \sqrt{n}\) for some positive constant \(c\).
This conjecture saw very little progress for almost 20 years, until Kawarabayashi and Reed claimed a solution in a FOCS 2010 conference paper [2]. However, as recently remarked by [11], one of the authors later clarified in a talk [12] that the precise bound is \(O(hn^{1/2} + f(h))\) where \(f(h)\) is the function in the graph minor structure theorem. The full version of their paper remains unpublished. And it is unclear if the recent breakthrough on the structure theorem [8] can be applied to reduce \(f(h)\) to a polynomial in \(h\). Even if it does, then \(f(h)\) remains a very large polynomial of \(h\), which gives a vacuous bound when \(h = n^{1/2300}\). Moreover, the construction would not be elementary, which has been regarded as the key advantage of separator theorems [1], [10], [11] over the structure theorem. In any case, 1 remains open in its full generality.
In a different direction, Biswal, Lee, and Rao [13] studied spectral partitioning algorithms for \(K_h\)-minor-free graphs. Their technique gave a different algorithm for constructing a balanced separator of size \(O(h^{3}\sqrt{n \log h})\) based on the duality between concurrent flow and (uniform) sparsest cut. While this separator bound is worse than that of Alon, Seymour, and Thomas [1] by a factor of \(h^{3/2}\sqrt{\log h}\), their framework made an important link between padded decomposition and balanced separators via concurrent flow. As of their writing, the best padding parameter was \(\beta(h) = O(h^2)\). Recently, Spalding-Jamieson [3] studied reweighted spectral graph partitioning for special classes of graphs, and noticed that using the recent padded decomposition by Conroy and Filtser [4], which has \(\beta(h) = O(\log h)\), the separator bound can be improved to \(O(h \log(h)\log\log h \sqrt{n})\) (Corollary 1.6. in [3]). We note that the proof by Spalding-Jamieson [3] via the spectral technique is somewhat complicated. Here, we give a direct proof relating the padded decomposition parameter and the size of the balanced separator, and on the way, remove the \(\log\log(h)\) factor from the separator bound by Spalding-Jamieson [3].
theoremFlowSeparator For any \(n\)-vertex \(K_h\)-minor-free graph, there exists a separator of size \(O(h\log(h)\sqrt{n})\) that can be found in randomized polynomial time.
Our proof of [thm:minor] is by adapting the proof of the separator theorem for \(K_h\)-induced minor-free graphs by Korhonen and Lokshtanov [5]. In particular, we plug in the recent padded decomposition with a padding parameter \(\beta(h) = O(\log h)\) by Conroy and Filtser [4] to replace \(O(\log n)\) factor with \(O(\log h)\) in the duality between concurrent flow and sparsest cut; see 4 for details.
The \(\log(h)\) factor in [thm:minor] is precisely the padding parameter, which is also the gap between concurrent flow and (uniform) sparsest cut. Conceivably, if one can improve the gap, one gets a smaller separator. However, the \(\log(h)\) gap is tight: for a degree-3 expander with at most \(h^2\) vertices, which excludes \(K_{O(h)}\) as a minor, has the flow-cut gap \(\Omega(\log(h))\). Thus, the flow-based technique [3], [5], [13] has a natural barrier of \(\Omega(h \log h \sqrt{n})\), and [thm:minor] is optimal for this class of techniques.
In this paper, we set out to bypass the flow barrier. Our main result is a new combinatorial1 algorithm for constructing a balanced separator in the following theorem.
| Separator Size | References | Notes |
|---|---|---|
| \(O(h^{3/2} \sqrt{n})\) | [1] | First balanced separator of size \(O(\sqrt{n})\) for a fixed \(h\) |
| \(O(h \sqrt{n \log n})\) | [10] | Suboptimal by a factor of \(\sqrt{\log n}\) for a fixed \(h\) |
| \(O(h \sqrt{n} + f(h))\) | [2] | \(f(h)\) is a fast growing function |
| \(O(h^3 \sqrt{\log h} \sqrt{n})\) | [13] | Flow-cut duality |
| \(O(h \log h \log \log h \sqrt{n})\) | [3] | Flow-cut duality, using \(O(\log h)\) padding parameter [4] |
| \(O(h \log h \sqrt{n})\) | [thm:minor] | Flow-cut duality, plugging [4] into [5], matching flow barrier |
| \(O(h \sqrt{\log h}\sqrt{n})\) | 1 | Main result, bypassing the flow barrier |
| \(O(h \sqrt{n})\) | 1 [1] | Open |
| \(O(h^{13} \sqrt{n})\) | [11] | First linear-time algorithm for fixed \(h\) |
Theorem 1. For any \(n\)-vertex \(K_h\)-minor-free graph, there exists a separator of size \(O(h \sqrt{\log h}\sqrt{n})\) that can be found in randomized polynomial time.
1 cuts the gap between the flow-based techniques and 1 quadratically, from \(\log(h)\) to \(\sqrt{\log h}\). See 1 for an overview of existing bounds. Our proof is elementary, which we view as a stepping stone towards a full resolution of 1. Astute readers might realize that the dependence on \(h\) in 1 is coincidentally the same as the dependence on \(h\) in the maximum number of edges of a \(K_h\)-minor-free graph, which is \(O(h\sqrt{\log h} n)\). The factor \(h\sqrt{\log h}\) in the latter bound is tight [14], and realized by the Erdős–Rényi random graph \(\mathcal{G}(n,p)\) with \(p=1/2\) [15]. For \(\mathcal{G}(n,p = 1/2)\), the clique minor size is \(\Theta(n/\sqrt{\log n})\) [15], so in this case, the separator bound \(h \sqrt{n} = \Omega(n^{3/2}/\log(n))\) is vacuous. When \(p = C/n\) for any constant \(C > 1\), the size of the clique minor in \(\mathcal{G}(n,p)\) is \(\Theta(\sqrt{n})\) w.h.p [16] and the separator size is \(\Theta(n)\), which is also within the bound of 1.
1.1 Other related work↩︎
In this paper, we focus solely on the existence of a small balanced separator and make no attempt to minimize the running time. There is a long line of work on the computational aspect of balanced separators [1], [2], [10], [11], [17]–[19]. The goal is to design a faster algorithm, ideally in linear time, possibly at the cost of higher dependence on \(h\) in the separator’s size. The recent work by Bonnet, Korhonen, Le, Li, and Masařík [11] gives the first linear-time algorithm when \(h\) is a constant: the separator size is \(O(h^{13}\sqrt{n})\) and the running time is \(O(h^{13}n)\). We refer readers to their paper for an in-depth discussion of existing techniques for fast algorithms. A major open question is to obtain the best of both: a linear-time algorithm for computing a balanced separator of size \(O(h\sqrt{n})\), which remains out of reach.
1.2 Proof overview↩︎
In this section, we give an overview of the proof of 1. An important concept is a , denoted by \(\mathcal{K}\), which is a collection of vertex-disjoint subgraphs, called , such that every two branch sets \(C, C' \in \mathcal{K}\) have an edge between them. The of the minor model is the number of branch sets it contains. A graph \(G\) is \(K_h\)-minor-free if and only if it does not contain a minor model of size \(h\). We first describe an iterative algorithmic template for constructing balanced separators by Alon, Seymour, and Thomas [1] (though our presentation differs from the original by Alon, Seymour, and Thomas [1]). This template captures the algorithm by Alon, Seymour, and Thomas [1] and other variants [10], [18]; see also [20]. Some components of the template will be redundant in one algorithm but are necessary in another. And all of them will be necessary in our final algorithm.
The algorithm iteratively maintains a minor model , a set of vertices \(\EMPH{X} \subseteq V\), and the largest connected component if one removes the “current separator” from the graph \(G\). The current separator contains \(X\) and some other vertices, denoted by ; the precise definition of \(F(\mathcal{K}, H)\) varies across algorithms. The key point is that it depends on the structure of \(\mathcal{K}\) and \(H\). Every branch set in \(\mathcal{K}\) has at least one neighbor in \(H\). As long as \(|V(H)| > 2n/3\) (which means the current separator is not balanced), the algorithm will shrink \(H\) and add more vertices to either \(X\) or \(\mathcal{K}\), which effectively also updates the current separator. If at any point, the size of the minor model \(\mathcal{K}\) reaches \(h\), then it is a certificate that \(G\) is not \(K_h\)-minor-free.
Also, the template takes a parameter \(\ell > 0\) as an input, and finds a separator whose size depends on \(\ell\). In the two algorithms most relevant to our work, namely, the Alon-Seymour-Thomas (AST) algorithm [1] and the Plotkin-Rao-Smith (PRS) algorithm [10], the separators’ sizes are: \[\label{eq:AST-PRS} O\left(\frac{nh}{\ell} + h^2\ell\right) \quad \text{(AST algorithm \cite{AST90})} \qquad \&\qquad O\left(\frac{n}{\ell} + h^2\ell \log n\right) \quad \text{(PRS algorithm \cite{PRS94})}\tag{1}\] In particular, choosing \(\ell = \sqrt{n/h}\) in the former algorithm, and \(\ell = \sqrt{n}/(h\sqrt{\log n})\) in the latter algorithm, we get separators of sizes \(O(h^{3/2}\sqrt{n})\) and \(O(h\sqrt{n\log n})\), respectively.
In the AST algorithm [1], in every step, either one can find () a connected subgraph of \(H\) with \(O(h \ell)\) vertices that contains at least one neighbor of each branch set in \(\mathcal{K}\) or () a subset \(S\) of size \(n/\ell\) such that at least one (small) connected component of \(H\setminus S\) contains all the neighbors in \(H\) of some branch set, say \(C\), in \(\mathcal{K}\). In the former case, it adds to \(\mathcal{K}\) a new branch set of size \(O(h \ell)\) and in the latter case, it extends an existing branch set \(C\in \mathcal{K}\) such that in the next iteration \(|N_{H}(C)| = O(n/\ell)\) where is the set of neighbors of \(C\) in \(H\). The final separator, when the algorithm stops, contains for every branch set \(C\in \mathcal{K}\), either \(V(C)\) or \(N_H(C)\), whichever set has smaller size. (The AST algorithm does not maintain \(X\).) Since \(|\mathcal{K}| \leq h\), the former case contributes \(O(h^2\ell)\), while the latter case contributes \(O(hn/\ell)\), to the separator’s size in 1 . Interestingly, Kotlov [6] shows that the trade-off \(O(h \ell)\) in case(i) vs \(O(n/\ell)\) in case (ii) of the AST algorithm is best possible. In other words, the \(|N_{H}(C)| = O(n/\ell)\) is tight.
In the PRS algorithm [10], there are also two cases in every step. (Case i) if the radius of \(H\) is at least \(2\ell \ln(n)\), then one can add to \(X\) a subset of vertices \(S\) such that \(|S| \leq \frac{|V(\tilde{H})\setminus V(H)|}{\ell}\), where \(\tilde{H}\) is the largest component in the next iteration. (Case ii) Otherwise, the radius of \(H\) is at most \(2\ell \ln(n)\), then one can add to \(\mathcal{K}\) a new branch set, which composes of at most \(h\) shortest paths of length at most \(2\ell \ln(n)\) each, where each path is connected to an existing branch set in \(\mathcal{K}\). The final separator is \(X\cup \left(\cup_{C\in \mathcal{K}}V(C)\right)\). To bound the size, in case i, the main observation is that \(V(\tilde{H})\setminus V(H)\) will not be involved in subsequent iterations, and therefore, by charging the size of \(S\) to \(V(\tilde{H})\setminus V(H)\), every vertex is charged by \(1/\ell\) amount, and it is charged at most once. This explains the first term \(O(n/\ell)\) in 1 . In case ii, the branch set has size \(O(h\ell \log n)\), and therefore, the total number of vertices in all (and at most \(h\)) branch sets is \(O(h^2\ell \log n)\), which explains the second term in 1 . Here we remark that the \(\log(n)\) factor is inherent in the first step, since one has to bound the size of \(S\) by vertices that are not in the largest component of the next step to avoid charging twice.
From the description above, \(F(\mathcal{K}, H) = \cup_{C\in \mathcal{K}}V(C)\) in the PRS algorithm, while in AST algorithm, \(F(\mathcal{K}, H) = \cup_{C\in \mathcal{K}} \arg\min \{|V(C)|, |N_H(C)|\}\).
Our algorithm also fits the iterative algorithmic template described above and has four cases, corresponding to four steps. The first step is a new twist, which incorporates the low-diameter decomposition (LDD) into the template. LDD says that one can remove a small number of vertices to get connected components of small weak diameter. Here the of a connected component \(Y\) is \(\max_{x\not= y \in Y} \delta_G(x,y)\), while the is \(\max_{x\not= y \in Y} \delta_{G[Y]}(x,y)\).
lemmaLDDLem Let \(G = (V,E)\) be an undirected, unweighted \(K_h\)-minor-free graphs. Let \(\Delta > 0\) be a parameter. Then we can find in randomized polynomial time a subset \(S\subseteq V\) of vertices of size \(O(\log(h)\frac{n}{\Delta})\) such that w.h.p. every connected component \(G\setminus S\) has a weak diameter at most \(\Delta\).
We note that the LDD in [cor:separation] is a simple corollary of padded decomposition [4]; see 2. Our algorithm has four steps:
(Step 1) we apply LDD to \(H\) with \(\Delta = \ell \log h\) to find a set \(S\) of size \(O(n/\ell)\). If every connected component of \(H\setminus S\) has size less than \(2n/3\) vertices, then we have found a balanced separator \(X\cup S\cup F(\mathcal{K},H)\). Otherwise, we have found a vertex \(v\) such that at least \(2n/3\) other vertices are within distance \(\Delta\) from \(v\); note that we do not add any new vertex to the current separator \(X\) in this case. We use \(v\) to divide \(V(H)\) into 3 parts, based on the distance from \(v\): \(U = \{u: \delta_H(u,v)\leq \Delta\}\) (upper), \(M = \{u: \Delta < \delta_H(u,v)\leq \Delta + (\log h+1)\ell\}\) (middle), and \(B = \{u: \delta_H(u,v)> \Delta + (\log h+1)\ell\}\) (bottom); see 1. For a technical reason, we need to define an extension of \(M\), denoted by \(M^{+\ell}\), which contains \(M\) and all vertices of \(B\) within distance \(\ell\) from \(M\). (These sets are continuous layers in the BFS tree rooted at \(v\).) The remaining three steps are based on the structure of the three parts.
(Step 2) If every branch set \(C\in \mathcal{K}\) has a neighbor in \(U\cup M^{+\ell}\), then we can add a new branch set of size \(O(h \ell \log(h))\) to \(\mathcal{K}\), consisting of at most \(h\) shortest paths, each of length at most \(\Delta + (\log h+1)\ell + \ell = O(\ell \log h)\).
(Step 3) If \(|B| \leq n/h\), which means at least one layer among \(\ell\) layers in \(M^{+\ell}\cap B\) has size at most \(n/(\ell h)\). Then we can extend an existing branch set \(C\in \mathcal{K}\) such that in the next iteration \(|N_H(C)| \leq n/(h\ell)\). Compared to the neighborhood bound in Case II of the AST algorithm, we reduce the bound by a factor of \(h\).
(Step 4) If \(|B|>n/h\), then can find a set \(S\) which is a layer \(i^*\) in \(M\) such that \(|S| \leq \frac{|L_{\geq i^*+1}|}{\ell}\) where \(L_{\geq i^*+1}\) are all layers after \(i^*\). Then we add \(S\) to \(X\), and charge its size to the vertices in \(L_{\geq i^*+1}\). By the LDD in Step 1, we know that at least \(2n/3\) vertices are in \(U\). Thus, in the next iteration, the largest connected component will not contain any vertex from \(L_{\geq i^*+1}\), and hence every vertex will be charged once during the entire algorithm. This means \(|X| \leq n/\ell\) in the end.
If we never return the separator in Step 1, the final separator is \(X\cup F(H,\mathcal{K})\); otherwise, it is \(X\cup S\cup F(\mathcal{K},H)\) where \(S\) is the vertex set from the LDD [cor:separation]. Here \(F(\mathcal{K}, H) = \cup_{C\in \mathcal{K}} \arg\min \{|V(C)|, |N_H(C)|\}\), which is the same as in the AST algorithm. To bound the size, observe that in Step 1, \(|S| = O(n/\ell)\) by [cor:separation]. In Step 2, \(|V(C)| \leq O(h\ell \log h)\) and in Step 3, \(N_H(C) \leq n/(h\ell)\). As \(\mathcal{K}\) contains at most \(h\) branch sets, the total size of \(F(\mathcal{K},H)\) is \(h\cdot O(h\ell \log h + n/(h\ell)) = O(n/\ell + h^2\ell \log h)\). In Step 4, \(|X| \leq n/\ell\), giving a separator of total size: \[\label{eq:our-bound} O(n/\ell + h^2 \ell \log h)\tag{2}\] By choosing \(\ell = \sqrt{n}/(h\sqrt{\log h})\), we get a separator of size \(O(h\sqrt{\log h}\sqrt{n})\) as in 1. As mentioned above, the root of our improvement is the smaller neighborhood bound resulting from the LLD step.
2 Preliminaries↩︎
Let \(G = (V,E)\) be an undirected and unweighted graph. If the vertex set and edge set of \(G\) are not explicitly written, then we denote the vertex set by \(V(G)\) and the edge set by \(E(G)\). If edges of \(G\) are associated with a weight function \(w\), then we write \(G = (V,E,w)\). Graphs in this paper are generally unweighted, unless noted otherwise. We denote by \(\delta_G(u,v)\) the shortest distance in \(G\) between any two vertices \(u,v\in V\). Let \(B_{G}(v,r) = \{u: \delta_G(v,u)\leq r\}\) be the ball of radius \(r\) centered at a vertex \(v\).
Let \(\Delta > 0\) be a parameter and an edge-weighted graph \(G = (V,E,w)\). A partition of \(G\) is a partition \(\mathcal{P}\) of \(V\) such that the weak diameter of every set \(P\in \mathcal{P}\) is at most \(\Delta\). For a vertex \(x\), we denote by \(\mathcal{P}(x)\) the set in \(\mathcal{P}\) containing \(x\). Let \(\beta \geq 1\) and \(\delta \in (0,1)\) be two parameters. A of \(G\) is a distribution of \(\Delta\)-bounded partitions of \(V\), denoted by \(\mathcal{D}\), such that for any parameter \(\gamma \in (0,\delta)\), we have: \[\label{eq:padd-prob} \mathrm{Pr}_{\mathcal{P}\sim \mathcal{D}}[B_G(x,\gamma \Delta)\subseteq \mathcal{P}(x)]\geq e^{-\beta \gamma}\tag{3}\]
The parameter \(\beta\) is called the . An ideal padded decomposition should have \(\beta\) as small as possible, and \(\delta\) close to \(1\). We say that \(G\) admits a if it admits a \((\beta,\delta,\Delta)\)-padded decomposition for any \(\Delta > 0\). The scheme is if for every \(\delta > 0\), one can sample a \(\Delta\)-bounded partition from the \((\beta,\delta,\Delta)\)-padded decomposition in polynomial time. Constructing a padded decomposition scheme for \(K_h\)-minor-free graphs with \(\beta = O(\log h)\) and \(\delta = \Omega(1)\) had been a long-standing open problem until the recent work by Conroy and Filtser [4] who constructed such a scheme.
Theorem 2 (Padded Decomposition [4]). Every edge-weighted \(K_h\)-minor-free graph admits a \((\beta,\delta)\)-padded decomposition scheme with \(\beta = O(\log h)\) and \(\delta = \Omega(1)\). Furthermore, the scheme is samplable in polynomial time.
Now we show that the padded decomposition in 2 implies the LDD in [cor:separation], restated below.
Proof. Let \(\Delta\) be the parameter in the LDD. Let \(\mathcal{P}\) be a \(\Delta\)-bounded partition sampled from a \((\beta = O(\log h), \gamma = 1/\Delta,\Delta)\)-padded decomposition for \(G\) (with unit edge weight). Let \(S = \{s: B_G(s,1) \not\subseteq \mathcal{P}(s)\}\). Observe that:
\[\begin{align} \mathbb{E}[|S|] &= \sum_{v\in V} \mathrm{Pr}[B_G(v,1) \not\subseteq \mathcal{P}(v)] \\ &\leq \sum_{v\in V} 1-e^{-\beta \gamma } \qquad \text{(by \Cref{eq:padd-prob})}\\ &= \sum_{v\in V} 1-e^{-\beta/\Delta} \qquad \text{(since \gamma =1/\Delta )}\\ &\leq \sum_{v\in V} \beta/\Delta = O(n\log h/\Delta) \qquad \text{(since \beta =O(\log h) )} \end{align}\]
To show that every connected component, say \(C\), of \(G\setminus S\) has weak diameter at most \(\Delta\), we observe that \(C \subseteq P\) for some set \(P \in \mathcal{P}\), since otherwise, at least one vertex \(v\in C\) has \(B_G(v,1)\not\subseteq \mathcal{P}(v)\), and hence is in \(S\), a contradiction. ◻
3 Proof of 1↩︎
Our algorithm will take a parameter \(\ell > 0\) as an input and output a balanced separator of size depending on \(\ell\), as stated in the following lemma.
lemmamainLemma Let \(G\) be an \(n\)-vertex graph \(K_h\)-minor-free graph, and \(\ell > 0\) be any parameter. Then one can find a balanced separator of size \(O(\frac{n}{\ell} + \ell h^2\log h)\) in randomized polynomial time.
Note that 1 follows by choosing \(\ell = \sqrt{n}/(h\sqrt{\log h})\).
3.1 The Algorithm↩︎
Our algorithm follows the iterative framework described in 1.2; see 3 for the pseudocode. In each iteration, it maintains: (i) a clique minor model \(\mathcal{K}\), (ii) a subset of vertices \(X\), and (iii) a subgraph \(H\) of \(G\), which is the largest connected component of \(G\) obtained by removing from \(G\) the current balanced separator. The current balanced separator contains \(X\) and a subset of vertices defined below, denoted by \(F(\mathcal{K},H)\), which depends on \(\mathcal{K}\) and \(H\). In every step, the algorithm will shrink \(H\), update \(\mathcal{K}\), and/or expand \(X\). (The size of \(\mathcal{K}\) could be increased or decreased in every step.)
3.1.0.1 Step 1: Low-diameter Decomposition.
Let \(\Delta = \ell \log(h)\). We apply the LDD in [cor:separation] to \(H\) with parameter \(\Delta\) to find a subset \(S\subseteq V(H)\) of size \(|S| = O(\log(h) n/\Delta) = O(n/\ell)\) such that every connected component of \(H\setminus S\) has a weak diameter at most \(\Delta\). If every connected component has size at most \(2n/3\), then we output \(X\cup S\cup F(\mathcal{K})\) as a balanced separator. (Note here that \(S\) has size \(O(n/\ell)\), which is well within the bound in [lm:Main]; the size of \(X\) and \(F(\mathcal{K},H)\) will be inductively guaranteed to satisfy [lm:Main] as well.)
Otherwise, pick a vertex \(v\) such that \(|B_H(v,\Delta)|\geq 2n/3\); such a vertex exists since at least one connected component of \(H\setminus S\) has size at least \(2n/3\). Let \(T\) be the BFS rooted at \(v\) of \(H\). Let \(L_i\) be the \(i\)-th layer of the BFS tree, starting from the \(0\)-th layer, which contains \(v\) only. For any integers \(0 \leq a\leq b\), let \(\text{\EMPH{L_{a:b}}} = \{L_i: a\leq i \leq b\}\), \(\text{\EMPH{L_{\geq b}}} = \cup_{i\geq b} L_i\) and \(\text{\EMPH{L_{\leq a}}} = L_{0:a}\). We partition the vertex set of \(H\) into three sets: \(U =L_{\leq \Delta}\) (upper), \(M = L_{\Delta + 1: \Delta + \ell^*}\) (middle), and \(B = L_{\geq \Delta + \ell^* + 1}\) (bottom), where \(\text{\EMPH{\ell^*}} = (\log h+1)\ell\). Let \(M^{+\ell} = M\cup L_{\Delta + \ell^* + 1: \Delta + \ell^* + \ell}\). Note that \(M^{+\ell}\) contains exactly \(\ell\) top layers of \(B\); see 2. We proceed to one of the following steps. In every step \(H\) will shrink.
3.1.0.2 Step 2: Growing the minor model.
This step applies when \(N_H(C)\cap (U\cup M^{+\ell})\not= \varnothing\) for every branch set \(C\in \mathcal{K}\), where \(N_H(C)\) is the set of neighbors of \(C\) in \(H\). That is, every branch set \(C\in \mathcal{K}\) has a neighbor in the first \(O(\ell \log h)\) layers of \(T\). In this case, we can add a new branch set \(\tilde{C}\) to \(\mathcal{K}\), which consists of at most \(|\mathcal{K}|\) shortest paths, each from \(v\) to a neighbor of a branch set in \(\mathcal{K}\). We then remove \(\tilde{C}\) from \(H\), and start a new iteration (without running the following subsequent steps). Observe \(\tilde{C}\) has size \(O(h\ell \log h)\), which is within the bound of [lm:Main].
3.1.0.3 Step 3: Growing a branch set.
If Step 2 does not apply, then there must exist a branch set \(C\) such that \(N_H(C)\subseteq B\setminus M^{+\ell}\). If \(|B|\leq n/h\), then we grow \(C\) into \(H\) such that in the next iteration, \(N_H(C) \leq \frac{n}{h\ell}\).
More precisely, let \(Y\) be the layer of minimum size among all the layers in \(M^{+\ell}\setminus M\), and \(y\) be its layer index, i.e., \(Y = L_{y}\). Since \(M^{+\ell}\setminus M\) is a subset of \(B\) and has exactly \(\ell\) layers, \(|Y| \leq |B|/\ell = n/(h\ell)\). Let \(W = H[L_{\geq (y+1)}]\). Note that \(W\) could be disconnected. Let \(Z\) be all the vertices reachable from \(N_H(C)\) in the graph \(W\). Then we grow \(C\) by setting \(C\leftarrow C\cup Z\), and shrink \(H\) by removing all vertices of \(Z\) from \(H\). After this step, \(N_H(C)\subseteq L_{y}\) and hence \(N_H(C) \leq |Y| \leq \frac{n}{h\ell}\). After removing \(Z\) from \(H\), a branch set in \(\mathcal{K}\) may no longer have a neighbor in \(H\); in this case, we by removing every such branch set from \(\mathcal{K}\). Then we start a new iteration.
Now we define: \[\label{eq:FKH-de} F(\mathcal{K}, H) \mathrel{\vcenter{:}}= \cup_{C\in \mathcal{K}}(\arg \min\{|V(C)|, |N_H(C)|\})\tag{4}\] That is, for every branch set \(C\) in \(\mathcal{K}\), \(F(\mathcal{K}, H)\) either contains \(V(C)\) or its set of neighbors in \(H\), whichever set has smaller size. The idea here is that one can disconnect \(C\) from \(H\) by deleting either \(C\) itself or its set of neighbors in \(H\); we prefer deleting the smaller set. As mentioned in Step 1, we would like to have \(|F(\mathcal{K}, H)| = O(n/\ell + \ell h^2\log h)\) (the same bound in [lm:Main]). When a branch set \(C\) is added to \(\mathcal{K}\) (in Step 2), it has size \(O(h\ell \log h)\). However, \(C\) might be grown further in Step 3. If it never grows, then all such branch sets will contribute at most \(|\mathcal{K}|\cdot O(h\ell \log h) = O(\ell h^2\log h)\) to \(F(\mathcal{K}, H)\). If it does grow in Step 3 (even many times), then \(|N_H(C)| \leq n/(h\ell)\) and therefore, the neighbor sets of such branch sets contribute \(|\mathcal{K}| n/(h\ell) = O(n/\ell)\) to \(|F(\mathcal{K}, H)|\). Thus, in any case, \(|F(\mathcal{K}, H)| = O(n/\ell + \ell h^2\log h)\).
3.1.0.4 Step 4: Growing \(X\).
If Step 3 does not apply, then at this step, there must exist a branch set \(C\) such that \(N_H(C)\subseteq B\setminus M^{+\ell}\) and \(|B|> n/h\). By a simple counting argument, we can show that there exists a layer \(i^*\in [\Delta+1, \Delta + \ell^{*}]\) such that \(L_{i^*} \leq L_{\geq i^*+1}/\ell\) (see 1). We then add \(L_{i^*}\) to \(X\), remove \(L_{\geq i^*}\) from \(H\), trim \(\mathcal{K}\) (by removing branch sets that have no neighbor in \(H\)), and start a new iteration.
Note that \(X\) only grows in Step 4, and its size can be bounded by a charging argument. Since \(L_{i^*} \leq L_{\geq i^*+1}/\ell\), we can charge the size of \(L_{i^*}\) to vertices in \(L_{\geq i^*+1}\); each vertex gets \(1/\ell\) charge. Since vertices in \(L_{\geq i^*}\) are removed from \(H\), no vertex will be charged twice during the entire course of the algorithm, giving \(|X| \leq n/\ell\).
Now we sketch the argument for bounding the size of the separator; the full analysis of the algorithm is given in the next section. As quickly argued in Step 3 and Step 4, it holds that \(|F(\mathcal{K}, H)| = O(n/\ell + \ell
h^2\log h)\) and \(|X| \leq n/\ell\). If the algorithm returns a separator in Step 1, then the total size is \(|S| + |X| + |F(\mathcal{K}, H)| = O(n/\ell + \ell h^2\log h)\).
Otherwise, the algorithm will return a separator \(X\cup F(\mathcal{K}, H)\) at the iteration when the number of vertices in \(H\) first falls below \(2n/3\). The size is also \(O(n/\ell + \ell h^2\log h)\) as claimed in [lm:Main].
3.2 The Analysis↩︎
First, we show that the layer \(i^*\) in line 24 exists.
Lemma 1. In Step 4, there exists \(i^*\in [\Delta+1, \Delta + \ell^*]\) such that \(L_{i^*} \leq L_{\geq i^*+1}/\ell\).
Proof. Recall that in this case \(|B|> n/h\). Suppose otherwise, then for every \(i\in [\Delta+1, \Delta + \ell^*], L_{i}\geq L_{\geq i+1}/\ell\). We have: \[\begin{align} L_{\geq \Delta+1}&= L_{\Delta+1} + L_{\geq \Delta+2} \geq (1+\frac{1}{\ell}) L_{\geq \Delta+2} \overset{\text{induction}}{\geq} (1+\frac{1}{\ell})^{\ell^*} L_{\geq \Delta + \ell^*+1} = (1+\frac{1}{\ell})^{\ell^*} |B|\\ &> (1+\frac{1}{\ell})^{\ceil{\log(h)}\ell}\frac{n}{h} \geq 2^{\ceil{\log(h)}} n/h\geq n \end{align}\] a contradiction. ◻
Next, we show several invariants maintained by the algorithm. Let \(V(\mathcal{K}) = \cup_{C\in \mathcal{K}}V(C)\).
Lemma 2 (Invariants). At the beginning of an iteration where \(|V(H)|\geq 2n/3\), \(\mathcal{K}, X\) and \(H\) satisfy the following properties:
\(\mathcal{K}\) is a clique minor of size \(|\mathcal{K}|\), and hence \(|\mathcal{K}|\leq h-1\) in every iteration when \(G\) is \(K_h\)-minor-free.
\(H\) and branch sets in \(\mathcal{K}\) are vertex-disjoint.
Every branch set \(C\in \mathcal{K}\) has a neighbor in \(H\). That is, \(N_H(C) \not= \varnothing\).
For every branch set \(C\in \mathcal{K}\), either \(|V(C)| \leq (h-1)(2\log(h)+2) \ell\) or \(|N_H(C)|\leq n/(h\ell)\).
Let \(\bdry H\) be the vertices in \(H\) that are adjacent to vertices not in \(H\). Then, \(N_G(\bdry H)\setminus V(H) \subseteq X\cup V(\mathcal{K})\).
Proof. We prove by induction; the base case is when \(\mathcal{K}= \{x\}\), \(X = \varnothing\), and \(H\) is the largest connected component of \(G\setminus \{x\}\). Then \(F(\mathcal{K},H) = \{x\}\) by definition. Thus, all properties are trivially satisfied.
Now we consider any iteration of the algorithm. In Step 1, if the algorithm returns a separator (in line 6), then it terminates, and all the properties follow from induction. Thus, we only consider Steps 2-4 where \(H\) and \(\mathcal{K}\) are updated. Note that whenever the algorithm updates \(\mathcal{K}\) by either adding a new branch set (line 13) or growing an existing branch set in \(\mathcal{K}\) (line 21), it removes the vertices added to \(\mathcal{K}\) from \(H\), and therefore \(\mathcal{K}\) in \(H\) are always vertex disjoint, giving property 2. Observe that property 3 follows from line 27, where we remove from \(\mathcal{K}\) any branch set that has no neighbor in \(H\). Property 5 follows from the fact that whenever we remove a set of vertices from \(H\) (lines 14, 22, 26), these vertices are either added to a branch set in \(\mathcal{K}\) or \(X\). Note that in line 27, we only remove from \(\mathcal{K}\) branch sets that are not adjacent to \(H\) and therefore, to \(\bdry H\). It remains to show properties 1 and 4.
In Step 2, we add a new branch set \(\tilde{C}\) to \(\mathcal{K}\). Lines 11 and 12 guarantee that \(\tilde{C}\) has an edge to every other branch set in \(\mathcal{K}\). Thus, property 1 holds. To bound the size of \(\tilde{C}\), observe that \(U\cup M^{+\ell}\) contains the first \(\Delta + \ell^*+\ell = (2\log h + 2)\ell\) layers of the BFS tree rooted at \(v\). Therefore, \(|V(T[v,x_C])| \leq (2\log h + 2)\ell\), giving \(|V(\tilde{C})|\leq |\mathcal{K}| \cdot (2\log h + 2)\ell \leq (h-1) (2\log h + 2)\ell\). Thus, property 4 holds for \(\tilde{C}\).
In both Steps 3 and 4, we do not add a new branch set to \(\mathcal{K}\) and therefore, property 1 follows directly from induction. Step 4 does not update \(\mathcal{K}\), and hence, we only need to verify property 4 after Step 3. Observe that \(M^{+\ell}\setminus M\) has exactly \(\ell\) layers. Thus, we have: \[|Y| \leq \frac{|M^{+\ell}\setminus M|}{\ell} \leq \frac{|B|}{\ell} \leq \frac{n}{h\ell}\] as \(M^{+\ell}\setminus M\subseteq B\) and \(|B|\leq n/h\). Since \(W\) contains all the vertices in layers after \(L_y = Y\) (line 19), the neighbors of \(Z\) in the updated \(H\) (after line 22) are in \(Y\). Furthermore, since \(N_H(C)\subseteq B\setminus M^{+\ell}\), \(C\) has no neighbors in layers \(L_{\leq y}\). Thus, in the updated \(H\), \(N_H(C)\subseteq Y\), giving \(|N_H(C)| \leq |Y| \leq n/(h\ell)\) claimed in property 4. ◻
Now we are ready to prove [lm:Main], which we restate below.
Proof. The algorithm is in randomized polynomial time because of the LDD step. Otherwise, every step in each iteration can be implemented in a total of \(O(m)\) time. Thus, the whole algorithm is in randomized polynomial time.
Now we bound the size of the separator returned by 3. In every iteration, we have: \[\label{eq:FKH-size} \begin{align} F(\mathcal{K}, H) &\leq \sum_{C\in \mathcal{K}}\min\{|V(C)|, |N_H(C)|\} \\ &\leq (h-1)\left((h-1)(2\log h+2)\ell + n/(h\ell)\right) \qquad \text{(by properties 1 and 4 in \Cref{lm:invariants})}\\ &= O(n/\ell + \ell h^2\log h) \end{align}\tag{5}\] Observe that the algorithm only adds \(L_{i^*}\) to \(X\) in line 25, and there is no other update on \(X\) in each iteration. We charge the size of \(L_{i^*}\) to vertices in \(L_{\geq i^*+1}\); every vertex is charged only \(1/\ell\) \(|L^*| \leq L_{\geq i^*+1}/\ell\) and is charged at most once during the entire algorithm, giving \(|X|\leq n/\ell\). Thus, if the algorithm returns the separator in line 29, its size remains \(O(n/\ell + \ell h^2\log h)\) by 5 . Otherwise, it returns a separator in line 6, which adds a set \(S\) of size \(O(\log(h)n/(\ell \log h)) = O(n/\ell)\). Thus, the total size of the separator remains in check.
Finally, we show that the separator is balanced. Consider the last iteration where \(|V(H)|\geq 2n/3\). For clarity, let \(\tilde{H}\) be the updated version of \(H\) after this iteration; it holds that \(|V(\tilde{H})| < 2n/3\). In Steps 1, 2, and 3, \(\tilde{H}\) is the largest connected component after we add a subset of vertices to the separator (in Step 3, the subset is \(N_H(C)\)). Since \(|V(\tilde{H})| < 2n/3\), every other connected component must have size at most \(2n/3\) as well, and hence the separator is balanced. In Step 4, we only add \(L_{i^*}\) to the separator, but we remove all vertices of \(L_{\geq i^*}\). However, note that \(|B_H(v,\Delta)|\geq 2n/3\) due to Step 1, at least \(2n/3\) vertices are in the first \(\Delta\) layers, while vertices in \(L_{\geq i^*}\) are in layers after \(\Delta\). Thus, by adding \(L_i^{*}\) to \(X\), \(\tilde{H}\) is the same as the largest connected component of \(H\) after removing only \(L_i^{*}\) from \(H\). ◻
3.2.0.1 Towards a faster algorithm.
While our algorithm described above calls LDD in every iteration, the whole analysis rests on the idea that there exists a vertex \(v\) that contains \(2n/3\) other vertices of \(H\) within distance \(\Delta = \ell \log(h)\). Instead of calling LDD to find such a vertex \(v\), we sample a random vertex \(s\), and with probability at least \(2/3\), \(s\in B_H(v, \Delta)\). Then, by the triangle inequality, every vertex in \(B_H(v, \Delta)\subseteq B_H(s, 2\Delta)\), and thus, we could use \(s\) and distance threshold \(2\Delta\) in place of \(v\) and \(\Delta\) in the above algorithm. Overall, we can replace all but one LDD calls by sampling and running BFS. The running time in each iteration becomes \(O(m\log n)\), where the \(\log n\) factor is to get a high probability. Observe that the number of iterations is \(O(h + n/(h\ell \log h) = O( h + \sqrt{n/\log h}) = O(\sqrt{n})\). Thus, the total running time is \(O(m\sqrt{n}\log n)\) plus the running time of exactly one LDD call. The LDD in [cor:separation] is obtained by calling padded decomposition [4], which can be implemented in \(O(n^2)\) time. Implementing padded decomposition in \(O(m)\) time (even in the case of constant \(h\)) remains an open problem. The LDD in [cor:separation] seems simpler than the padded decomposition and hence could be found faster than sampling from a padded decomposition. We leave this as an open problem for future work.
4 A Flow-Based Approach↩︎
In this section, we construct a balanced separator for any \(K_h\)-minor-free graph of size \(O(h\log h \sqrt{n})\) as in [thm:minor]. We adapt the technique of Korhonen and Lokshtanov [5], who constructed a balanced separator for induced-minor-free graphs based on the flow-cut duality [21], [22]. Here we observe that for \(K_h\)-minor-free graphs, we can use the recent padded decomposition with a padding parameter \(O(\log h)\) by Conroy and Filtser [4] to replace the \(\log(n)\) factor with \(\log(h)\) in the flow-cut duality. The rest of the proof is borrowed directly from Korhonen and Lokshtanov [5]. We include all the details for completeness.
Let \(\mathcal{P}_{st}(G)\) be the set of all simple paths between \(s\not= t\) and \(\mathcal{P}(G) = \cup_{(s,t)\in V\times V} \mathcal{P}_{st}(G)\) be the set of all simple paths in \(G\). A \(\lambda: \mathcal{P}(G) \rightarrow \mathbb{R}_{\geq 0}\) is a function that assigns each path in \(\mathcal{G}\) a non-negative value, a.k.a, the , such that for ordered pair of vertices \((s,t)\in V\times V\), \(\sum_{P\in \mathcal{P}_{st}(G)}\lambda(P) = 1\). Thus, one can think of a concurrent flow as giving a distribution of paths between every pair of vertices. This is also the view we take in constructing a minor model when the algorithm fails to give a balanced separator.
Let \(\lambda(v)\) be the total amount of flow passing through \(v\). More formally: \[\lambda(v) = \sum_{P \in \mathcal{P}_{s,t}(G): ~v\in P,~ (s,t)\in V\times V} \lambda(P)\] The of the concurrent flow \(\lambda\) is \(\max_{v\in V}\lambda(v)\). The following lemma is a simple consequence of applying the padded decomposition for \(K_h\)-minor-free graphs with padding parameter \(O(\log h)\) on top of the framework for vertex separator by Feige, Hajiaghayi, and Lee [22].
Lemma 3. Let \(G\) be an \(n\)-vertex graph \(K_h\)-minor-free graph. For any parameter \(\gamma > 0\), there is a randomized polynomial-time algorithm that outputs either:
a balanced separator of \(G\) of size \(O(n^2\log h/\gamma)\), or
a concurrent flow of congestion \(\gamma\) on an induced subgraph \(G'\) of \(G\) such that \(|V(G')|\geq 2n/3\).
The \(\log(h)\) factor is best possible in 3, and it factors directly into the size of the balanced separator. Thus, \(O(h\log h \sqrt{n})\) is the barrier of the flow-based technique for balanced separators.
We will delay the proof of 3 to the end of this section, and continue with our algorithm for finding a balanced separator. Let \(\Ddot{H}\) be a graph obtained from \(K_h\) by subdividing every edge twice and replacing each vertex of degree \(h-1\) by a binary tree with \(h-1\) leaves. Observe that if \(G\) excludes \(K_h\) as a minor, then \(G\) also excludes \(\Ddot{H}\) as a minor, e.g., Lemma 2 in [11]. We define an an of \(\Ddot{H}\) to \(G\) is a pair of mapping \((\phi, \pi)\) where \(\phi: V(\Ddot{H})\rightarrow G\) and \(\pi: E(\Ddot{H})\rightarrow \mathcal{P}(G)\) such that:
for every edge \(xy\in E(\Ddot{H})\), \(\pi(xy)\) is a simple \(\phi(x)\)-to-\(\phi(y)\) path in \(G\).
for every two edges \(xy\) and \(uv\) in \(\Ddot{H}\) that do not share any endpoint, \(\pi(xy)\cap \pi(uv) = \emptyset\).
Proof. Let \(\gamma = \frac{n^{3/2}}{c\cdot h}\) for a sufficiently large constant \(c\). By applying the algorithm in 3 with parameter \(\gamma\), we either find a balanced separator of size \(O(h\log h \sqrt{n})\) of \(G\) or a subgraph \(G'\) of \(G\) that has a concurrent flow of congestion \(\gamma\). In the latter case, we can construct an almost minor embedding \(\phi\) of \(\Ddot{H}\) in \(G'\), and therefore we can conclude that \(G\) is not \(K_h\)-minor-free. The construction is as follows:
\(\phi\) maps each vertex \(u\in \Ddot{H}\) to a vertex \(\phi(u)\in V(G')\) uniformly at random.
For every edge \(uv\in \Ddot{H}\), \(\pi(uv)\) will map \(uv\) to a path \(P \in \mathcal{P}_{uv}(G')\) sampled from distribution induced by the concurrent flow \(\lambda\).
Let \(xy\) and \(uv\) be two edges in \(E(\Ddot{H})\) that do not share any endpoint. We say that \(\pi(xy)\) and \(\pi(uv)\) if \(\pi(xy)\cap \pi(uv) \not=\emptyset\).
For every vertex \(w\), we have: \[\begin{align} \Pr[w\in \pi(xy)] &= \frac{1}{|V(G')|^2}\sum_{(a,b)\in V(G')\times V(G')}\sum_{w \in \mathcal{P}_{ab}(G')} \lambda(P)\\ &= \frac{\lambda(w)}{|V(G')|^2} \leq \frac{9}{4n^2} \lambda(w) \leq \frac{9\gamma}{4n^2} \end{align}\] The penultimate inequality is due to \(|V(G')|\geq 2n/3\), and the last inequality is by the definition of the congestion. Since \(xy\) and \(uv\) do not share an endpoint, \(\pi(xy)\) and \(\pi(uv)\) are two independent variables. Thus, we have:
\[\Pr[w\in \pi(xy) \wedge w\in \pi(uv)]\leq \frac{81 \gamma^2}{16n^4}\] By taking the union bound over \(w\), we have:
\[\label{eq:colide-prob} \Pr[ \pi(xy) \text{ and } \pi(uv) \text{ collides}]\leq \frac{81 \gamma^2}{16n^3}\tag{6}\]
At this point, if we take the union bound over (at most) \(h^4\) pairs of edges in \(\Ddot{H}\), we would end up with the probability of having at least one collision is at most \(\frac{81h^4\gamma^2}{16n^3}\). Thus, the probability that \(\phi\) is an almost minor embedding of \(\Ddot{H}\) is at least \(1-\frac{81h^4\gamma^2}{16n^3}\), which is at least \(1/2\) when \(\gamma = O(n^{3/2}/h^2)\). However, we need \(\gamma = O(n^{3/2}/h)\).
To this end, following Korhonen and Lokshtanov [5], we use the Lovász Local Lemma: Let \(\mathcal{B}\) be a collection of bad events and let \(p\) be such that \(\max_{B\in \mathcal{B}}\Pr[B] \leq p\). Suppose that each bad event depends on at most \(d\) other bad events. Then if \(4dp\leq 1\), there is a non-zero probability that none of the bad events in \(\mathcal{B}\) happens.
In our context, each bad event is \(\pi(xy)\cap \pi(uv)\not = \emptyset\) for each non-adjacent pair. The number of such pairs is \(O(|E(\Ddot{H})|^2) = O(h^4)\). However, each bad event is only dependent on \(O(|E(\Ddot{H})|) = O(h^2)\) other bad events since \(\Ddot{H}\) has degree at most \(3\). Thus, it suffices to have the probability in 6 to be at most \(1/(c'\cdot h^2)\) for a sufficiently large \(c'\), giving \(\gamma^{2} = O(n^{3}/ h^2)\) and hence \(\gamma \leq n^{3/2}/(c\cdot h)\), for some constant \(c\), as desired. ◻
It remains to prove 3. We denote a of \(G\) by \((A,S,B)\), where (i) \(A,B,S\) are vertex disjoint, (ii) \(A\cup B\cup S = V\), and (iii) there is no edge between \(A\) and \(B\). Intuitively, \(A\) and \(B\) are obtained by removing \(S\) from \(G\). The of \((A,S,B)\) is denoted by: \[\alpha_G(A,S,B) = \frac{|S|}{|A\cup S||B\cup S|}\]
Let \(\omega: V\rightarrow \mathbb{R}^+\) be a non-negative weight function on the vertex set of \(G\). The weight function \(\omega\) induces a metric on \(V(G)\), denoted by \(\langle G,\omega\rangle\), where the distance between any two vertices \(u\) and \(v\) is the shortest vertex-weighted distance, denoted by \(\delta_{\omega}(u,v)\). Let \(f_{\omega}: V(G)\rightarrow \mathbb{R}\) be an embedding of \(\langle G,\omega\rangle\) into the line; we say that \(f_{\omega}\) is if \(|f_{\omega}(u) - f_{\omega}(v)|\leq \delta_{\omega}(u,v)\) for every \(u,v\in V\). We say that \(G\) admits an embedding with an at most \(D\) into the line if for every non-negative vertex weight function \(\omega\), there exists a contracting embedding \(f_{\omega}\) into \(\mathbb{R}\) such that:
\[\sum_{(u,v)\in V\times V} |f_{\omega}(u) - f_{\omega}(v)|\geq \frac{1}{D} \sum_{(u,v)\in V\times V} \delta_{\omega}(u,v)\]
The following result by Feige, Hajiaghayi, and Lee [22] relates embeddings into the line with low average distortion with sparsest vertex cut.
Lemma 4 (Theorem 4.1. [22]). If \(G\) admits a low-distortion embedding into the line with distortion \(D\) that is constructible in randomized polynomial time, then one can find in randomized polynomial time either: (1) a concurrent flow with congestion \(\gamma\) in \(G\) or (2) a vertex cut \((A,S,B)\) of sparsity \(O(D/\gamma)\).
Proof of 3. Rabinovich [23] showed that if the shortest path metric (induced by edge weight function \(w\)) of \(G\), denoted by \(\delta_G(u,v)\), has a padded decomposition with padding parameter \(\beta_G\), then the (edge-weight) metric \((V(G),\delta_G)\) admits an embedding into the line with average distortion \(O(\beta_G)\). Observe that by setting \(w(u,v) = \frac{\omega(u) + \omega(v)}{2}\), the shortest path metric w.r.t edge weight function \(w\) is an embedding of the shortest path metric with vertex weight \(\omega\) with distortion at most \(2\). Furthermore, \(\beta_G = O(\log h)\) for \(K_h\)-minor-free graphs [4]. Thus, \(\langle G,\omega\rangle\) is embeddable into the line with average distortion \(O(\beta_G)\). The embedding can be constructed in randomized polynomial time w.h.p., as the padded decomposition is sampleable in polynomial time [4]. Thus, by 4, we either get a (1) concurrent flow with congestion \(\gamma\) in \(G\) or (2) a cut \((A,S,B)\) with sparsity \(O(\log h/\gamma)\).
Note that the separator \(S\) in the sparse cut \((A,S,B)\) might not be balanced. W.l.o.g, we assume that \(A\) is the larger side, i.e., \(|A| > 2n/3\). To get a balanced cut, the standard trick [5], [22] is to recurse on the subgraph induced by the larger side \(G[A]\). We stop whenever we find a concurrent flow with congestion \(\gamma\) in a subgraph of \(G\) or the larger size of the cut has size at most \(2n/3\). Let \(\{(A_i,S_i,B_i)\}_{i=1}^{t}\) be a sequence of sparse cuts in this process. In the latter case, the separator \(\cup_{i=1}^t S_i\) is balanced and has size:
\[\begin{align} \sum_{i=1}^t |S_i| &= O(\log h/\gamma)\sum_{i=1}^t |A_i||B_i| \\ &\leq O(n\log h /\gamma) \sum_{i=1}^t |B_i| \qquad \text{(as |A_i|\leq n)}\\ &= O(n^2\log h/\gamma) \end{align}\] since \(\sum_{i=1}^t |B_i| \leq n\), concluding the proof. ◻
4.0.0.1 Acknowledgments.
We thank Jack Spalding-Jamieson for helpful conversations and comments. The author is supported by NSF grant CCF-2517033 and NSF CAREER Award CCF-2237288.
References↩︎
Flow-based techniques use linear programming or other numerical methods, including SDP or spectral techniques, for recursively computing a sparse vertex cut, whose union is a balanced separator.↩︎