AI Disclosure. The key high-level ideas, especially the online learning perspective, of this work were human-devised, but many of them were fleshed out and developed using LLM assistance. GPT 5.5 and GPT 5.6-Sol played useful roles in our initial developments for the presentation using FTRL, while GPT 6-Astra improved our initial running time in § 6 . Other models, namely GPT 6.1-Sol and Claude Opus 5.5 have been used to proofread. The presentation and the write-up are by the human authors only. Of course, we take full responsibility for our results.
Introduction
Separator theorems are cornerstones of modern algorithmic graph theory. They facilitate divide-and-conquer algorithms on graphs, a basic technique in algorithm design. Furthermore, research in separator theorems often reveals deep and unexpected connections between different areas of math and computer science, some of which we will mention here.
Balanced separators of sparse graphs. In 1979, Lipton and Tarjan [24 ] constructed a balanced separator of size O ( n ) O(\sqrt{n}) O ( n ) for n n n -vertex planar graphs, and showed various algorithmic applications of their result [25 ] . Their main technique is to use the duality of the (planar) embedding, which was also used in a subsequent (and more general) balanced separator result for surface-embedded graphs [15 ] . A decade later, Alon, Seymour and Thomas [4 ] showed how to get around using (planar or surface) embeddings and constructed a balanced separator for any K h K_h K h -minor-free graph of size O ( h 3 / 2 n ) O(h^{3/2}\sqrt{n}) O ( h 3/2 n ) in time O ( m h n ) O(m\sqrt{hn}) O ( m hn ) . Both the (dependence on h h h of the) separator size and the running time are not optimal, and have hence motivated two long lines of work that remain active to this day.
One line of work seeks to reduce the separator size to O ( h n ) O(h\sqrt{n}) O ( h n ) , while treating the running time as a secondary concern. Kawarabayashi and Reed [18 ] used Robertson-Seymour decomposition and claimed to obtain a separator of size O ( h n + f ( h ) ) O(h\sqrt{n}+f(h)) O ( h n + f ( h )) for some function f f f of h h h . At around the same time, Biswal, Lee and Rao [6 ] devised a new technique for constructing balanced separators via a connection to flow-cut duality. Though their separator’s size is worse than that of Alon, Seymour and Thomas [4 ] , subsequent results [32 , 21 ] followed this technique, along with recent advances with padded decomposition for K h K_h K h -minor-free graphs by Conroy and Filtser [7 ] , to bring the separator size to a nearly-optimal bound of O ( h log h n ) O(h\log h\sqrt{n}) O ( h log h n ) . This bound is optimal for a class of techniques relying on flow-cut duality and hence O ( h log h n ) O(h\log h\sqrt{n}) O ( h log h n ) becomes a barrier. Recently, Le [21 ] broke this barrier by combining two combinatorial approaches of Alon, Seymour and Thomas [4 ] and Plotkin, Rao, and Smith [30 ] . During the final stages of our own work on this paper, this line of work was fully resolved by a superset of the authors on this paper, with AI assistance, by building on Le’s techniques [8 ] . However, a common theme in this entire line of work is that the running time does not improve on that of Alon, Seymour and Thomas [4 ] . It is possible that heavy machinery from recent dynamic graph algorithms could improve the running time, though it is unclear what new insights one could gain. Often, a lack of good running-time bounds points to our lack of structural understanding of minor-free graphs.
A second line of work focuses mostly on the regime of h = O ( 1 ) h=O(1) h = O ( 1 ) and aims to improve the running time to linear, often at the cost of a larger separator, both in terms of h h h and n n n . Reed and Wood [31 ] gave the first linear-time algorithm for finding a balanced separator of size O h ( n 2 / 3 ) O_h(n^{2/3}) O h ( n 2/3 ) . However, the dependence on n n n is not optimal. And the dependence on h h h in both the running time and the separator’s size is 2 O ( h 2 ) 2^{O(h^2)} 2 O ( h 2 ) , so even a very small value of h h h , say h = log ( n ) h=\log(n) h = log ( n ) , makes both extremely large. For linear-time algorithms, this algorithm remained the state of the art until very recently; Bonnet, Korhonen, Le, Li, and Masařík [5 ] gave an O ( poly ( h ) ⋅ n ) O(\operatorname{poly}(h)\cdot n) O ( poly ( h ) ⋅ n ) time algorithm that gives a separator of size O ( poly ( h ) ⋅ n ) O(\operatorname{poly}(h)\cdot\sqrt{n}) O ( poly ( h ) ⋅ n ) . Their algorithm achieves optimal dependence on n n n while losing only a poly ( h ) \operatorname{poly}(h) poly ( h ) factor instead of an exponential factor in h h h . Notably, they introduce a novel technique for constructing balanced separators: it assigns weights to the graph’s vertices, and at each step, if the algorithm fails to output a balanced separator, it adjusts the vertex weights for the next step. On the other hand, the poly ( h ) \operatorname{poly}(h) poly ( h ) factors in both the running time and the separator’s size are quite large: O ( h 13 ) O(h^{13}) O ( h 13 ) .
The two aforementioned lines of work, while productive in pursuing their own goals, diverge in their techniques and bounds: either the running time is too big (even for a fixed h h h ) or the separator size is too big. Achieving the best of both is left as an open problem by Bonnet et al. [5 ] :
Question 1. Can we construct a balanced separator of (nearly) optimal size in time O ( poly ( h ) n ) O(\operatorname{poly}(h)n) O ( poly ( h ) n ) for K h K_h K h -minor-free graphs?
At the conceptual level, Question 1 asks for a unification of the two long lines of work on separators for K h K_h K h -minor-free graphs over the last few decades.
Beyond minor-free graphs, Plotkin, Rao, and Smith [30 ] introduced the notion of shallow minor-free graphs. Roughly speaking, K h K_h K h is an ℓ \ell ℓ -shallow minor of G G G if the minor model of K h K_h K h in G G G can be formed from (disjoint) subgraphs of radius at most ℓ \ell ℓ . Plotkin, Rao, and Smith [30 ] adapted the separator theorem of Alon, Seymour, Thomas [4 ] to show that ℓ \ell ℓ -shallow K h K_h K h -minor-free graphs have balanced separators of size O ( n / ℓ + ℓ h 2 log n ) O(n/\ell+\ell h^2\log n) O ( n / ℓ + ℓ h 2 log n ) . The concept of shallow minors and the Plotkin-Rao-Smith separator theorem are the basis of the (award-winning) theory of graph sparsity by Nešetřil and Ossona de Mendez [28 ] . One key result, among others, in this theory is a precise characterization of the classes of graphs that have strongly sublinear separators of the form O ( n 1 − α ) O(n^{1-\alpha}) O ( n 1 − α ) for a constant α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) [28 , 10 , 13 ] : these are exactly graphs with polynomial expansion.3
Balanced separators for dense graphs. The graph classes mentioned so far are sparse: for instance, every n n n -vertex K h K_h K h -minor-free graph has O ( n ) O(n) O ( n ) edges, where big-O hides the dependency on the class parameter. Many structural graph classes of practical interest are dense. For example, unit disk graphs, which are the intersection graphs of unit disks on the plane, can contain a large clique. This example is generalized by the class of all geometric intersection graphs in the plane, also known as string graphs. Despite their density, string graphs are K 5 ( 1 ) K_{5}^{(1)} K 5 ( 1 ) -induced-minor-free [1 ] , where K 5 ( 1 ) K_{5}^{(1)} K 5 ( 1 ) is the graph obtained from K 5 K_5 K 5 by subdividing each edge once. Here, a graph H H H is an induced minor of a graph G G G if H H H can be obtained from G G G by a sequence of vertex deletions and edge contractions4 . In a remarkable recent work, Korhonen and Lokshtanov [16 ] gave a separator theorem for all induced-minor-free graphs.
Theorem 1 (Korhonen and Lokshtanov [16 ] ). Any H H H -induced-minor-free graph G G G with n n n vertices and m m m edges has a balanced separator of size O ( log n ∣ V ( H ) ∣ + ∣ E ( H ) ∣ m ) O(\log n\sqrt{|V(H)|+|E(H)|}\sqrt{m}) O ( log n ∣ V ( H ) ∣ + ∣ E ( H ) ∣ m ) that can be constructed in polynomial time.
The m \sqrt{m} m factor is best possible: K n K_n K n has m = Θ ( n 2 ) m=\Theta(n^2) m = Θ ( n 2 ) edges, and every balanced separator of K n K_n K n has size Ω ( n ) = Ω ( m ) \Omega(n)=\Omega(\sqrt{m}) Ω ( n ) = Ω ( m ) . Their proof introduced a novel flow-based technique that also yielded the nearly optimal bound for balanced separators of minor-free graphs via the flow-based techniques mentioned above [21 ] . In the same paper, Korhonen and Lokshtanov [16 ] gave many algorithmic applications of Theorem 1; see Corollary 1.2 of [16 ] . In these applications, computing the balanced separator is the first step. However, though polynomial, the running time is far from linear because it requires computing a concurrent flow between Ω ( n 2 ) \Omega(n^2) Ω ( n 2 ) pairs of vertices. A recent work [11 ] improved the separator size by Korhonen and Lokshtanov [16 ] to O ( log ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) ∣ V ( H ) ∣ + ∣ E ( H ) ∣ m ) O(\log(|V(H)|+|E(H)|)\sqrt{|V(H)|+|E(H)|}\sqrt{m}) O ( log ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) ∣ V ( H ) ∣ + ∣ E ( H ) ∣ m ) which is also nearly optimal. The key new idea in this work [11 ] is an embedding of vertex-weighted induced-minor-free graphs into the line with a small average distortion. In other words, a direct (vertex) flow-cut gap bound. Such an embedding can be used to replace a padded decomposition subroutine in the work of Korhonen and Lokshtanov [16 ] . The techniques of both works run in polynomial time (for a relatively large polynomial), so the overall question of fast running time for such results remains:
Question 2. Can we construct a balanced separator of (nearly) optimal size O ( log ∣ V ( H ) ∣ ∣ V ( H ) ∣ + ∣ E ( H ) ∣ m ) O(\log|V(H)|\sqrt{|V(H)|+|E(H)|}\sqrt{m}) O ( log ∣ V ( H ) ∣ ∣ V ( H ) ∣ + ∣ E ( H ) ∣ m ) in time O ( poly ( ∣ V ( H ) ∣ ) ( m + n ) ) O(\operatorname{poly}(|V(H)|)(m+n)) O ( poly ( ∣ V ( H ) ∣ ) ( m + n )) ?
Our results
Our main results affirmatively answer both Question 1 and Question 2: we give linear-time algorithms for finding nearly-optimal balanced separators of both K h K_h K h -minor-free graphs (for a fixed h h h ) and H H H -induced-minor-free graphs (for a fixed graph H H H ).
Theorem 2. Let G G G be K h K_h K h -minor-free with n n n vertices and m m m edges. There is a randomized algorithm that returns a 3/4-balanced separator of size O ( h log h n ) O(h\log h\sqrt{n}) O ( h log h n ) in expected O ( h 7 ( m + n ) ) O(h^7(m+n)) O ( h 7 ( m + n )) time.
Theorem 3. Let G G G be H H H -induced-minor-free with n n n vertices and m m m edges. There is a randomized algorithm that returns a 3/4-balanced separator of size O ( log ∣ V ( H ) ∣ m ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) ) O(\log|V(H)|\sqrt{m(|V(H)|+|E(H)|)}) O ( log ∣ V ( H ) ∣ m ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) ) in expected O ( ∣ V ( H ) ∣ 7 ( m + n ) ) O(|V(H)|^7(m+n)) O ( ∣ V ( H ) ∣ 7 ( m + n )) time.
Our Theorem 2 not only answers Question 1 but also unifies the two lines of work on balanced separators for minor-free graphs since Alon, Seymour, and Thomas [4 ] . Each of our separator sizes are only log h \log h log h away from the optimal bound, and both are optimal for techniques that rely on flow-cut duality, including ours. In particular, both are tight for 3-regular expander graphs, which are K Ω ( n ) K_{\Omega(\sqrt{n})} K Ω ( n ) -minor-free. Table 1 compares our results with previous work.
Table 1. Table 1. Balanced separator bounds for graphs with n n n vertices and m m m edges. Here ε > 0 \varepsilon>0 ε > 0 is an arbitrary fixed constant, and f ( h ) f(h) f ( h ) , g ( h ) g(h) g ( h ) are fast-growing functions from the graph minor structure theorem. Our running times are in expectation. *Full proof unavailable (see [5 , 21 ] for more nuanced discussions). †A corollary, distinct from the main algorithm the paper studies.
Both of our results are based on the same set of underlying ideas. At a very high level, our approach may seem quite standard: We devise a continuous optimization problem, which we solve using an online learning algorithm. In the course of executing this online learning algorithm, we may terminate early to output a separator. If we never terminate early, we instead certify the existence of a minor or induced-minor. This kind of approach is quite similar to many existing approximation algorithms for graph partitioning (e.g. [3 , 26 , 20 ] ). However, there are two key differences that prevent us from using much of the existing machinery: The continuous optimization problem we devise is non-convex, and the online learning algorithm we employ has not yet seen any use in combinatorial approximation algorithms or graph partitioning (to our knowledge).
We discuss the online learning algorithm first. To design our algorithms, we introduce a new approach based on the follow the regularized leader (FTRL) framework, a well-studied technique in online learning and convex optimization. For readers who are not familiar with online learning and FTRL, we give a very short primer in § 3.1 by outlining basic ideas in the FTRL framework. A very short summary is: learning happens in T T T rounds, where in each round t t t , a learner has to output a vector x t ∈ X ⊆ R d x_t \in\mathcal{X} \subseteq\mathbb{R}^d x t ∈ X ⊆ R d , and suffers a loss ℓ t ( x t ) \ell_t(x_t) ℓ t ( x t ) for a loss function ℓ t : X → ( − ∞ , + ∞ ] \ell_t:\mathcal{X}\to(-\infty,+\infty] ℓ t : X → ( − ∞ , + ∞ ] that the learner does not know. (X \mathcal{X} X is the domain.) In future rounds, the learner gets access not just to the previous losses, but also their gradients. The learner’s goal is to minimize regret, defined as the difference between the learner’s cumulative loss and the cumulative loss of the best fixed vector in hindsight. The FTRL framework would tell the learner how to choose x t x_t x t based on the previous choices x 1 , … , x t − 1 x_1,\ldots,x_{t-1} x 1 , … , x t − 1 and the loss functions at previous steps ℓ 1 ( x ) , … , ℓ t − 1 ( x ) \ell_1(x),\ldots,\ell_{t-1}(x) ℓ 1 ( x ) , … , ℓ t − 1 ( x ) . In online learning, the loss functions are chosen by an online adversary. FTRL itself is a generalization of many popular online learning algorithms, including multiplicative weight update and matrix multiplicative weight update. However, the specific instantiation of FTRL that we will employ is not captured by these special cases.
Essentially any constrained convex optimization problem can be set up as a two-player min-max game via Lagrangian duality, so online learning is also frequently employed as a method for solving convex optimization problems. Since solutions to convex relaxations of combinatorial problems can often be rounded to approximate solutions of the original combinatorial problems, one may expect that this is the methodology with which online learning is employed for approximation algorithms. However, doing things in this manner does not make use of the special characteristics of online learning. Instead, many fast approximation algorithms use the idea of early termination : Perform a learning game over the course of (at most) T T T rounds between a learner and an adversary, where the adversary has the option of terminating the entire game prematurely and outputting a desired combinatorial solution (see e.g. [3 LTV22, 20 ] ). In such games (including all the examples), the adversary will also often use loss functions with some helpful properties like sparse gradients, in order to reduce the computational overhead of the learner. This is often done in order to reduce the time complexity of the learner from a large polynomial to near-linear (per-round). If the learning game completes all T T T rounds, such approaches then certify a lower bound on the value of the problem. These lower bounds are guaranteed via duality and standard regret guarantees. Our algorithm shares a number of similar ideas with such works. However, unlike the cited works, our objective will not simply follow as a natural convex relaxation of a combinatorial problem. In fact, as previously mentioned, it will not be convex at all, which means duality and standard regret guarantees will not help us in proving our results.
At a high level, our goal, which is also our major conceptual contribution, is to set up an online learning game with early termination such that, for a suitable choice of T T T and the loss functions, learning over T T T rounds yields an early termination with a balanced separator in one of the rounds. We break this goal into three concrete steps. (Step 1) Formulating a (new) continuous optimization problem F μ , ι ( λ ) F_{\mu,\iota}(\lambda) F μ , ι ( λ ) that captures the balanced separators. (For now, the parameters μ \mu μ and ι \iota ι are not important.) Our formulation also relies on flow-cut duality. Unlike typical optimization problems solved via FTRL, the variable λ \lambda λ in our problem has an exponentially large dimension, and F μ , ι ( λ ) F_{\mu,\iota}(\lambda) F μ , ι ( λ ) is non-convex. (Step 2) Modeling the continuous optimization problem as an online learning problem. (Step 3) Implementing each round of the online learning using the FTRL framework. As we mentioned in Step 1, our optimization has an exponential number of dimensions, so we cannot simply follow the standard FTRL template, specifically the step of designing the loss function ℓ t \ell_t ℓ t . Here, we simplify the problem greatly to derive a proxy (and simpler) optimization problem G μ , ι ( λ ) G_{\mu,\iota}(\lambda) G μ , ι ( λ ) . A key technical innovation that we want to highlight here is that we can relate ∇ G μ , ι ( λ ) \nabla G_{\mu,\iota}(\lambda) ∇ G μ , ι ( λ ) , the gradient of G μ , ι ( λ ) G_{\mu,\iota}(\lambda) G μ , ι ( λ ) , to the (vertex-weighted) graph radius, from which we can implement each FTRL round by doing a simple low-diameter decomposition on the input graphs. We will give a more detailed exposition of these steps in § 1.2 below.
We mentioned above that the linear-time algorithm for minor-free graphs by Bonnet et al. [5 ] is obtained through a novel technique that assigns weights to the graph’s vertices. As the algorithm proceeds through Θ ( h 2 ) \Theta(h^2) Θ ( h 2 ) iterations, it adjusts the vertices’ weights and outputs the separator in one of the iterations. Their vertex-weighting scheme is perhaps the most innovative part of their paper, yet also the most mysterious. Our paper is inspired by this weighting scheme, but we go one step further: by making a connection to the FTRL framework, the weighting scheme arises naturally from Step 3, where we design the loss function ℓ t \ell_t ℓ t . Our resulting weighting scheme is indeed simpler and more efficient: we can improve the running time from O ( h 13 n ) O(h^{13}n) O ( h 13 n ) [5 ] to O ( h 7 ( m + n ) ) O(h^7(m+n)) O ( h 7 ( m + n )) without any additional effort, while improving the separator size from O ( h 13 n ) O(h^{13}\sqrt{n}) O ( h 13 n ) [5 ] to nearly optimal as in Theorem 2.
Technical overview
We now describe the ideas leading to our algorithm, which uses a learning game with early termination.
Step 1: Designing an objective. Our objective will be inspired by three related concepts: An existing probabilistic path bound, subset flow problems, and the stochastic connectors of Bonnet et al. [5 ] .
Our starting point is a key component of Korhonen and Lok̄shtanov’s proof of Theorem 1. They gave a bound on a vertex-variant of the L ∞ L_\infty L ∞ -concurrent flow problem studied by Leighton and Rao [23 ] , which routes one unit of flow between every pair of vertices, and seeks to minimize the maximum “congestion” (sum of flows) through any vertex. The maximum congestion is itself called the L ∞ L_\infty L ∞ congestion, hence the name “L ∞ L_\infty L ∞ -concurrent flow problem”. This problem had been bounded for many classes in earlier works [6 , 27 , 22 ] . However, almost all these prior bounds were based on various combinatorial methods and were inherently suboptimal as a result. Korhonen and Lok̄shtanov instead used a probabilistic construction, essentially proving the following intermediate result.
Proposition 1 (adapted from [16 proofs of Lemmas 4.2–4.4] ). Let H H H be a nonempty graph and G G G an H H H -induced-minor-free graph. Sample u , v u,v u , v independently from a probability distribution π \pi π on V ( G ) V(G) V ( G ) , then sample a simple u u u –v v v path P P P from any fixed distribution for that ordered pair. If u = v u=v u = v , take P = { u } P=\{u\} P = { u } . For an independent copy P ′ P' P ′ , we have
Pr [ P and P ′ share a vertex or are joined by an edge ] ≥ c 1 ∣ V ( H ) ∣ + ∣ E ( H ) ∣ . \Pr[P\text{ and }P'\text{ share a vertex or are joined by an edge}] \ge\frac{c_1}{|V(H)|+|E(H)|}. Pr [ P and P ′ share a vertex or are joined by an edge ] ≥ ∣ V ( H ) ∣ + ∣ E ( H ) ∣ c 1 . where c 1 > 0 c_1>0 c 1 > 0 is an absolute constant.
Later, Le [21 ] and then Kolbe and Spalding-Jamieson [19 ] used variations of this argument for minor-free graphs as well, essentially proving the following.
Proposition 2 (adapted from [19 proof of Proposition 3.2] ). Let G G G be a K h K_h K h -minor-free graph, where h ≥ 3 h \ge3 h ≥ 3 , and let π \pi π be a probability distribution on V ( G ) V(G) V ( G ) . Sample u , v u,v u , v independently from π \pi π , then sample a simple u u u –v v v path P P P from any fixed distribution for that ordered pair. If u = v u=v u = v , take P = { u } P=\{u\} P = { u } . For an independent sample P ′ P' P ′ resulting from the same process,
Pr [ V ( P ) ∩ V ( P ′ ) ≠ ∅ ] ≥ c 0 h 2 , \Pr[V(P)\cap V(P')\ne\varnothing]\ge\frac{c_0}{h^2}, Pr [ V ( P ) ∩ V ( P ′ ) = ∅ ] ≥ h 2 c 0 , where c 0 > 0 c_0>0 c 0 > 0 is an absolute constant.
Both of these propositions will come up again later in our work, but for now we will use them only as general ideas. Korhonen and Lokshtanov and Le used these ideas to bound the L ∞ L_\infty L ∞ -concurrent flow problem, while Kolbe and Spalding-Jamieson used them to bound the L 2 L_2 L 2 -concurrent flow problem initially studied by Biswal, Lee, and Rao [6 ] . All of these bounds use the propositions in a straightforward manner: Assume the existence of a concurrent flow bypassing the claimed bound, sample u , v u,v u , v from V V V uniformly, and then sample a path from u u u to v v v using the flow values, obtaining a probability below the lower bounds in the propositions.
Kolbe and Spalding-Jamieson also lifted their bound to get a more general bound on the L 2 L_2 L 2 -subset flow problem initially studied by Kelner, Lee, Price, and Teng [17 ] . Subset flow problems (which are dual to “spreading metric” problems), are generally relaxations of balanced separator problems (see e.g. [12 ] ), so they are a natural tool to try and use for finding balanced separators. These problems can be formulated as follows, for a value 1 ≤ r ≤ n 1\le r\le n 1 ≤ r ≤ n , and various definitions of congestion:
min λ : ( V r ) → R ≥ 0 congestion ( ∑ A ∈ ( V r ) λ ( A ) F A ) F A a multicommodity flow in G for every A ∈ ( V r ) subject to ∑ A ∈ ( V r ) λ ( A ) = 1 , F A [ u , v ] = 1 r 2 for every A ∈ ( V r ) and u , v ∈ A , F A [ u , v ] = 0 for every A ∈ ( V r ) and u , v ∈ V with { u , v } ⊈ A . (1) \begin{aligned}
\min_{\lambda:\binom{V}{r}\to\mathbb{R}_{\ge0}} \quad& \operatorname{congestion}\left(\sum_{A\in\binom{V}{r}}\lambda(A)F_A\right) \\
& F_A\text{ a multicommodity flow in }G\text{ for every }A\in\binom{V}{r} \\
\text{subject to}\quad& \sum_{A\in\binom{V}{r}}\lambda(A)=1, \\
& F_A[u,v]=\frac{1}{r^2} \quad\text{for every }A\in\binom{V}{r}\text{ and }u,v\in A, \\
& F_A[u,v]=0 \quad\text{for every }A\in\binom{V}{r}\text{ and }u,v\in V\text{ with }\{u,v\}\not\subseteq A. \tag*{(1)}
\end{aligned} λ : ( r V ) → R ≥ 0 min subject to congestion A ∈ ( r V ) ∑ λ ( A ) F A F A a multicommodity flow in G for every A ∈ ( r V ) A ∈ ( r V ) ∑ λ ( A ) = 1 , F A [ u , v ] = r 2 1 for every A ∈ ( r V ) and u , v ∈ A , F A [ u , v ] = 0 for every A ∈ ( r V ) and u , v ∈ V with { u , v } ⊆ A . (1)
where F [ u , v ] F[u,v] F [ u , v ] denotes the amount of flow that a multicommodity flow F F F sends between u u u and v v v . This is equivalent to the form used by Kelner, Lee, Price, and Teng, but the form here is much more relevant to our purposes. In particular, these kinds of flows are quite similar to what we will use, while the objective we will use will be more directly inspired by the goal of leveraging the propositions.
The last ingredient is a slight modification of these subset flows inspired by Bonnet et al.’s “stochastic connectors” [5 ] . They define a stochastic connector as a collection of rooted trees, each containing a large number of vertices, so that the collision probability of rooted paths on distinct trees is bounded. While we will not leverage the specific parametrization of their definition, it turns out that this general idea is exactly what we need: Rooted trees can be viewed as a naturally structured variant of the flows F A F_A F A in Eq. (1) that are easy to work with and compute. The analogous flows here are those between pairs of vertices on the rooted tree, and they are sent only along the tree itself. Moreover, collision probability is exactly what will allow us to leverage Propositions 1 and 2. That said, rooted trees alone are not quite the right analogue, since they are slightly too restrictive. Instead, we define the idea of a wide connector : A rooted tree containing a subset of 3 n / 4 3n/4 3 n /4 specified terminals . The flows we use to sample our paths will then be the root-to-terminal paths, rather than all rooted paths.
Altogether, this would give us an objective, defined over wide connectors, given by the probability of the two different kinds of collisions bounded in Propositions 1 and 2 (with the two parameters controlling how to weigh the two kinds of collision). To simplify bookkeeping, we define our objective F μ , λ F_{\mu,\lambda} F μ , λ as a maximization problem capturing only the probability of collisions between distinct wide connectors, while also incorporating a term serving as an analogue to the total cost sum constraint in Eq. (1) (∑ λ ( A ) = 1 \sum\lambda(A)=1 ∑ λ ( A ) = 1 ). An extra constraint is also required so that our online learning algorithm is able to make sufficient forward progress (an analogue of “width” in many common learning algorithms). The precise choice is given in § 3.3 .
Step 2: Formulating an online learning problem. We formulate the two players of the learning game as follows. In each round t t t , the learner plays a vector λ t \lambda_t λ t of weights over all wide connectors, and the adversary responds with a loss function. We constrain the game so that, at each round t t t , λ t \lambda_t λ t has weight updates induced by at most one new wide connector (in fact, up to normalization only one entry changes), or the game is terminated early with a small balanced separator. If too many rounds complete (O ( h 2 ) O(h^2) O ( h 2 ) for K h K_h K h -minor-free graphs, O ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) O(|V(H)| + |E(H)|) O ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) for H H H -induced-minor-free graphs), an application of either Proposition 2 or Proposition 1 will be used to prove that the graph contains a minor or induced-minor, respectively.
Step 3: Implementing each round of the online learning problem using the FTRL framework. It remains to discuss several implementation details. First, during the course of the algorithm, we maintain the list of wide connectors C t C_t C t played so far, as well as a load vector p t p_t p t for each one, containing the probability of being an element of a sampled path (according to a certain distribution). We also maintain a prefix sum vector q t q_t q t of load vectors. At each iteration, the adversary uses these values to define a weight vector w t w_t w t over the vertices, inducing a vertex-weighted shortest-path metric (equivalently, an edge-weighted shortest-path metric where each edge u v uv uv is given weight 1 2 ( w t [ u ] + w t [ v ] ) \frac{1}{2}(w_t[u] + w_t[v]) 2 1 ( w t [ u ] + w t [ v ]) ). Using this metric, we will leverage a form of the flow-cut gap for induced-minor-free graphs. Davies, Rzążewski, Spalding-Jamieson, and Walczak recently proved the following result.
Theorem 4 ([11 Theorem 3.4] ). Let G = ( V , E ) G = (V, E) G = ( V , E ) be a graph with vertex weights w : V → R ≥ 0 w: V \to\mathbb{R}_{\ge0} w : V → R ≥ 0 , d = d w G d = d^G_w d = d w G be the vertex-weighted shortest-path metric of G G G , H H H be a graph with h V h_V h V vertices and h E ≥ 1 h_E \ge1 h E ≥ 1 edges, and δ , ϵ , η ≥ 0 \delta, \epsilon, \eta\ge0 δ , ϵ , η ≥ 0 . If ( 2 h V + 2 ) ϵ + ( h V + h E ) η < 1 (2h_V + 2)\epsilon+ (h_V + h_E)\eta< 1 ( 2 h V + 2 ) ϵ + ( h V + h E ) η < 1 , then, in time polynomial in ∣ V ∣ |V| ∣ V ∣ , one can obtain one of the following outputs:
a vertex x ∈ V x \in V x ∈ V with ∣ B ( x , 11 δ ) ∣ > η ∣ V ∣ |B(x, 11\delta)| > \eta|V| ∣ B ( x , 11 δ ) ∣ > η ∣ V ∣ ;
vertex sets A , B ⊆ V A, B \subseteq V A , B ⊆ V with ∣ A ∣ > ϵ ∣ V ∣ |A| > \epsilon|V| ∣ A ∣ > ϵ ∣ V ∣ , ∣ B ∣ > ϵ ∣ V ∣ |B| > \epsilon|V| ∣ B ∣ > ϵ ∣ V ∣ , and d ( A , B ) > δ d(A, B) > \delta d ( A , B ) > δ ;
an induced minor model of the 1-subdivision of H H H in G G G .
We give an expected-linear-time (for constant H H H ) analogue of this result for some specific choices of δ , ϵ , η \delta, \epsilon, \eta δ , ϵ , η in § 6 . The three outcome types induce different behaviors for the adversary: The first kind of outcome will be sufficient for the adversary to choose a new wide connector and use it to generate a corresponding loss function; the second kind of outcome would be needed in an iterative manner (which may instead terminate early with either the first or third kind of outcome), but would be eventually sufficient for the learner to produce a small separator, and the third kind of outcome of course gives an induced minor model in G G G .
For the first type of outcome, a loss function for the learning game is generated using a proxy objective G μ , ℓ ( p t ) G_{\mu,\ell}(p_t) G μ , ℓ ( p t ) , which itself is defined using a new load vector p t p_t p t and the prefix sum of previous load vectors q t q_t q t . These vectors, unlike λ t \lambda_t λ t , are of linear size, and are thus much easier to work with computationally. Our particular choice of G μ , ℓ G_{\mu,\ell} G μ , ℓ also gives us a direct relationship between ∇ G μ , ℓ ( λ ) \nabla G_{\mu,\ell}(\lambda) ∇ G μ , ℓ ( λ ) and the vertex-weighted graph radius. These are almost the weights induced above, except that we also require a regularization term as part of the FTRL framework, and some appropriate scaling. The scaling happens to correspond to the idea of a learning rate as defined in various optimization methods, as well as the diameter of our metric.
Note that the boundary between the learner and adversary (e.g., which one of them computes the vertex weights or the prefix sum) becomes fuzzy within the efficient implementation of the algorithm. In fact, in the actual algorithm we implement, the weights λ t \lambda_t λ t are not computed explicitly at all.
Preliminaries
We use mostly standard graph terminology. Given a graph H H H and a graph G G G , a minor model of H H H in G G G is a collection K \mathcal{K} K of vertex-disjoint connected subgraphs of G G G such that:
[Edge correspondence]: For every edge ( u , v ) ∈ E ( H ) (u,v) \in E(H) ( u , v ) ∈ E ( H ) , there is an edge in G G G between the two corresponding subgraphs C u C_u C u and C v C_v C v in K \mathcal{K} K .
G G G is H H H -minor-free if it does not contain a minor model for H H H .
We say that K \mathcal{K} K is an induced minor model of H H H in G G G , if, in addition to satisfying the vertex correspondence and edge correspondence properties above, it satisfies:
G G G is H H H -induced-minor-free if it does not contain an induced minor model for H H H . Because of the non-edge correspondence property, an H H H -induced-minor-free graph can be dense. For example, the clique K n K_n K n excludes P 2 P_2 P 2 (a path of length 2) as an induced minor. Every graph H H H with ∣ V ( H ) ∣ = h |V(H)| = h ∣ V ( H ) ∣ = h is an induced minor of K h ( 1 ) K_h^{(1)} K h ( 1 ) , so if G G G does not contain H H H as an induced minor, then it does not contain K h ( 1 ) K_h^{(1)} K h ( 1 ) as an induced minor either. Thus, in some parts of our paper, we work directly with K h ( 1 ) K_h^{(1)} K h ( 1 ) -induced-minor-free graphs.
We also use the following single-source shortest path algorithm on graphs with integer weights by Dial [9 ] .
Theorem 5 (Dial’s algorithm [9 ] ). Let G = ( V , E , w ) G = (V,E,w) G = ( V , E , w ) be a graph with integer weights on the edges. Let D D D be the diameter of G G G , n = ∣ V ∣ n = |V| n = ∣ V ∣ , and m = ∣ E ∣ m = |E| m = ∣ E ∣ . Then computing the single-source shortest path from any source vertex takes O ( n + m + D ) O(n + m + D) O ( n + m + D ) time.
Balanced Separators from Follow the Regularized Leader
Since our algorithms for balanced separators are inspired by the Follow the Regularized Leader (FTRL) framework in online learning, we first give a brief overview of online learning and FTRL.
Online Learning: A Primer
The setup. The general setup is a game over T T T rounds, where in each round t ∈ [ T ] t \in[T] t ∈ [ T ] , a player picks a vector x t ∈ X x_t \in\mathcal{X} x t ∈ X , called a strategy , where X ⊆ R d \mathcal{X} \subseteq\mathbb{R}^d X ⊆ R d is the domain. (Often X \mathcal{X} X is a convex set.) The player could choose x t x_t x t based on the information from previous rounds. Once the player chooses x t x_t x t , a loss function ℓ t : X → ( − ∞ , + ∞ ] \ell_t : \mathcal{X} \to(-\infty,+\infty] ℓ t : X → ( − ∞ , + ∞ ] is revealed; the player pays ℓ t ( x t ) \ell_t(x_t) ℓ t ( x t ) loss; and the game continues to the next round.
The goal of the player is to minimize the regret , defined as follows:
Regret ( x 1 , … , x T ) = sup u ∈ X ( ∑ t = 1 T ℓ t ( x t ) − ℓ t ( u ) ) (2) \operatorname{Regret}(x_1,\ldots,x_T)=\sup_{u\in\mathcal{X}}\left(\sum_{t=1}^{T}\ell_t(x_t)-\ell_t(u)\right) \tag*{(2)} Regret ( x 1 , … , x T ) = u ∈ X sup ( t = 1 ∑ T ℓ t ( x t ) − ℓ t ( u ) ) (2)
which is the loss difference w.r.t. the best fixed strategy.
Follow the regularized leader (FTRL) is a meta-algorithm that a player can use to pick a strategy x t ∈ X x_t \in\mathcal{X} x t ∈ X in every step. To apply this meta-algorithm, the player has to first choose a function ψ : X → R \psi:\mathcal{X}\to\mathbb{R} ψ : X → R called a regularizer . Once the regularizer is chosen, in every step t t t , the player chooses a strategy x t ∈ X x_t\in\mathcal{X} x t ∈ X that minimizes ψ ( x ) + ∑ i = 1 t − 1 ℓ i ( x ) \psi(x)+\sum_{i=1}^{t-1}\ell_i(x) ψ ( x ) + ∑ i = 1 t − 1 ℓ i ( x ) . That is:
x t = arg min x ∈ X ( ψ ( x ) + ∑ i = 1 t − 1 ℓ i ( x ) ) (3) x_t=\underset{x\in\mathcal{X}}{\operatorname{arg\,min}}\left(\psi(x)+\sum_{i=1}^{t-1}\ell_i(x)\right) \tag*{(3)} x t = x ∈ X arg min ( ψ ( x ) + i = 1 ∑ t − 1 ℓ i ( x ) ) (3)
The second term in Equation (3) is not hard to see: the only information given up to round t t t is the loss functions { ℓ i ( x ) } i < t \{\ell_i(x)\}_{i<t} { ℓ i ( x ) } i < t , and it makes sense to find a strategy for round t t t that minimizes the sum ∑ i = 1 t − 1 ℓ i ( x ) \sum_{i=1}^{t-1}\ell_i(x) ∑ i = 1 t − 1 ℓ i ( x ) . On the other hand, it is well known in online learning that minimizing this sum alone is not enough, since the adversary who knows the strategy could come up with a new loss next round to throw off the player; see, e.g., [33 ] . A simple fix that works well is to add the regularizer ψ ( x ) \psi(x) ψ ( x ) [2 ] . The algorithm’s pseudocode is given in Algorithm 1.
Algorithm 1 FTRL(ψ , X \psi,\mathcal{X} ψ , X ): Follow the Regularized Leader Meta-Algorithm
Input: Regularizer ψ : X → R \psi:\mathcal{X}\to\mathbb{R} ψ : X → R
Output: { x 1 , x 2 , … , x T } \{x_1,x_2,\ldots,x_T\} { x 1 , x 2 , … , x T }
for each round t ← 1 t\leftarrow1 t ← 1 to T T T do
pick x t ∈ arg min x ∈ X { ψ ( x ) + ∑ i = 1 t − 1 ℓ i ( x ) } x_t\in\underset{x\in\mathcal{X}}{\arg\min}\left\{\psi(x)+\sum_{i=1}^{t-1}\ell_i(x)\right\} x t ∈ x ∈ X arg min { ψ ( x ) + ∑ i = 1 t − 1 ℓ i ( x ) }
loss function ℓ t ( x ) : R d → ( − ∞ , + ∞ ] \ell_t(x):\mathbb{R}^d\to(-\infty,+\infty] ℓ t ( x ) : R d → ( − ∞ , + ∞ ] is revealed
player pays loss ℓ t ( x t ) \ell_t(x_t) ℓ t ( x t )
return { x 1 , x 2 , … , x T } \{x_1,x_2,\ldots,x_T\} { x 1 , x 2 , … , x T }
The choice of the regularizer matters in minimizing the regret bounds. We will not discuss the details of these choices, as we will not use these regret bounds in our paper. Curious readers are referred to [29 ] for details. Instead, we briefly review how FTRL solves a convex optimization problem, since our algorithms for balanced separators follow the same strategy.
Convex optimization via FTRL.
Given a convex function f ( x ) : X → R f(x):\mathcal{X}\to\mathbb{R} f ( x ) : X → R where X ⊆ R d \mathcal{X}\subseteq\mathbb{R}^d X ⊆ R d is convex, find:
arg min x ∈ X f ( x ) (4) \underset{x\in\mathcal{X}}{\arg\min}\ f(x) \tag*{(4)} x ∈ X arg min f ( x ) (4)
We can approximately solve this problem via the FTRL framework as follows. First, choose any initial feasible point x 0 ∈ X x_0\in\mathcal{X} x 0 ∈ X , a regularizer ψ ( x ) = η 2 ∥ x − x 0 ∥ 2 2 \psi(x)=\frac{\eta}{2}\lVert x-x_0\rVert_2^2 ψ ( x ) = 2 η ∥ x − x 0 ∥ 2 2 where η > 0 \eta>0 η > 0 is a parameter called the learning rate . Then we play the online game for T T T rounds (with T T T chosen later), but for doing so, we need to choose a loss function ℓ t ( x ) \ell_t(x) ℓ t ( x ) at each round t ∈ [ T ] t\in[T] t ∈ [ T ] .
We could simply choose ℓ t ( x ) = f ( x ) \ell_t(x)=f(x) ℓ t ( x ) = f ( x ) , but then ∑ i = 1 t − 1 ℓ i ( x ) = ( t − 1 ) f ( x ) \sum_{i=1}^{t-1}\ell_i(x)=(t-1)f(x) ∑ i = 1 t − 1 ℓ i ( x ) = ( t − 1 ) f ( x ) and hence finding x t x_t x t following Equation (3) is as hard as solving the original convex optimization problem in Equation (4) . Instead, we choose ℓ t ( x ) = ⟨ g t , x ⟩ \ell_t(x)=\langle g_t,x\rangle ℓ t ( x ) = ⟨ g t , x ⟩ where g t ∈ ∂ f ( x t ) g_t\in\partial f(x_t) g t ∈ ∂ f ( x t ) is a subgradient of f f f at x t x_t x t . Intuitively, ℓ t ( x ) \ell_t(x) ℓ t ( x ) is a linear approximation of f ( x ) f(x) f ( x ) at time t t t since by the definition of subgradient:
f ( x ) ≥ f ( x t ) + ⟨ g t , x − x t ⟩ (5) f(x)\ge f(x_t)+\langle g_t,x-x_t\rangle \tag*{(5)} f ( x ) ≥ f ( x t ) + ⟨ g t , x − x t ⟩ (5)
and hence, instead of minimizing f ( x ) f(x) f ( x ) directly (which is a hard problem), we minimize the linear lower bound. With this choice of ℓ t ( x ) \ell_t(x) ℓ t ( x ) , Equation (3) becomes:
x t = arg min x ∈ X ( η 2 ∥ x − x 0 ∥ 2 2 + ⟨ ∑ i = 1 t − 1 g i , x ⟩ ) , (6) x_t=\underset{x\in\mathcal{X}}{\arg\min}\left(\frac{\eta}{2}\lVert x-x_0\rVert_2^2+\left\langle\sum_{i=1}^{t-1}g_i,x\right\rangle\right), \tag*{(6)} x t = x ∈ X arg min ( 2 η ∥ x − x 0 ∥ 2 2 + ⟨ i = 1 ∑ t − 1 g i , x ⟩ ) , (6)
which is a simple quadratic function that is much easier to solve. After round T T T is completed, we simply return:
x ˉ = ∑ i = 1 T x i T (7) \bar{x}=\frac{\sum_{i=1}^{T}x_i}{T} \tag*{(7)} x ˉ = T ∑ i = 1 T x i (7)
as an approximate solution to Equation (4) . By choosing T T T and η \eta η appropriately, one can show that f ( x ˉ ) − f ( x ∗ ) ≤ ϵ f(\bar{x})-f(x^*)\le\epsilon f ( x ˉ ) − f ( x ∗ ) ≤ ϵ for any given ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) . Again, we will not reproduce the analysis here, but note two important points that are relevant to us:
Choosing the regularizer ψ ( x ) \psi(x) ψ ( x ) and the proxy loss function ℓ t ( x ) \ell_t(x) ℓ t ( x ) at each round t ∈ [ T ] t\in[T] t ∈ [ T ] is important for efficient computation of the strategy x t x_t x t at each step, as well as for obtaining a good approximate solution x ˉ \bar{x} x ˉ in the end.
Though the analysis of FTRL works out nicely if f ( x ) f(x) f ( x ) is convex, the algorithm also makes sense when f f f is non-convex. In the latter case, the kind of guarantee one gets from FTRL depends on how nicely f f f “behaves”.
In our setup of FTRL for balanced separators, we not only have to choose ψ ( x ) \psi(x) ψ ( x ) and { ℓ t ( x ) } t ∈ [ T ] \{\ell_t(x)\}_{t\in[T]} { ℓ t ( x ) } t ∈ [ T ] , but we also have to set up an appropriate function f f f , which turns out to be non-convex and very non-standard. Setting up f f f is the focus of the next section.
Balanced Vertex Separators as A Continuous Optimization Problem
A starting point to formulate our optimization problem is the intimate relationship between balanced separators and concurrent flow . Let P G \mathcal{P}_G P G be the set of all simple paths in an undirected graph G = ( V , E ) G=(V,E) G = ( V , E ) with n n n vertices and m m m edges. A concurrent flow λ : P G → [ 0 , 1 ] \lambda:\mathcal{P}_G\to[0,1] λ : P G → [ 0 , 1 ] assigns each simple path P ∈ P G P\in\mathcal{P}_G P ∈ P G a flow value λ ( P ) ∈ [ 0 , 1 ] \lambda(P)\in[0,1] λ ( P ) ∈ [ 0 , 1 ] such that for every ordered pair ( u , v ) ∈ V 2 (u,v)\in V^2 ( u , v ) ∈ V 2 , ∑ P ∈ P u v λ ( P ) = 1 / n \sum_{P\in\mathcal{P}_{uv}}\lambda(P)=1/n ∑ P ∈ P uv λ ( P ) = 1/ n where P u v ⊆ P G \mathcal{P}_{uv}\subseteq\mathcal{P}_G P uv ⊆ P G is the set of all simple paths from u u u to v v v . (Note that P u v = P v u \mathcal{P}_{uv}=\mathcal{P}_{vu} P uv = P v u since the graph is undirected). In words, a concurrent flow λ \lambda λ sends 1 unit of flow from every vertex to all other vertices, equally distributed. The congestion at u u u of the concurrent flow λ \lambda λ is ∑ P ∈ P G : u ∈ P λ ( P ) \sum_{P\in\mathcal{P}_G:u\in P}\lambda(P) ∑ P ∈ P G : u ∈ P λ ( P ) , and the congestion of λ \lambda λ is the maximum congestion over all vertices of V V V . It is well known that:
Theorem 6 (Leighton and Rao [23 ] ). For every ϕ ∈ ( 0 , 1 ) \phi\in(0,1) ϕ ∈ ( 0 , 1 ) , either:
G G G admits a balanced separator of size ϕ ⋅ n \phi\cdot n ϕ ⋅ n , or
G G G has an induced subgraph H H H on at least 2 n / 3 2n/3 2 n /3 vertices such that H H H admits a concurrent flow with congestion O ( log n / ϕ ) O(\log n/\phi) O ( log n / ϕ ) .
There are two closely related interpretations of Theorem 6 that are useful for us:
If we can send one unit of flow from every vertex to at least 2 n / 3 2n/3 2 n /3 other vertices with little congestion (large ϕ \phi ϕ ), then any balanced separator of G G G must be large.
Let O p t G \mathrm{Opt}_G Opt G be the size of the optimal balanced separator of G G G and ϕ = O p t G n ∈ ( 0 , 1 ] \phi=\frac{\mathrm{Opt}_G}{n}\in(0,1] ϕ = n Opt G ∈ ( 0 , 1 ] . Then:
total flow sent congestion ≈ n log ( n ) / ϕ ≈ O ~ ( 1 ) O p t G (8) \frac{\text{total flow sent}}{\text{congestion}}\approx\frac{n}{\log(n)/\phi}\approx\widetilde{O}(1)\mathrm{Opt}_G \tag*{(8)} congestion total flow sent ≈ log ( n ) / ϕ n ≈ O ( 1 ) Opt G (8)
The optimization problem. Instead of sending flow along paths as in the concurrent flow, we take a slightly different perspective: sending one unit of flow from each vertex u u u to 3 n / 4 3n/4 3 n /4 other vertices along a tree. This gives rise to a wide connector , a central concept in our formulation. More formally, a wide connector , denoted by C : = ( T , r , B ) C:=(T,r,B) C := ( T , r , B ) , is a tuple consisting of: (i) a rooted tree T T T , which is a (not necessarily spanning) subgraph of G G G , (ii) the root r r r of T T T , and (iii) a subset B ⊆ V B\subseteq V B ⊆ V of exactly 3 n / 4 3n/4 3 n /4 vertices5 that belongs to T T T . We call B B B the terminals of the connector C C C . Given a wide connector C = ( T , r , B ) C=(T,r,B) C = ( T , r , B ) , we define its load vector p C ∈ [ 0 , 1 ] n \mathbf{p}_C\in[0,1]^n p C ∈ [ 0 , 1 ] n as follows:
p C [ v ] = ∣ T v ∩ B ∣ ∣ B ∣ ∀ v ∈ V (9) \mathbf{p}_C[v]=\frac{|T_v\cap B|}{|B|}\qquad\forall v\in V \tag*{(9)} p C [ v ] = ∣ B ∣ ∣ T v ∩ B ∣ ∀ v ∈ V (9)
where T v T_v T v is the subtree of T T T rooted at v v v . A subtlety is that not every vertex belongs to T T T , and for such a vertex v v v , we set p C [ v ] = 0 p_C[v]=0 p C [ v ] = 0 . A useful interpretation of the load vector is: if we send 1 unit of flow from the root r r r to all vertices in B B B , equally distributed, along the tree T T T , then p C [ v ] p_C[v] p C [ v ] is the fraction of the flow going through v v v . Clearly, p C [ r ] = 1 p_C[r]=1 p C [ r ] = 1 and p C [ v ] ∈ [ 0 , 1 ] p_C[v]\in[0,1] p C [ v ] ∈ [ 0 , 1 ] for every v ∈ V v\in V v ∈ V .
Let T ( G ) \mathcal{T}(G) T ( G ) be the set of all rooted trees that are subgraphs of G G G . For every vertex u ∈ V u\in V u ∈ V , let C u \mathcal{C}_u C u be the set of all wide connectors rooted at u u u . Formally:
C u = { ( T , u , B ) : B ∈ ( V 3 n / 4 ) , T ∈ T ( G ) rooted at u and B ⊆ T } (10) \mathcal{C}_u=\left\{(T,u,B):B\in\binom{V}{3n/4},\ T\in\mathcal{T}(G)\text{ rooted at }u\text{ and }B\subseteq T\right\} \tag*{(10)} C u = { ( T , u , B ) : B ∈ ( 3 n /4 V ) , T ∈ T ( G ) rooted at u and B ⊆ T } (10)
Let C = ⋃ u ∈ V C u \mathcal{C}=\bigcup_{u\in V}\mathcal{C}_u C = ⋃ u ∈ V C u be the set of all wide connectors. Let μ \mu μ and ι \iota ι be two parameters chosen later. The optimization problem is formulated as follows:
max λ ∈ [ 0 , 1 ] ∣ C ∣ F μ , ι ( λ ) : = ∑ C ∈ C λ [ C ] − ∑ ( C , C ′ ) ∈ ( C 2 ) λ [ C ] λ [ C ′ ] ( μ ⟨ p C , p C ′ ⟩ + ι ∑ ( u , v ) ∈ E ( p C [ u ] p C ′ [ v ] + p C [ v ] p C ′ [ u ] ) ) (11) \max_{\lambda\in[0,1]^{|\mathcal{C}|}} F_{\mu,\iota}(\lambda) := \sum_{C\in\mathcal{C}}\lambda[C]-\sum_{(C,C')\in\binom{\mathcal{C}}{2}}\lambda[C]\lambda[C']\left(\mu\langle p_C,p_{C'}\rangle+\iota\sum_{(u,v)\in E}(p_C[u]p_{C'}[v]+p_C[v]p_{C'}[u])\right) \tag*{(11)} λ ∈ [ 0 , 1 ] ∣ C ∣ max F μ , ι ( λ ) := C ∈ C ∑ λ [ C ] − ( C , C ′ ) ∈ ( 2 C ) ∑ λ [ C ] λ [ C ′ ] μ ⟨ p C , p C ′ ⟩ + ι ( u , v ) ∈ E ∑ ( p C [ u ] p C ′ [ v ] + p C [ v ] p C ′ [ u ]) (11)
subject to ∑ C ∈ C u λ [ C ] ≤ 1 \sum_{C\in\mathcal{C}_u}\lambda[C]\leq1 ∑ C ∈ C u λ [ C ] ≤ 1 for every u ∈ V u\in V u ∈ V .
In this optimization problem:
for each connector C = ( T , r , B ) ∈ C C=(T,r,B)\in\mathcal{C} C = ( T , r , B ) ∈ C rooted at some vertex r r r , the variable λ [ C ] ∈ [ 0 , 1 ] \lambda[C]\in[0,1] λ [ C ] ∈ [ 0 , 1 ] denotes the amount of flow r C r_C r C sends to B B B along the tree T T T . Thus, the constraint ∑ C ∈ C u λ [ C ] ≤ 1 \sum_{C\in\mathcal{C}_u}\lambda[C]\leq1 ∑ C ∈ C u λ [ C ] ≤ 1 means that the total flow sent from vertex u u u to all other vertices is at most 1.
∑ C ∈ C λ [ C ] \sum_{C\in\mathcal{C}}\lambda[C] ∑ C ∈ C λ [ C ] is the total amount of flow sent from every node of G G G to all other nodes via the wide connectors.
The negative term encodes the flow congestion; it takes some effort to really see this, and we will expand on this term below. The parameters μ \mu μ and ι \iota ι determine how much we penalize the total flow sent, depending on the graph classes we are interested in. For example, for minor-free graphs, we set μ = 1 \mu=1 μ = 1 and ι = 0 \iota=0 ι = 0 , while for induced-minor-free graphs, we set μ = ι = 1 \mu=\iota=1 μ = ι = 1 .
Thus, the optimization in Equation (11) is to maximize the total flow sent through G G G via wide connectors, while minimizing the congestion.
Remark 1. λ ∈ [ 0 , 1 ] ∣ C ∣ \lambda\in[0,1]^{|\mathcal{C}|} λ ∈ [ 0 , 1 ] ∣ C ∣ has an exponential number of dimensions, and it is unclear how to solve the optimization problem in Equation (11) in polynomial time; at least, the optimization problem is non-convex.
Let:
H μ , ι ( p C , p C ′ ) = μ ⟨ p C , p C ′ ⟩ + ι ∑ ( u , v ) ∈ E ( p C [ u ] p C ′ [ v ] + p C [ v ] p C ′ [ u ] ) (12) H_{\mu,\iota}(p_C,p_{C'})=\mu\langle p_C,p_{C'}\rangle+\iota\sum_{(u,v)\in E}(p_C[u]p_{C'}[v]+p_C[v]p_{C'}[u]) \tag*{(12)} H μ , ι ( p C , p C ′ ) = μ ⟨ p C , p C ′ ⟩ + ι ( u , v ) ∈ E ∑ ( p C [ u ] p C ′ [ v ] + p C [ v ] p C ′ [ u ]) (12)
be the bilinear form of the interaction term. Then Equation (11) can be shortened to:
max λ ∈ [ 0 , 1 ] ∣ C ∣ F μ , ι ( λ ) : = ∑ C ∈ C λ [ C ] − ∑ ( C , C ′ ) ∈ ( C 2 ) λ [ C ] λ [ C ′ ] H μ , ι ( p C , p C ′ ) (13) \max_{\lambda\in[0,1]^{|\mathcal{C}|}} F_{\mu,\iota}(\lambda) := \sum_{C\in\mathcal{C}}\lambda[C]-\sum_{(C,C')\in\binom{\mathcal{C}}{2}}\lambda[C]\lambda[C']H_{\mu,\iota}(p_C,p_{C'}) \tag*{(13)} λ ∈ [ 0 , 1 ] ∣ C ∣ max F μ , ι ( λ ) := C ∈ C ∑ λ [ C ] − ( C , C ′ ) ∈ ( 2 C ) ∑ λ [ C ] λ [ C ′ ] H μ , ι ( p C , p C ′ ) (13)
subject to ∑ C ∈ C u λ [ C ] ≤ 1 \sum_{C\in\mathcal{C}_u}\lambda[C]\leq1 ∑ C ∈ C u λ [ C ] ≤ 1 for every u ∈ V u\in V u ∈ V .
This shorter form is useful for much of our analysis, by exploiting the fact that H μ , ι ( p C , p C ′ ) H_{\mu,\iota}(p_C,p_{C'}) H μ , ι ( p C , p C ′ ) is a bilinear form. In the next subsection, we describe how to approximately solve the optimization problem in Equation (11) using the FTRL framework laid out in § 3.1 .
On the congestion term. The congestion term in Equation (11) is motivated by the probabilistic perspective of wide connectors and the load vectors, inspired by the argument in [5 ] . For a fixed wide connector C = ( T , r , B ) C=(T,r,B) C = ( T , r , B ) , if we pick a random vertex b ∈ B b\in B b ∈ B , then p C [ v ] p_C[v] p C [ v ] in Equation (9) is exactly the probability that v ∈ T [ r , b ] v\in T[r,b] v ∈ T [ r , b ] . Consider the following process to sample two paths in G G G , for a feasible λ \lambda λ with at least two positive entries: sample two distinct wide connectors C ≠ C ′ C\ne C' C = C ′ with probability proportional to λ [ C ] λ [ C ′ ] \lambda[C]\lambda[C'] λ [ C ] λ [ C ′ ] , and then sample a random root-to-terminal path from each of them, namely P P P from C C C and P ′ P' P ′ from C ′ C' C ′ . Then:
the probability that P P P and P ′ P' P ′ share a vertex is at most:
∑ ( C , C ′ ) ∈ ( C 2 ) ∑ v ∈ V ( λ [ C ] p C [ v ] ) ( λ [ C ′ ] p C ′ [ v ] ) ∑ ( C , C ′ ) ∈ ( C 2 ) λ [ C ] λ [ C ′ ] = ∑ ( C , C ′ ) ∈ ( C 2 ) λ [ C ] λ [ C ′ ] ⟨ p C , p C ′ ⟩ ∑ ( C , C ′ ) ∈ ( C 2 ) λ [ C ] λ [ C ′ ] . \frac{\sum_{(C,C')\in\binom{\mathcal{C}}{2}}\sum_{v\in V}\left(\lambda[C]p_C[v]\right)\left(\lambda[C']p_{C'}[v]\right)}{\sum_{(C,C')\in\binom{\mathcal{C}}{2}}\lambda[C]\lambda[C']}=\frac{\sum_{(C,C')\in\binom{\mathcal{C}}{2}}\lambda[C]\lambda[C']\langle p_C,p_{C'}\rangle}{\sum_{(C,C')\in\binom{\mathcal{C}}{2}}\lambda[C]\lambda[C']}. ∑ ( C , C ′ ) ∈ ( 2 C ) λ [ C ] λ [ C ′ ] ∑ ( C , C ′ ) ∈ ( 2 C ) ∑ v ∈ V ( λ [ C ] p C [ v ] ) ( λ [ C ′ ] p C ′ [ v ] ) = ∑ ( C , C ′ ) ∈ ( 2 C ) λ [ C ] λ [ C ′ ] ∑ ( C , C ′ ) ∈ ( 2 C ) λ [ C ] λ [ C ′ ] ⟨ p C , p C ′ ⟩ .
Thus, the term ∑ ( C , C ′ ) ∈ ( C 2 ) λ [ C ] λ [ C ′ ] μ ⟨ p C , p C ′ ⟩ \sum_{(C,C')\in\binom{\mathcal{C}}{2}}\lambda[C]\lambda[C']\mu\langle p_C,p_{C'}\rangle ∑ ( C , C ′ ) ∈ ( 2 C ) λ [ C ] λ [ C ′ ] μ ⟨ p C , p C ′ ⟩ in Equation (11) captures the collision probability of two random paths. In K h K_h K h -minor-free graphs, the collision probability of random paths is closely related to the size of the clique minor [5 ] . Thus, by penalizing the optimization problem in Equation (11) with this collision probability, we indirectly encode the structure of K h K_h K h -minor-free graphs.
the probability that P P P and P ′ P' P ′ are connected by an edge ( u , v ) ∈ E (u,v)\in E ( u , v ) ∈ E , namely that either u ∈ P u\in P u ∈ P and v ∈ P ′ v\in P' v ∈ P ′ or v ∈ P v\in P v ∈ P and u ∈ P ′ u\in P' u ∈ P ′ , is at most:
∑ ( C , C ′ ) ∈ ( C 2 ) ∑ ( u , v ) ∈ E ( ( λ [ C ] p C [ u ] ) ( λ [ C ′ ] p C ′ [ v ] ) + ( λ [ C ] p C [ v ] ) ( λ [ C ′ ] p C ′ [ u ] ) ) ∑ ( C , C ′ ) ∈ ( C 2 ) λ [ C ] λ [ C ′ ] = ∑ ( C , C ′ ) ∈ ( C 2 ) λ [ C ] λ [ C ′ ] ∑ ( u , v ) ∈ E ( p C [ u ] p C ′ [ v ] + p C [ v ] p C ′ [ u ] ) ∑ ( C , C ′ ) ∈ ( C 2 ) λ [ C ] λ [ C ′ ] (14) \begin{aligned}
&\frac{\sum_{(C,C')\in\binom{\mathcal{C}}{2}}\sum_{(u,v)\in E}\left((\lambda[C]p_C[u])(\lambda[C']p_{C'}[v])+(\lambda[C]p_C[v])(\lambda[C']p_{C'}[u])\right)}{\sum_{(C,C')\in\binom{\mathcal{C}}{2}}\lambda[C]\lambda[C']}\\
&=\frac{\sum_{(C,C')\in\binom{\mathcal{C}}{2}}\lambda[C]\lambda[C']\sum_{(u,v)\in E}(p_C[u]p_{C'}[v]+p_C[v]p_{C'}[u])}{\sum_{(C,C')\in\binom{\mathcal{C}}{2}}\lambda[C]\lambda[C']} \tag*{(14)}
\end{aligned} ∑ ( C , C ′ ) ∈ ( 2 C ) λ [ C ] λ [ C ′ ] ∑ ( C , C ′ ) ∈ ( 2 C ) ∑ ( u , v ) ∈ E ( ( λ [ C ] p C [ u ]) ( λ [ C ′ ] p C ′ [ v ]) + ( λ [ C ] p C [ v ]) ( λ [ C ′ ] p C ′ [ u ]) ) = ∑ ( C , C ′ ) ∈ ( 2 C ) λ [ C ] λ [ C ′ ] ∑ ( C , C ′ ) ∈ ( 2 C ) λ [ C ] λ [ C ′ ] ∑ ( u , v ) ∈ E ( p C [ u ] p C ′ [ v ] + p C [ v ] p C ′ [ u ]) (14)
Thus, the term ∑ ( u , v ) ∈ E ( p C [ u ] p C ′ [ v ] + p C [ v ] p C ′ [ u ] ) \sum_{(u,v)\in E}(p_C[u]p_{C'}[v]+p_C[v]p_{C'}[u]) ∑ ( u , v ) ∈ E ( p C [ u ] p C ′ [ v ] + p C [ v ] p C ′ [ u ]) in Equation (11) captures the probability that two random paths are connected by an edge. This probability is closely related to the size of an induced minor of G G G [16 ] .
FTRL using Low-Diameter Clusters
Our goal is to solve:
max λ ∈ [ 0 , 1 ] ∣ C ∣ F μ , ι ( λ ) subject to ∑ C ∈ C u λ [ C ] ≤ 1 for every u ∈ V \max_{\lambda\in[0,1]^{|\mathcal{C}|}} F_{\mu,\iota}(\lambda)\quad\text{subject to}\quad\sum_{C\in\mathcal{C}_u}\lambda[C]\le1\quad\text{for every }u\in V λ ∈ [ 0 , 1 ] ∣ C ∣ max F μ , ι ( λ ) subject to C ∈ C u ∑ λ [ C ] ≤ 1 for every u ∈ V
where F μ , ι ( λ ) F_{\mu,\iota}(\lambda) F μ , ι ( λ ) is defined in Equation (11) . Following the FTRL framework, in each round t t t we are going to pick:
λ t ∈ arg max λ ∈ [ 0 , 1 ] ∣ C ∣ { ψ ( λ ) + ∑ i = 1 t − 1 ℓ i ( λ ) } \lambda_t\in\operatorname*{arg\,max}_{\lambda\in[0,1]^{|\mathcal{C}|}}\left\{\psi(\lambda)+\sum_{i=1}^{t-1}\ell_i(\lambda)\right\} λ t ∈ λ ∈ [ 0 , 1 ] ∣ C ∣ arg max { ψ ( λ ) + i = 1 ∑ t − 1 ℓ i ( λ ) }
and a loss ℓ t ( λ ) \ell_t(\lambda) ℓ t ( λ ) which is the proxy for F μ , ι ( λ ) F_{\mu,\iota}(\lambda) F μ , ι ( λ ) . However, doing so here is particularly non-trivial since the dimension of λ \lambda λ is ∣ C ∣ |\mathcal{C}| ∣ C ∣ , which is exponential. To get around this issue, we need to simplify F μ , ι ( λ ) F_{\mu,\iota}(\lambda) F μ , ι ( λ ) .
Simplifying the problem. First, in every step, we choose λ t \lambda_t λ t that has only one non-zero entry; all other entries are 0 0 0 . This means at step t t t , we will find only one wide connector C t C_t C t such that λ t [ C t ] ≠ 0 \lambda_t[C_t]\ne0 λ t [ C t ] = 0 , while λ t [ C ] = 0 \lambda_t[C]=0 λ t [ C ] = 0 for every C ∈ C ∖ { C t } C\in\mathcal{C}\setminus\{C_t\} C ∈ C ∖ { C t } . Second, we are going to set λ t [ C t ] = 1 \lambda_t[C_t]=1 λ t [ C t ] = 1 for every t ∈ [ T ] t\in[T] t ∈ [ T ] . That means in every round we will send 1 unit of flow along the tree of C t C_t C t from the root. Third, to find C t C_t C t at step t t t , we restrict the set C \mathcal{C} C in the definition of F μ , ι ( λ ) F_{\mu,\iota}(\lambda) F μ , ι ( λ ) to C t = { C 1 , … , C t } \mathcal{C}_t=\{C_1,\ldots,C_t\} C t = { C 1 , … , C t } where C 1 , … , C t − 1 C_1,\ldots,C_{t-1} C 1 , … , C t − 1 are the wide connectors obtained in the previous steps 1 , 2 , … , t − 1 1,2,\ldots,t-1 1 , 2 , … , t − 1 . All of the wide connectors are known except C t C_t C t . To simplify the notation, we denote the load vector p C t p_{C_t} p C t of the wide connector C t C_t C t by p t p_t p t for t ∈ [ T ] t\in[T] t ∈ [ T ] . With these simplifications, the problem (at step t t t ), which is arg max λ ∈ [ 0 , 1 ] ∣ C ∣ F μ , ι ( λ ) \operatorname*{arg\,max}_{\lambda\in[0,1]^{|\mathcal{C}|}}F_{\mu,\iota}(\lambda) arg max λ ∈ [ 0 , 1 ] ∣ C ∣ F μ , ι ( λ ) , becomes:
arg max C t ∈ C ( ∑ C ∈ C t λ [ C ] − ∑ ( C , C ′ ) ∈ ( C t 2 ) λ [ C ] λ [ C ′ ] H μ , ι ( p C , p C ′ ) ) = arg max C t ∈ C ( t − ∑ { i , j } ∈ ( [ t ] 2 ) H μ , ι ( p i , p j ) ) (since λ [ C i ] = 1 ∀ 1 ≤ i ≤ t ) = arg min C t ∈ C ( ∑ { i , j } ∈ ( [ t ] 2 ) H μ , ι ( p i , p j ) ) (dropping constant t ) = arg min C t ∈ C ( ∑ { i , j } ∈ ( [ t ] 2 ) μ ⟨ p i , p j ⟩ + ι ∑ ( u , v ) ∈ E ( p i [ u ] p j [ v ] + p i [ v ] p j [ u ] ) ) (by Equation (12)) = arg min C t ∈ C ( μ ∑ i = 1 t − 1 ⟨ p i , p t ⟩ + ι ∑ 1 ≤ i ≤ t − 1 ∑ ( u , v ) ∈ E ( p i [ u ] p t [ v ] + p i [ v ] p t [ u ] ) ) = arg min C t ∈ C ( μ ⟨ q t , p t ⟩ + ι ∑ ( u , v ) ∈ E ( q t [ u ] p t [ v ] + q t [ v ] p t [ u ] ) ) (by defining q t : = ∑ i = 1 t − 1 p i ) : = arg min C t ∈ C G μ , ι ( p t ) (15) \begin{aligned}
\operatorname*{arg\,max}_{C_t\in\mathcal{C}}\left(\sum_{C\in C_t}\lambda[C]-\sum_{(C,C')\in\binom{C_t}{2}}\lambda[C]\lambda[C']H_{\mu,\iota}(p_C,p_{C'})\right)
&=\operatorname*{arg\,max}_{C_t\in\mathcal{C}}\left(t-\sum_{\{i,j\}\in\binom{[t]}{2}}H_{\mu,\iota}(p_i,p_j)\right) \quad\text{(since \(\lambda[C_i]=1\ \forall1\le i\le t\))}\\
&=\operatorname*{arg\,min}_{C_t\in\mathcal{C}}\left(\sum_{\{i,j\}\in\binom{[t]}{2}}H_{\mu,\iota}(p_i,p_j)\right) \quad\text{(dropping constant \(t\))}\\
&=\operatorname*{arg\,min}_{C_t\in\mathcal{C}}\left(\sum_{\{i,j\}\in\binom{[t]}{2}}\mu\langle p_i,p_j\rangle+\iota\sum_{(u,v)\in E}(p_i[u]p_j[v]+p_i[v]p_j[u])\right) \quad\text{(by Equation (12))}\\
&=\operatorname*{arg\,min}_{C_t\in\mathcal{C}}\left(\mu\sum_{i=1}^{t-1}\langle p_i,p_t\rangle+\iota\sum_{1\le i\le t-1}\sum_{(u,v)\in E}(p_i[u]p_t[v]+p_i[v]p_t[u])\right)\\
&=\operatorname*{arg\,min}_{C_t\in\mathcal{C}}\left(\mu\langle q_t,p_t\rangle+\iota\sum_{(u,v)\in E}(q_t[u]p_t[v]+q_t[v]p_t[u])\right) \quad\text{(by defining \(q_t:=\sum_{i=1}^{t-1}p_i\))}\\
&:=\operatorname*{arg\,min}_{C_t\in\mathcal{C}}G_{\mu,\iota}(p_t) \tag*{(15)}
\end{aligned} C t ∈ C arg max C ∈ C t ∑ λ [ C ] − ( C , C ′ ) ∈ ( 2 C t ) ∑ λ [ C ] λ [ C ′ ] H μ , ι ( p C , p C ′ ) = C t ∈ C arg max t − { i , j } ∈ ( 2 [ t ] ) ∑ H μ , ι ( p i , p j ) (since λ [ C i ] = 1 ∀1 ≤ i ≤ t ) = C t ∈ C arg min { i , j } ∈ ( 2 [ t ] ) ∑ H μ , ι ( p i , p j ) (dropping constant t ) = C t ∈ C arg min { i , j } ∈ ( 2 [ t ] ) ∑ μ ⟨ p i , p j ⟩ + ι ( u , v ) ∈ E ∑ ( p i [ u ] p j [ v ] + p i [ v ] p j [ u ]) (by Equation (12)) = C t ∈ C arg min μ i = 1 ∑ t − 1 ⟨ p i , p t ⟩ + ι 1 ≤ i ≤ t − 1 ∑ ( u , v ) ∈ E ∑ ( p i [ u ] p t [ v ] + p i [ v ] p t [ u ]) = C t ∈ C arg min μ ⟨ q t , p t ⟩ + ι ( u , v ) ∈ E ∑ ( q t [ u ] p t [ v ] + q t [ v ] p t [ u ]) (by defining q t := ∑ i = 1 t − 1 p i ) := C t ∈ C arg min G μ , ι ( p t ) (15)
Observation 1. Function G μ , ι ( p t ) G_{\mu,\iota}(p_t) G μ , ι ( p t ) defined in Equation (15) is a linear function in p t p_t p t , and the gradient:
∇ p t G μ , ι ( p t ) [ v ] = μ q t [ v ] + ι ∑ u ∈ N G ( v ) q t [ u ] (16) \nabla_{p_t}G_{\mu,\iota}(p_t)[v]=\mu q_t[v]+\iota\sum_{u\in N_G(v)}q_t[u] \tag*{(16)} ∇ p t G μ , ι ( p t ) [ v ] = μ q t [ v ] + ι u ∈ N G ( v ) ∑ q t [ u ] (16)
for every v ∈ V v\in V v ∈ V .
Recall that p t p_t p t is the load vector of the (unknown) wide connector C t C_t C t , and hence the allowable values for p t p_t p t form a (finite) discrete set of exponential size. This is the key difficulty in minimizing G μ , ι ( p t ) G_{\mu,\iota}(p_t) G μ , ι ( p t ) , even though it is a linear function of p t p_t p t . The next step, which arguably is the most innovative step, is to connect optimizing for G μ , ι ( p t ) G_{\mu,\iota}(p_t) G μ , ι ( p t ) with low-diameter clusters.
Connection to low-diameter clusters. Note that G μ , ι ( p t ) = ⟨ ∇ p t G μ , ι ( p t ) , p t ⟩ G_{\mu,\iota}(p_t)=\langle\nabla_{p_t}G_{\mu,\iota}(p_t),p_t\rangle G μ , ι ( p t ) = ⟨ ∇ p t G μ , ι ( p t ) , p t ⟩ since G μ , ι ( p t ) G_{\mu,\iota}(p_t) G μ , ι ( p t ) is linear. The following lemma connects G μ , ι ( p t ) G_{\mu,\iota}(p_t) G μ , ι ( p t ) to the graph diameter.
Lemma 1. Let w ~ ∈ R ≥ 0 V \widetilde{w}\in\mathbb{R}_{\ge0}^{V} w ∈ R ≥ 0 V be any non-negative vector. Let C t = ( X , r , B ) C_t=(X,r,B) C t = ( X , r , B ) be a wide connector and p t p_t p t be its load vector. Suppose that we assign every vertex v ∈ V v\in V v ∈ V a weight w ~ [ v ] \widetilde{w}[v] w [ v ] . Let Q Q Q be a random path of X X X obtained by sampling a vertex b ∈ B b\in B b ∈ B uniformly at random and returning the b b b -to-root path X [ r , b ] X[r,b] X [ r , b ] . Then the expected weight of the path is:
E [ w ~ ( Q ) ] = ⟨ w ~ , p t ⟩ (17) \mathbb{E}[\widetilde{w}(Q)]=\langle\widetilde{w},p_t\rangle \tag*{(17)} E [ w ( Q )] = ⟨ w , p t ⟩ (17) As a result, ⟨ w ~ , p t ⟩ ≤ D \langle\widetilde{w},p_t\rangle\le D ⟨ w , p t ⟩ ≤ D where D D D is the vertex-weighted radius of X X X centered at r r r .
Proof. By definition of the load vector, Pr [ v ∈ X [ r , b ] ] = p t [ v ] \Pr[v\in X[r,b]]=p_t[v] Pr [ v ∈ X [ r , b ]] = p t [ v ] . Thus:
E [ w ~ ( Q ) ] = ∑ v ∈ V ( X ) Pr [ v ∈ Q ] w ~ [ v ] = ⟨ w ~ , p t ⟩ \mathbb{E}[\widetilde{w}(Q)]=\sum_{v\in V(X)}\Pr[v\in Q]\widetilde{w}[v]=\langle\widetilde{w},p_t\rangle E [ w ( Q )] = v ∈ V ( X ) ∑ Pr [ v ∈ Q ] w [ v ] = ⟨ w , p t ⟩ as vertices u u u not in X X X have p t [ u ] = 0 p_t[u]=0 p t [ u ] = 0 . □
By Lemma 1, if we assign each vertex v v v in the tree of the wide connector C t C_t C t a weight ∇ p t G μ , ι ( p t ) [ v ] \nabla_{p_t}G_{\mu,\iota}(p_t)[v] ∇ p t G μ , ι ( p t ) [ v ] , then G μ , ι ( p t ) G_{\mu,\iota}(p_t) G μ , ι ( p t ) , which is ⟨ ∇ p t G μ , ι ( p t ) , p t ⟩ \langle\nabla_{p_t}G_{\mu,\iota}(p_t),p_t\rangle ⟨ ∇ p t G μ , ι ( p t ) , p t ⟩ , is the expected weight of a random path in the tree. Thus, to minimize G μ , ι ( p t ) G_{\mu,\iota}(p_t) G μ , ι ( p t ) , a natural idea is to: (i) assign every vertex v v v of G G G a weight ∇ p t G μ , ι ( p t ) [ v ] \nabla_{p_t}G_{\mu,\iota}(p_t)[v] ∇ p t G μ , ι ( p t ) [ v ] , (ii) find a shortest path tree T T T of G G G w.r.t. the weight function ∇ p t G μ , ι ( p t ) \nabla_{p_t}G_{\mu,\iota}(p_t) ∇ p t G μ , ι ( p t ) , and (iii) cut off the tree at a small radius in such a way that at least 3 n / 4 3n/4 3 n /4 vertices are still in the tree. (If the tree has small radius, then a random path to the root would have small expected weight, and hence small G μ , ι ( p t ) G_{\mu,\iota}(p_t) G μ , ι ( p t ) .) A small radius in (iii) might not exist, and this is where Theorem 7 below comes into play. It gives either a cluster of more than 3 n / 4 3n/4 3 n /4 vertices with small diameter, or a small balanced separator in G G G . In the latter case, we simply stop the algorithm and return the separator.
For vertex weights w w w and a path P P P , let w ( P ) : = ∑ v ∈ P w ( v ) w(P):=\sum_{v\in P}w(v) w ( P ) := ∑ v ∈ P w ( v ) . Let K h ( 1 ) K_h^{(1)} K h ( 1 ) be the graph obtained from K h K_h K h by subdividing every edge once. Every K h K_h K h -minor-free graph excludes K h ( 1 ) K_h^{(1)} K h ( 1 ) as an induced minor, and so does every H H H -induced-minor-free graph with h = ∣ V ( H ) ∣ h=|V(H)| h = ∣ V ( H ) ∣ .
Theorem 7. Let h ≥ 2 h\ge2 h ≥ 2 , and let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph with n n n vertices and m m m edges that excludes K h ( 1 ) K_h^{(1)} K h ( 1 ) as an induced minor. Let w : V → Z ≥ 1 w:V\to\mathbb{Z}_{\ge1} w : V → Z ≥ 1 be vertex weights, W : = ∑ v ∈ V w ( v ) W:=\sum_{v\in V}w(v) W := ∑ v ∈ V w ( v ) , and 0 < D ≤ n 0<D\le n 0 < D ≤ n . There is a randomized algorithm CUTORCLUSTER ( G , h , w , D ) \operatorname{CUTORCLUSTER}(G,h,w,D) CUTORCLUSTER ( G , h , w , D ) that returns one of the following:
a cluster : a set K ⊆ V K\subseteq V K ⊆ V with ∣ K ∣ > 3 n / 4 |K|>3n/4 ∣ K ∣ > 3 n /4 such that G [ K ] G[K] G [ K ] has vertex-weight diameter at most D D D : every two vertices of K K K are joined by a path P P P in G [ K ] G[K] G [ K ] with w ( P ) ≤ D w(P)\le D w ( P ) ≤ D , or
a balanced separator : a set S ⊆ V S\subseteq V S ⊆ V with ∣ S ∣ = O ( W log ( h W / n ) / D ) |S|=O(W\log(hW/n)/D) ∣ S ∣ = O ( W log ( hW / n ) / D ) such that every connected component of G − S G-S G − S has at most 3 n / 4 3n/4 3 n /4 vertices.
Its expected running time is O ( h 5 ( T S S S P ( n + 1 , m + n , 2 W ) + m + n ) ) O(h^5(T_{\mathrm{SSSP}}(n+1,m+n,2W)+m+n)) O ( h 5 ( T SSSP ( n + 1 , m + n , 2 W ) + m + n )) , where T S S S P ( N , M , L ) T_{\mathrm{SSSP}}(N,M,L) T SSSP ( N , M , L ) is the time to compute a shortest-path tree from a single source in a graph with at most N N N vertices, at most M M M edges, and integer edge lengths with maximum distance at most L L L .
We prove Theorem 7 in Section 6, building on a structural result of [11 ] . We note that while Theorem 7 is formalized for induced-minor-free graphs, it applies equally well to minor-free graphs, and we actually use it to prove our separator result for minor-free graphs.
In our implementation, instead of assigning the weight exactly ∇ p t G μ , ι ( p t ) [ v ] \nabla_{p_t}G_{\mu,\iota}(p_t)[v] ∇ p t G μ , ι ( p t ) [ v ] to every vertex v v v , we will assign this weight scaled by a diameter parameter D > 0 D>0 D > 0 ; it is 4 D 4D 4 D to be precise. (And we also have to take into account the regularization following the FTRL framework.) Concretely, we assign a weight:
w t [ v ] = ( 1 + n deg ( v ) 2 m ) + 4 D ∇ p t G μ , ι ( p t ) [ v ] = ( 1 + n deg ( v ) 2 m ) + 4 D ( μ q t [ v ] + ι ∑ u ∈ N G ( v ) q t [ u ] ) , (18) \begin{aligned}
w_t[v]=\left(1+\frac{n\deg(v)}{2m}\right)+4D\nabla_{p_t}G_{\mu,\iota}(p_t)[v] \\
&=\left(1+\frac{n\deg(v)}{2m}\right)+4D\left(\mu q_t[v]+\iota\sum_{u\in N_G(v)}q_t[u]\right), \tag*{(18)}
\end{aligned} w t [ v ] = ( 1 + 2 m n deg ( v ) ) + 4 D ∇ p t G μ , ι ( p t ) [ v ] = ( 1 + 2 m n deg ( v ) ) + 4 D μ q t [ v ] + ι u ∈ N G ( v ) ∑ q t [ u ] , (18)
for every v ∈ V v\in V v ∈ V . The first term is the regularization: it is the gradient of the linear regularizer
ψ ( λ ) : = 1 4 D ∑ C ∈ C λ [ C ] ∑ v ∈ V ( 1 + n deg ( v ) 2 m ) p C [ v ] , (19) \psi(\lambda):=\frac{1}{4D}\sum_{C\in\mathcal{C}}\lambda[C]\sum_{v\in V}\left(1+\frac{n\deg(v)}{2m}\right)p_C[v], \tag*{(19)} ψ ( λ ) := 4 D 1 C ∈ C ∑ λ [ C ] v ∈ V ∑ ( 1 + 2 m n deg ( v ) ) p C [ v ] , (19)
so for the indicator vector λ t \lambda_t λ t of C t C_t C t , maximizing ψ ( λ t ) \psi(\lambda_t) ψ ( λ t ) plus the objective in Equation (15) is the same as minimizing ⟨ w t , p t ⟩ \langle w_t,p_t\rangle ⟨ w t , p t ⟩ . Its role is to make w t [ v ] ≥ 1 w_t[v]\ge1 w t [ v ] ≥ 1 with ∑ v ∈ V ( 1 + n deg ( v ) 2 m ) = 2 n \sum_{v\in V}\left(1+\frac{n\deg(v)}{2m}\right)=2n ∑ v ∈ V ( 1 + 2 m n d e g ( v ) ) = 2 n , which the bounds on ∥ w t ∥ 1 \lVert w_t\rVert_1 ∥ w t ∥ 1 use. In convex optimization using gradient descent, D D D corresponds to the learning rate ; in our discrete setting, it is the diameter. Now we have everything we need for the FTRL algorithm.
The algorithm. Let us briefly recap the discussion up to this point. At each step t t t of the FTRL framework, we find a wide connector C t ∈ C C_t\in\mathcal{C} C t ∈ C that minimizes Equation (15) . To do so, we assign every vertex v ∈ V v\in V v ∈ V a weight w t [ v ] w_t[v] w t [ v ] in Equation (18) . We then apply CUTORCLUSTER \operatorname{CUTORCLUSTER} CUTORCLUSTER from Theorem 7 to G G G w.r.t. the vertex weight function [ w t ] [w_t] [ w t ] with diameter parameter D D D . Here [ w t ] [w_t] [ w t ] is the component-wise ceiling of w t w_t w t ; that is, [ w t ] [ v ] = ⌈ w t [ v ] ⌉ [w_t][v]=\lceil w_t[v]\rceil [ w t ] [ v ] = ⌈ w t [ v ]⌉ for every v ∈ V v \in V v ∈ V . If it gives a balanced separator (no connected component contains more than 3 n / 4 3n/4 3 n /4 vertices), we return it. Otherwise, it gives a cluster K K K of more than 3 n / 4 3n/4 3 n /4 vertices, and we form a wide connector C t C_t C t that contains the shortest path tree (with vertex weight ⌈ w t ⌉ \lceil w_t\rceil ⌈ w t ⌉ ) of G [ K ] G[K] G [ K ] . The pseudocode is given in Algorithm 2 below.
Algorithm 2 CLUSTER-FTRL(G , h , T , D , μ , ι G,h,T,D,\mu,\iota G , h , T , D , μ , ι )
Input: h h h such that G G G excludes K h ( 1 ) K_h^{(1)} K h ( 1 ) as an induced minor, T T T = number of FTRL rounds, D D D = diameter parameter, { μ , ι } \{\mu,\iota\} { μ , ι } = parameters in the unified optimization problem in Equation (11) .
Output: either a balanced separator, or a set of wide connectors { C t } t ∈ [ T ] T \{C_t\}_{t\in[T]}^T { C t } t ∈ [ T ] T , each with λ [ C t ] = 1 \lambda[C_t]=1 λ [ C t ] = 1 .
q 1 ← 0 q_1 \gets0 q 1 ← 0
for t ← 1 t \gets1 t ← 1 to T T T do
w t [ v ] ← ( 1 + n deg ( v ) 2 m ) + 4 D ( μ q t [ v ] + ι ∑ u ∈ N G ( v ) q t [ u ] ) w_t[v]\gets\left(1+\frac{n\deg(v)}{2m}\right)+4D\left(\mu q_t[v]+\iota\sum_{u\in N_G(v)}q_t[u]\right) w t [ v ] ← ( 1 + 2 m n d e g ( v ) ) + 4 D ( μ q t [ v ] + ι ∑ u ∈ N G ( v ) q t [ u ] ) for every v ∈ V v\in V v ∈ V
run CUTORCLUSTER( G , h , ⌈ w t ⌉ , D ) (G,h,\lceil w_t\rceil,D) ( G , h , ⌈ w t ⌉ , D ) ▷ Theorem 7
if it returns a balanced separator S t S_t S t then
return S t S_t S t ▷ S t S_t S t is a balanced separator
K ← K\gets K ← the returned cluster
r t ← r_t\gets r t ← a vertex in K K K that is not a root of any existing connector ▷ we will send 1 flow from r t r_t r t
X t ← X_t\gets X t ← vertex-weighted shortest-path tree of G [ K ] G[K] G [ K ] w.r.t. ⌈ w t ⌉ \lceil w_t\rceil ⌈ w t ⌉ rooted at r t r_t r t .
B t ← B_t\gets B t ← an arbitrary set of 3 n / 4 3n/4 3 n /4 vertices of K ∖ { r t } K\setminus\{r_t\} K ∖ { r t } .
C t ← ( X t , r t , B t ) C_t\gets(X_t,r_t,B_t) C t ← ( X t , r t , B t ) , and p t ← p_t\gets p t ← the load vector of C t C_t C t ▷ the wide connector
q t + 1 ← q t + p t q_{t+1}\gets q_t+p_t q t + 1 ← q t + p t
return C T : = { C 1 , C 2 , … , C T } C_T:=\{C_1,C_2,\ldots,C_T\} C T := { C 1 , C 2 , … , C T }
We use ⌈ w t ⌉ \lceil w_t\rceil ⌈ w t ⌉ as the weights rather than w t w_t w t for efficient shortest-path computation in linear time (for a fixed h h h ). If we are willing to tolerate a factor of log n \log n log n in the running time, then we can work with w t w_t w t (though the proof is not simpler in any way).
The following lemma gives the lower bound on the optimal value of the optimization problem in Equation (11) after T T T rounds of CLUSTER-FTRL.
Lemma 2 (Cluster-FTRL Progress). Suppose that Algorithm 2 outputs C T C_T C T after T T T rounds. Let λ ˉ \bar{\lambda} λ ˉ be a vector such that, for every wide connector C ∈ C C\in\mathcal{C} C ∈ C :
λ ˉ [ C ] = { 0 if C ∉ C T 1 otherwise (20) \bar{\lambda}[C]=
\begin{cases}
0 & \text{if } C\notin C_T\\
1 & \text{otherwise}
\end{cases} \tag*{(20)} λ ˉ [ C ] = { 0 1 if C ∈ / C T otherwise (20) Then λ ˉ \bar{\lambda} λ ˉ is a feasible solution of the optimization problem in Equation (11) with value:
F μ , ι ( λ ˉ ) ≥ 3 T / 4 (21) F_{\mu,\iota}(\bar{\lambda})\ge3T/4 \tag*{(21)} F μ , ι ( λ ˉ ) ≥ 3 T /4 (21)
Proof: We note that connectors in C T C_T C T are pairwise distinct since they have different roots due to line 8 in Algorithm 2. Recall in Equation (12)
H μ , ι ( p C , p C ′ ) = μ ⟨ p C , p C ′ ⟩ + ι ∑ ( u , v ) ∈ E ( p C [ u ] p C ′ [ v ] + p C [ v ] p C ′ [ u ] ) . H_{\mu,\iota}(p_C,p_{C'})=\mu\langle p_C,p_{C'}\rangle+\iota\sum_{(u,v)\in E}\left(p_C[u]p_{C'}[v]+p_C[v]p_{C'}[u]\right). H μ , ι ( p C , p C ′ ) = μ ⟨ p C , p C ′ ⟩ + ι ( u , v ) ∈ E ∑ ( p C [ u ] p C ′ [ v ] + p C [ v ] p C ′ [ u ] ) .
Observe that H μ , ι ( p C , p C ′ ) H_{\mu,\iota}(p_C,p_{C'}) H μ , ι ( p C , p C ′ ) is bilinear w.r.t. the variables p C p_C p C and p C ′ p_{C'} p C ′ . We write:
F μ , ι ( λ ˉ ) = ∑ C ∈ C λ ˉ [ C ] − ∑ ( C , C ′ ) ∈ ( C 2 ) λ ˉ [ C ] λ ˉ [ C ′ ] H μ , ι ( p C , p C ′ ) = T − ∑ ( C , C ′ ) ∈ ( C T 2 ) H μ , ι ( p C , p C ′ ) = T − ∑ t = 1 T ∑ i = 1 t − 1 H μ , ι ( p i , p t ) = T − ∑ t = 1 T H μ , ι ( ∑ i = 1 t − 1 p i , p t ) (since H μ , ι is bilinear) = T − ∑ t = 1 T H μ , ι ( q t , p t ) (by definition of q t in Algorithm 2) (22) \begin{aligned}
F_{\mu,\iota}(\bar{\lambda}) &= \sum_{C\in\mathcal{C}} \bar{\lambda}[C] - \sum_{(C,C')\in\binom{\mathcal{C}}{2}} \bar{\lambda}[C]\bar{\lambda}[C']H_{\mu,\iota}(p_C,p_{C'}) \\
&= T-\sum_{(C,C')\in\binom{\mathcal{C}_T}{2}} H_{\mu,\iota}(p_C,p_{C'}) \\
&= T-\sum_{t=1}^{T}\sum_{i=1}^{t-1}H_{\mu,\iota}(p_i,p_t) \\
&= T-\sum_{t=1}^{T}H_{\mu,\iota}\left(\sum_{i=1}^{t-1}p_i,p_t\right) \qquad\text{(since $H_{\mu,\iota}$ is bilinear)} \\
&= T-\sum_{t=1}^{T}H_{\mu,\iota}(q_t,p_t) \qquad\text{(by definition of $q_t$ in Algorithm 2)} \tag*{(22)}
\end{aligned} F μ , ι ( λ ˉ ) = C ∈ C ∑ λ ˉ [ C ] − ( C , C ′ ) ∈ ( 2 C ) ∑ λ ˉ [ C ] λ ˉ [ C ′ ] H μ , ι ( p C , p C ′ ) = T − ( C , C ′ ) ∈ ( 2 C T ) ∑ H μ , ι ( p C , p C ′ ) = T − t = 1 ∑ T i = 1 ∑ t − 1 H μ , ι ( p i , p t ) = T − t = 1 ∑ T H μ , ι ( i = 1 ∑ t − 1 p i , p t ) (since H μ , ι is bilinear) = T − t = 1 ∑ T H μ , ι ( q t , p t ) (by definition of q t in Algorithm 2) (22)
Next, we show Equation (23) below, which together with Equation (22) , implies F μ , ι ( λ ˉ ) ≥ T − T / 4 = 3 T / 4 F_{\mu,\iota}(\bar{\lambda}) \ge T-T/4=3T/4 F μ , ι ( λ ˉ ) ≥ T − T /4 = 3 T /4 as desired.
H μ , ι ( q t , p t ) ≤ 1 / 4 (23) H_{\mu,\iota}(q_t,p_t)\le1/4 \tag*{(23)} H μ , ι ( q t , p t ) ≤ 1/4 (23)
To see this, observe that by applying Lemma 1 to p t p_t p t and ⌈ w t ⌉ \lceil w_t\rceil ⌈ w t ⌉ , we get ⟨ ⌈ w t ⌉ , p t ⟩ ≤ D \langle\lceil w_t\rceil,p_t\rangle\le D ⟨⌈ w t ⌉ , p t ⟩ ≤ D , giving:
⟨ w t , p t ⟩ ≤ ⟨ ⌈ w t ⌉ , p t ⟩ ≤ D \langle w_t,p_t\rangle\le\langle\lceil w_t\rceil,p_t\rangle\le D ⟨ w t , p t ⟩ ≤ ⟨⌈ w t ⌉ , p t ⟩ ≤ D
By definition of w t w_t w t in line 3 of Algorithm 2, we have w t [ v ] ≥ 4 D ( μ q t [ v ] + ι ∑ u ∈ N G ( v ) q t [ u ] ) w_t[v]\ge4D(\mu q_t[v]+\iota\sum_{u\in N_G(v)}q_t[u]) w t [ v ] ≥ 4 D ( μ q t [ v ] + ι ∑ u ∈ N G ( v ) q t [ u ]) , and hence:
D ≥ ⟨ w t , p t ⟩ ≥ 4 D ( μ ⟨ q t , p t ⟩ + ι ∑ u v ∈ E ( q t [ u ] p t [ v ] + q t [ v ] p t [ u ] ) ) = 4 D H μ , ι ( q t , p t ) D\ge\langle w_t,p_t\rangle\ge4D\left(\mu\langle q_t,p_t\rangle+\iota\sum_{uv\in E}(q_t[u]p_t[v]+q_t[v]p_t[u])\right)=4DH_{\mu,\iota}(q_t,p_t) D ≥ ⟨ w t , p t ⟩ ≥ 4 D ( μ ⟨ q t , p t ⟩ + ι uv ∈ E ∑ ( q t [ u ] p t [ v ] + q t [ v ] p t [ u ]) ) = 4 D H μ , ι ( q t , p t )
giving Equation (23) . □
Balanced Separators for Minor-Free Graphs
In this section, G G G is a K h K_h K h -minor-free graph for an integer h ≥ 3 h\ge3 h ≥ 3 . We apply the FTRL algorithm (Algorithm 2) with the following parameters. The number of FTRL rounds is T = c ⋅ h 2 T=c\cdot h^2 T = c ⋅ h 2 for a sufficiently large constant c c c chosen later. We set the diameter parameter D = n / T D=\sqrt{n/T} D = n / T in Algorithm 2.
Our goal here is to show by contradiction that the FTRL algorithm in Algorithm 2 will not run all T T T rounds. That is, it will return a balanced separator in line 6. By Lemma 2, after T T T rounds, we have found a feasible solution with value at least 3 T / 4 = 3 c h 2 / 4 3T/4=3ch^2/4 3 T /4 = 3 c h 2 /4 . The following lemma bounds the value of the optimization problem in Equation (11) by O ( h 2 ) O(h^2) O ( h 2 ) . Thus, as long as we choose c c c sufficiently large, the algorithm must terminate before round T T T .
Lemma 3. Let λ \lambda λ be any feasible solution of the optimization problem in Equation (11) with μ = 1 \mu=1 μ = 1 and ι = 0 \iota=0 ι = 0 . If G G G is K h K_h K h -minor-free, then:
F 1 , 0 ( λ ) = O ( h 2 ) (24) F_{1,0}(\lambda)=O(h^2) \tag*{(24)} F 1 , 0 ( λ ) = O ( h 2 ) (24)
We delay the proof of Lemma 3 to Section 4.1. Instead, we will continue with the analysis of the FTRL algorithm for minor-free graphs, specifically bounding the size of the output separator. To this end, we bound the ℓ 1 \ell_1 ℓ 1 -norm of w t w_t w t .
Lemma 4. In every round ∥ w t ∥ 1 ≤ 6 n \lVert w_t\rVert_1\le6n ∥ w t ∥ 1 ≤ 6 n .
Proof: Applying Lemma 1 to p t p_t p t and ⌈ w t ⌉ \lceil w_t\rceil ⌈ w t ⌉ , we get ⟨ ⌈ w t ⌉ , p t ⟩ ≤ D \langle\lceil w_t\rceil,p_t\rangle\le D ⟨⌈ w t ⌉ , p t ⟩ ≤ D , giving:
⟨ w t , p t ⟩ ≤ ⟨ ⌈ w t ⌉ , p t ⟩ ≤ D \langle w_t,p_t\rangle\le\langle\lceil w_t\rceil,p_t\rangle\le D ⟨ w t , p t ⟩ ≤ ⟨⌈ w t ⌉ , p t ⟩ ≤ D
Since w t [ v ] ≥ 1 w_t[v]\ge1 w t [ v ] ≥ 1 for every v ∈ V v\in V v ∈ V by the definition, we have:
∥ p t ∥ 1 ≤ ⟨ w t , p t ⟩ ≤ D (25) \lVert p_t\rVert_1\le\langle w_t,p_t\rangle\le D \tag*{(25)} ∥ p t ∥ 1 ≤ ⟨ w t , p t ⟩ ≤ D (25)
and hence by the definition of q t q_t q t :
∥ q t ∥ 1 = ∥ ∑ i = 1 t − 1 p i ∥ 1 ≤ ( t − 1 ) D ≤ T D \lVert q_t\rVert_1=\left\lVert\sum_{i=1}^{t-1}p_i\right\rVert_1\le(t-1)D\le TD ∥ q t ∥ 1 = i = 1 ∑ t − 1 p i 1 ≤ ( t − 1 ) D ≤ T D
Now we can bound ∥ w t ∥ 1 \lVert w_t\rVert_1 ∥ w t ∥ 1 . By the definition and the fact that μ = 1 , ι = 0 \mu=1,\iota=0 μ = 1 , ι = 0 , we get:
∥ w t ∥ 1 = n + n ∑ v deg ( v ) 2 m + 4 D ∥ q t ∥ 1 ≤ n + n + 4 D ( T D ) = 2 n + 4 ( n / T ) 2 T ≤ 6 n \lVert w_t\rVert_1=n+\frac{n\sum_{v}\deg(v)}{2m}+4D\lVert q_t\rVert_1
\le n+n+4D(TD)=2n+4(\sqrt{n/T})^2T\le6n ∥ w t ∥ 1 = n + 2 m n ∑ v deg ( v ) + 4 D ∥ q t ∥ 1 ≤ n + n + 4 D ( T D ) = 2 n + 4 ( n / T ) 2 T ≤ 6 n
as claimed. □
Theorem 2. Let G G G be a K h K_h K h -minor-free graph with n n n vertices and m m m edges. There is a randomized algorithm that returns a 3 / 4 3/4 3/4 -balanced separator of size O ( h log h n ) O(h\log h\sqrt{n}) O ( h log h n ) in expected O ( h 7 ( m + n ) ) O(h^7(m+n)) O ( h 7 ( m + n )) time.
Proof: By Lemma 3 and Lemma 2, by choosing c c c (in the definition of T T T ) sufficiently large, the FTRL algorithm (Algorithm 2) will terminate before T T T rounds. Therefore, CutOrCluster ( G , h , ⌈ w t ⌉ , D ) \operatorname{CutOrCluster}(G,h,\lceil w_t\rceil,D) CutOrCluster ( G , h , ⌈ w t ⌉ , D ) returns a separator S S S . Let W = ∑ v ∈ V ⌈ w t ⌉ [ v ] ≤ n + ∑ v ∈ V w t [ v ] ≤ 7 n W=\sum_{v\in V}\lceil w_t\rceil[v]\le n+\sum_{v\in V}w_t[v]\le7n W = ∑ v ∈ V ⌈ w t ⌉ [ v ] ≤ n + ∑ v ∈ V w t [ v ] ≤ 7 n by Lemma 4. By Theorem 7, we have
∣ S ∣ = O ( W log ( h W / n ) D ) = O ( 7 n log ( 7 h ) T / n ) = O ( h log h n ) (since T = O ( h 2 ) ) (26) |S|=O\left(\frac{W\log(hW/n)}{D}\right)
=O\left(7n\log(7h)\sqrt{T/n}\right)
=O(h\log h\sqrt{n})\qquad\text{(since }T=O(h^2)\text{)} \tag*{(26)} ∣ S ∣ = O ( D W log ( hW / n ) ) = O ( 7 n log ( 7 h ) T / n ) = O ( h log h n ) (since T = O ( h 2 ) ) (26) as claimed. For the running time, we note that the vertex weights are integers of total weight at most W ≤ 7 n W\le7n W ≤ 7 n . Thus, a single-source shortest path tree can be computed in time O ( n + m + W ) = O ( n + m ) O(n+m+W)=O(n+m) O ( n + m + W ) = O ( n + m ) by Dial’s algorithm in Theorem 5. Then by Theorem 7, the total expected running time is O ( T ⋅ h 5 ( m + n ) ) = O ( h 7 ( m + n ) ) O(T\cdot h^5(m+n))=O(h^7(m+n)) O ( T ⋅ h 5 ( m + n )) = O ( h 7 ( m + n )) . □
Proof of lm:opt-bound-minor
We use a known collision probability bound that follows from a variant of an argument by Korhonen and Lokshtanov for induced-minor-free graphs [16 ] , later modified by Le [21 ] for minor-free graphs, and further generalized by Kolbe and Spalding-Jamieson [19 ] for a slightly more general task. We specifically use an intermediate form of the construction in the proof by Kolbe and Spalding-Jamieson.
Proposition 2 (adapted from [19 ] , proof of Proposition 3.2). Let G G G be a K h K_h K h -minor-free graph, where h ≥ 3 h\ge3 h ≥ 3 , and let π \pi π be a probability distribution on V ( G ) V(G) V ( G ) . Sample u , v u,v u , v independently from π \pi π , then sample a simple u u u –v v v path P P P from any fixed distribution for that ordered pair. If u = v u=v u = v , take P = { u } P=\{u\} P = { u } . For an independent sample P ′ P' P ′ resulting from the same process,
Pr [ V ( P ) ∩ V ( P ′ ) ≠ ∅ ] ≥ c 0 h 2 , \Pr[V(P)\cap V(P')\ne\varnothing]\ge\frac{c_0}{h^2}, Pr [ V ( P ) ∩ V ( P ′ ) = ∅ ] ≥ h 2 c 0 , where c 0 > 0 c_0>0 c 0 > 0 is an absolute constant.
Proof: The random-path argument in [19 proof of Proposition 3.2] (see also [21 Section 4] ) produces a K h K_h K h -minor if
Pr [ V ( P ) ∩ V ( P ′ ) ≠ ∅ ] ≤ ( 1 50 h + 1 2500 h 2 ) 2 . \Pr[V(P)\cap V(P')\ne\varnothing]\leq\left(\frac{1}{50h}+\frac{1}{2500h^2}\right)^2. Pr [ V ( P ) ∩ V ( P ′ ) = ∅ ] ≤ ( 50 h 1 + 2500 h 2 1 ) 2 .
Since G G G is K h K_h K h -minor-free, it follows that
Pr [ V ( P ) ∩ V ( P ′ ) ≠ ∅ ] > ( 1 50 h + 1 2500 h 2 ) 2 ≥ 1 2500 h 2 . \Pr[V(P)\cap V(P')\ne\varnothing]>\left(\frac{1}{50h}+\frac{1}{2500h^2}\right)^2\geq\frac{1}{2500h^2}. Pr [ V ( P ) ∩ V ( P ′ ) = ∅ ] > ( 50 h 1 + 2500 h 2 1 ) 2 ≥ 2500 h 2 1 .
Thus the claim holds with c 0 = 1 / 2500 c_0=1/2500 c 0 = 1/2500 . □
This is all we will need to prove Lemma 3.
Proof of Lemma 3. The case λ = 0 \lambda=0 λ = 0 is immediate, so assume λ ≠ 0 \lambda\ne0 λ = 0 . Write C = ( T C , r C , B C ) C=(T_C,r_C,B_C) C = ( T C , r C , B C ) for each connector. Sample two connectors C 1 , C 2 C_1,C_2 C 1 , C 2 independently with probabilities λ [ C ] / ∥ λ ∥ 1 \lambda[C]/\|\lambda\|_1 λ [ C ] /∥ λ ∥ 1 , and then sample z z z uniformly from B C 1 ∩ B C 2 B_{C_1}\cap B_{C_2} B C 1 ∩ B C 2 . Let Q i Q_i Q i be the r C i r_{C_i} r C i –z z z path in T C i T_{C_i} T C i , for i = 1 , 2 i=1,2 i = 1 , 2 . Concatenate Q 1 Q_1 Q 1 and Q 2 Q_2 Q 2 , erasing cycles, to get a path P P P with independent, identically distributed endpoints, where P = { r C 1 } P=\{r_{C_1}\} P = { r C 1 } if r C 1 = r C 2 r_{C_1}=r_{C_2} r C 1 = r C 2 .
Fix C 1 , C 2 C_1,C_2 C 1 , C 2 and i ∈ { 1 , 2 } i\in\{1,2\} i ∈ { 1 , 2 } . By the definition of p C i [ v ] p_{C_i}[v] p C i [ v ] , exactly ∣ B C i ∣ ⋅ p C i [ v ] |B_{C_i}|\cdot p_{C_i}[v] ∣ B C i ∣ ⋅ p C i [ v ] terminals in B C i B_{C_i} B C i have a root-to-terminal path containing v v v . Restricting to terminals in B C 1 ∩ B C 2 B_{C_1}\cap B_{C_2} B C 1 ∩ B C 2 cannot increase this count. Since Q i = T C i [ r C i , z ] Q_i=T_{C_i}[r_{C_i},z] Q i = T C i [ r C i , z ] and z z z is uniform in that intersection, counting the possible values of z z z gives
Pr [ v ∈ V ( Q i ) ∣ C 1 , C 2 ] = Pr [ v ∈ V ( T C i [ r C i , z ] ) ∣ C 1 , C 2 ] = ∣ { z ∗ ∈ B C 1 ∩ B C 2 : v ∈ V ( T C i [ r C i , z ∗ ] ) } ∣ ∣ B C 1 ∩ B C 2 ∣ ≤ ∣ B C i ∣ ⋅ p C i [ v ] ∣ B C 1 ∩ B C 2 ∣ ≤ 3 n / 4 n / 2 p C i [ v ] = 3 2 p C i [ v ] . \begin{aligned}
\Pr[v\in V(Q_i)\mid C_1,C_2]=\Pr[v\in V(T_{C_i}[r_{C_i},z])\mid C_1,C_2] \\
&=\frac{\left|\{z^*\in B_{C_1}\cap B_{C_2}:v\in V(T_{C_i}[r_{C_i},z^*])\}\right|}{|B_{C_1}\cap B_{C_2}|} \\
&\leq\frac{|B_{C_i}|\cdot p_{C_i}[v]}{|B_{C_1}\cap B_{C_2}|}\leq\frac{3n/4}{n/2}p_{C_i}[v]=\frac{3}{2}p_{C_i}[v].
\end{aligned} Pr [ v ∈ V ( Q i ) ∣ C 1 , C 2 ] = Pr [ v ∈ V ( T C i [ r C i , z ]) ∣ C 1 , C 2 ] = ∣ B C 1 ∩ B C 2 ∣ ∣ { z ∗ ∈ B C 1 ∩ B C 2 : v ∈ V ( T C i [ r C i , z ∗ ])} ∣ ≤ ∣ B C 1 ∩ B C 2 ∣ ∣ B C i ∣ ⋅ p C i [ v ] ≤ n /2 3 n /4 p C i [ v ] = 2 3 p C i [ v ] .
Repeat the construction independently, with connectors C 1 ′ , C 2 ′ C'_1,C'_2 C 1 ′ , C 2 ′ and paths Q 1 ′ , Q 2 ′ , P ′ Q'_1,Q'_2,P' Q 1 ′ , Q 2 ′ , P ′ . Fix i , j ∈ { 1 , 2 } i,j\in\{1,2\} i , j ∈ { 1 , 2 } and condition on all four connectors. The two terminal choices are independent, since the constructions use independent random choices. For C i ≠ C j ′ C_i\ne C'_j C i = C j ′ , a union bound gives
Pr [ V ( Q i ) ∩ V ( Q j ′ ) ≠ ∅ ∣ C 1 , C 2 , C 1 ′ , C 2 ′ ] ≤ ∑ v Pr [ v ∈ V ( Q i ) , v ∈ V ( Q j ′ ) ∣ C 1 , C 2 , C 1 ′ , C 2 ′ ] = ∑ v Pr [ v ∈ V ( Q i ) ∣ C 1 , C 2 ] Pr [ v ∈ V ( Q j ′ ) ∣ C 1 ′ , C 2 ′ ] ≤ 9 4 ∑ v p C i [ v ] p C j ′ [ v ] . \begin{aligned}
\Pr[V(Q_i)\cap V(Q'_j)\ne\varnothing\mid C_1,C_2,C'_1,C'_2] \\
&\leq\sum_v\Pr[v\in V(Q_i),\,v\in V(Q'_j)\mid C_1,C_2,C'_1,C'_2] \\
&=\sum_v\Pr[v\in V(Q_i)\mid C_1,C_2]\Pr[v\in V(Q'_j)\mid C'_1,C'_2] \\
&\leq\frac{9}{4}\sum_v p_{C_i}[v]p_{C'_j}[v].
\end{aligned} Pr [ V ( Q i ) ∩ V ( Q j ′ ) = ∅ ∣ C 1 , C 2 , C 1 ′ , C 2 ′ ] ≤ v ∑ Pr [ v ∈ V ( Q i ) , v ∈ V ( Q j ′ ) ∣ C 1 , C 2 , C 1 ′ , C 2 ′ ] = v ∑ Pr [ v ∈ V ( Q i ) ∣ C 1 , C 2 ] Pr [ v ∈ V ( Q j ′ ) ∣ C 1 ′ , C 2 ′ ] ≤ 4 9 v ∑ p C i [ v ] p C j ′ [ v ] .
For C i = C j ′ C_i=C'_j C i = C j ′ , both paths contain the same root, so this same intersection probability is 1. The connectors C 1 , C 2 , C 1 ′ , C 2 ′ C_1,C_2,C'_1,C'_2 C 1 , C 2 , C 1 ′ , C 2 ′ are independent samples from the distribution λ [ C ] / ∥ λ ∥ 1 \lambda[C]/\|\lambda\|_1 λ [ C ] /∥ λ ∥ 1 . Hence, by using expectation over all four connector choices, we get
Pr [ V ( Q i ) ∩ V ( Q j ′ ) ≠ ∅ ] = E [ Pr [ V ( Q i ) ∩ V ( Q j ′ ) ≠ ∅ ∣ C 1 , C 2 , C 1 ′ , C 2 ′ ] ] ≤ ∑ C λ [ C ] 2 ∥ λ ∥ 1 2 + ∑ C ≠ D λ [ C ] λ [ D ] ∥ λ ∥ 1 2 9 4 ⟨ p C , p D ⟩ . \begin{aligned}
\Pr[V(Q_i)\cap V(Q'_j)\ne\varnothing]=\mathbb{E}\left[\Pr[V(Q_i)\cap V(Q'_j)\ne\varnothing\mid C_1,C_2,C'_1,C'_2]\right] \\
&\leq\sum_C\frac{\lambda[C]^2}{\|\lambda\|_1^2}+\sum_{C\ne D}\frac{\lambda[C]\lambda[D]}{\|\lambda\|_1^2}\frac{9}{4}\langle p_C,p_D\rangle.
\end{aligned} Pr [ V ( Q i ) ∩ V ( Q j ′ ) = ∅ ] = E [ Pr [ V ( Q i ) ∩ V ( Q j ′ ) = ∅ ∣ C 1 , C 2 , C 1 ′ , C 2 ′ ] ] ≤ C ∑ ∥ λ ∥ 1 2 λ [ C ] 2 + C = D ∑ ∥ λ ∥ 1 2 λ [ C ] λ [ D ] 4 9 ⟨ p C , p D ⟩ .
Another union bound gives
Pr [ V ( P ) ∩ V ( P ′ ) ≠ ∅ ] ≤ ∑ i = 1 2 ∑ j = 1 2 Pr [ V ( Q i ) ∩ V ( Q j ′ ) ≠ ∅ ] ≤ 4 ∑ C λ [ C ] 2 + 9 ∑ C ≠ D λ [ C ] λ [ D ] ⟨ p C , p D ⟩ ∥ λ ∥ 1 2 . \begin{aligned}
\Pr[V(P)\cap V(P')\ne\varnothing]\leq\sum_{i=1}^{2}\sum_{j=1}^{2}\Pr[V(Q_i)\cap V(Q'_j)\ne\varnothing] \\
&\leq\frac{4\sum_C\lambda[C]^2+9\sum_{C\ne D}\lambda[C]\lambda[D]\langle p_C,p_D\rangle}{\|\lambda\|_1^2}.
\end{aligned} Pr [ V ( P ) ∩ V ( P ′ ) = ∅ ] ≤ i = 1 ∑ 2 j = 1 ∑ 2 Pr [ V ( Q i ) ∩ V ( Q j ′ ) = ∅ ] ≤ ∥ λ ∥ 1 2 4 ∑ C λ [ C ] 2 + 9 ∑ C = D λ [ C ] λ [ D ] ⟨ p C , p D ⟩ .
To apply Proposition 2, observe that the endpoints of P P P are r C 1 , r C 2 r_{C_1}, r_{C_2} r C 1 , r C 2 . In particular, they are independently chosen using the distribution
π ( v ) = ∑ C : r C = v λ [ C ] ∥ λ ∥ 1 . \pi(v) = \sum_{C:r_C=v} \frac{\lambda[C]}{\|\lambda\|_1}. π ( v ) = C : r C = v ∑ ∥ λ ∥ 1 λ [ C ] .
Thus P , P ′ P,P' P , P ′ satisfy the hypotheses of Proposition 2, giving
c 0 h 2 ≤ Pr [ V ( P ) ∩ V ( P ′ ) ≠ ∅ ] . \frac{c_0}{h^2} \leq\Pr[V(P) \cap V(P') \ne\varnothing]. h 2 c 0 ≤ Pr [ V ( P ) ∩ V ( P ′ ) = ∅ ] .
Using the definition of F 1 , 0 F_{1,0} F 1 , 0 and λ [ C ] 2 ≤ λ [ C ] \lambda[C]^2 \leq\lambda[C] λ [ C ] 2 ≤ λ [ C ] , the lower and upper bounds therefore yield
c 0 h 2 ≤ 4 ∑ C λ [ C ] 2 + 18 ( ∥ λ ∥ 1 − F 1 , 0 ( λ ) ) ∥ λ ∥ 1 2 ≤ 22 ∥ λ ∥ 1 − 18 F 1 , 0 ( λ ) ∥ λ ∥ 1 2 . \frac{c_0}{h^2} \leq\frac{4\sum_C \lambda[C]^2 + 18(\|\lambda\|_1-F_{1,0}(\lambda))}{\|\lambda\|_1^2} \leq\frac{22\|\lambda\|_1-18F_{1,0}(\lambda)}{\|\lambda\|_1^2}. h 2 c 0 ≤ ∥ λ ∥ 1 2 4 ∑ C λ [ C ] 2 + 18 ( ∥ λ ∥ 1 − F 1 , 0 ( λ )) ≤ ∥ λ ∥ 1 2 22∥ λ ∥ 1 − 18 F 1 , 0 ( λ ) .
Rearranging yields
F 1 , 0 ( λ ) ≤ 11 9 ∥ λ ∥ 1 − c 0 ∥ λ ∥ 1 2 18 h 2 . F_{1,0}(\lambda) \leq\frac{11}{9}\|\lambda\|_1-\frac{c_0\|\lambda\|_1^2}{18h^2}. F 1 , 0 ( λ ) ≤ 9 11 ∥ λ ∥ 1 − 18 h 2 c 0 ∥ λ ∥ 1 2 .
The right-hand side is a concave quadratic in ∥ λ ∥ 1 \|\lambda\|_1 ∥ λ ∥ 1 , maximized at
∥ λ ∥ 1 = 11 h 2 c 0 . \|\lambda\|_1 = \frac{11h^2}{c_0}. ∥ λ ∥ 1 = c 0 11 h 2 .
Substituting this value gives
F 1 , 0 ( λ ) ≤ 121 h 2 18 c 0 = O ( h 2 ) . F_{1,0}(\lambda) \leq\frac{121h^2}{18c_0}=O(h^2). F 1 , 0 ( λ ) ≤ 18 c 0 121 h 2 = O ( h 2 ) .
Balanced Separators for Induced-Minor-Free Graphs
In this section, G G G is H H H -induced-minor-free for some fixed graph H H H . We set μ = 1 , ι = 1 \mu=1,\iota=1 μ = 1 , ι = 1 in the optimization problem Equation (11) . We apply the FTRL Algorithm 2 with T = c ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) T=c(|V(H)|+|E(H)|) T = c ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) for a sufficiently large constant c c c chosen later, and D = n / m T D=n/\sqrt{mT} D = n / m T . Similar to the minor-free case, we will show that the FTRL algorithm will terminate before T T T rounds, by upper bounding the value of the optimal solution.
Lemma 5. Let λ \lambda λ be any feasible solution of the optimization problem in Equation (11) with μ = ι = 1 \mu=\iota=1 μ = ι = 1 . If G G G is H H H -induced-minor-free, then:
F 1 , 1 ( λ ) = O ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) (27) F_{1,1}(\lambda)=O(|V(H)|+|E(H)|) \tag*{(27)} F 1 , 1 ( λ ) = O ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) (27)
We delay the proof of Lemma 5 to Section 5.1. Now we bound the ℓ 1 \ell_1 ℓ 1 -norm of w t w_t w t .
Lemma 6. In every round ∥ w t ∥ 1 ≤ 14 n \|w_t\|_1 \leq14n ∥ w t ∥ 1 ≤ 14 n .
Proof: We only need to tweak the proof of Lemma 4 slightly. Observe that:
⟨ w t , p t ⟩ ≤ D \langle w_t,p_t\rangle\leq D ⟨ w t , p t ⟩ ≤ D
And since w t [ v ] ≥ 1 + n deg ( v ) 2 m w_t[v] \geq1+\frac{n\operatorname{deg}(v)}{2m} w t [ v ] ≥ 1 + 2 m n deg ( v ) , the above inequality gives:
∥ p t ∥ 1 ≤ D \|p_t\|_1 \leq D ∥ p t ∥ 1 ≤ D
∑ v ∈ V n deg ( v ) p t [ v ] 2 m ≤ D \sum_{v\in V}\frac{n\operatorname{deg}(v)p_t[v]}{2m}\leq D v ∈ V ∑ 2 m n deg ( v ) p t [ v ] ≤ D
Since q t = ∑ i = 1 t − 1 p i q_t = \sum_{i=1}^{t-1} p_i q t = ∑ i = 1 t − 1 p i , it holds that:
∥ q t ∥ 1 ≤ ( t − 1 ) D ≤ T D ∑ v ∈ V n deg ( v ) q t [ v ] 2 m ≤ T D (28) \begin{aligned}
\lVert q_t\rVert_1 &\le(t-1)D \le TD \\
\sum_{v\in V} \frac{n\deg(v)q_t[v]}{2m} &\le TD \tag*{(28)}
\end{aligned} ∥ q t ∥ 1 v ∈ V ∑ 2 m n deg ( v ) q t [ v ] ≤ ( t − 1 ) D ≤ T D ≤ T D (28)
Now we observe by the definition of w t w_t w t that:
∥ w t ∥ 1 = n + n ∑ v deg ( v ) 2 m + 4 D ∥ q t ∥ 1 + 4 D ∑ v ∈ V ∑ u ∈ N G ( v ) q t [ u ] ≤ n + n + 4 D ∥ q t ∥ 1 + 4 D ∑ v ∈ V deg ( v ) q t [ v ] ≤ 2 n + 4 D ( T D ) + 4 D T D 2 m n (by Equation (28)) = 2 n + 4 T ( n / m T ) 2 + 4 T ( n / m T ) 2 2 m n ≤ 2 n + 4 n + 8 n = 14 n (29) \begin{aligned}
\lVert w_t\rVert_1 &= n+\frac{n\sum_{v}\deg(v)}{2m}+4D\lVert q_t\rVert_1+4D\sum_{v\in V}\sum_{u\in N_G(v)}q_t[u] \\
&\le n+n+4D\lVert q_t\rVert_1+4D\sum_{v\in V}\deg(v)q_t[v] \\
&\le2n+4D(TD)+4DTD\frac{2m}{n} \qquad\text{(by Equation (28))}\\
&=2n+4T(n/\sqrt{mT})^2+4T(n/\sqrt{mT})^2\frac{2m}{n}\\
&\le2n+4n+8n=14n \tag*{(29)}
\end{aligned} ∥ w t ∥ 1 = n + 2 m n ∑ v deg ( v ) + 4 D ∥ q t ∥ 1 + 4 D v ∈ V ∑ u ∈ N G ( v ) ∑ q t [ u ] ≤ n + n + 4 D ∥ q t ∥ 1 + 4 D v ∈ V ∑ deg ( v ) q t [ v ] ≤ 2 n + 4 D ( T D ) + 4 D T D n 2 m (by Equation (28)) = 2 n + 4 T ( n / m T ) 2 + 4 T ( n / m T ) 2 n 2 m ≤ 2 n + 4 n + 8 n = 14 n (29)
as claimed. □
Theorem 3. Let G G G be H H H -induced-minor-free with n n n vertices and m m m edges. There is a randomized algorithm that returns a 3 / 4 3/4 3/4 -balanced separator of size O ( log ∣ V ( H ) ∣ m ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) ) O(\log|V(H)|\sqrt{m}(|V(H)|+|E(H)|)) O ( log ∣ V ( H ) ∣ m ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ )) in expected O ( ∣ V ( H ) ∣ 7 ( m + n ) ) O(|V(H)|^7(m+n)) O ( ∣ V ( H ) ∣ 7 ( m + n )) time.
Proof. By Lemma 5 and Lemma 2, by choosing c c c sufficiently large, the FTRL algorithm (Algorithm 2) will terminate before T T T rounds. Therefore, CUTORCLUSTER(G , ∣ V ( H ) ∣ , ⌈ w t ⌉ , D G,|V(H)|,\lceil w_t\rceil,D G , ∣ V ( H ) ∣ , ⌈ w t ⌉ , D ) returns a separator S S S . Let W = ∑ v ∈ V ⌈ w t ⌉ [ v ] ≤ n + ∑ v ∈ V w t [ v ] W=\sum_{v\in V}\lceil w_t\rceil[v]\le n+\sum_{v\in V}w_t[v] W = ∑ v ∈ V ⌈ w t ⌉ [ v ] ≤ n + ∑ v ∈ V w t [ v ] . By Lemma 6, W ≤ 15 n W\le15n W ≤ 15 n . It is well known that if G G G excludes H H H as an induced minor, then G G G excludes K ∣ V ( H ) ∣ K_{|V(H)|} K ∣ V ( H ) ∣ as an induced minor. By Theorem 7, we have
∣ S ∣ = O ( W log ( h W / n ) D ) (30) |S|=O\left(\frac{W\log(hW/n)}{D}\right) \tag*{(30)} ∣ S ∣ = O ( D W log ( hW / n ) ) (30) = O ( 15 n log ( 15 ∣ V ( H ) ∣ ) m T / n ) =O\left(15n\log(15|V(H)|)\sqrt{mT}/n\right) = O ( 15 n log ( 15∣ V ( H ) ∣ ) m T / n ) = O ( log ∣ V ( H ) ∣ m ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) ) (since T = O ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) ) =O\left(\log\lvert V(H)\rvert\sqrt{m}\left(\lvert V(H)\rvert+\lvert E(H)\rvert\right)\right)\qquad\text{(since }T=O\left(\lvert V(H)\rvert+\lvert E(H)\rvert\right)\text{)} = O ( log ∣ V ( H )∣ m ( ∣ V ( H )∣ + ∣ E ( H )∣ ) ) (since T = O ( ∣ V ( H )∣ + ∣ E ( H )∣ ) ) as claimed. For the running time, we note that the vertex weights are integers of total weight at most W ≤ 15 n W\le15n W ≤ 15 n . Thus, a single-source shortest path tree can be computed in time O ( n + m + W ) = O ( n + m ) O(n+m+W)=O(n+m) O ( n + m + W ) = O ( n + m ) by Dial’s algorithm (Theorem 5) and hence by Theorem 7, the total expected running time is O ( T ⋅ ∣ V ( H ) ∣ 5 ( m + n ) ) = O ( ∣ V ( H ) ∣ 7 ( m + n ) ) O(T\cdot|V(H)|^5(m+n))=O(|V(H)|^7(m+n)) O ( T ⋅ ∣ V ( H ) ∣ 5 ( m + n )) = O ( ∣ V ( H ) ∣ 7 ( m + n )) . □
Proof of lm:opt-bound-indminor
Similarly to the proof of Lemma 3, we will make use of a known collision probability bound. In this case, the bound follows directly from an argument of Korhonen and Lokshtanov, rather than a later variant of their construction [16 ] .
Proposition 1 (adapted from [16 proofs of Lemmas 4.2–4.4] ). Let H H H be a nonempty graph and G G G an H H H -induced-minor-free graph. Sample u , v u,v u , v independently from a probability distribution π \pi π on V ( G ) V(G) V ( G ) , then sample a simple u u u –v v v path P P P from any fixed distribution for that ordered pair. If u = v u=v u = v , take P = { u } P=\{u\} P = { u } . For an independent copy P ′ P' P ′ , we have
Pr [ P and P ′ share a vertex or are joined by an edge ] ≥ c 1 ∣ V ( H ) ∣ + ∣ E ( H ) ∣ , \Pr[P\text{ and }P'\text{ share a vertex or are joined by an edge}]\ge\frac{c_1}{|V(H)|+|E(H)|}, Pr [ P and P ′ share a vertex or are joined by an edge ] ≥ ∣ V ( H ) ∣ + ∣ E ( H ) ∣ c 1 , where c 1 > 0 c_1>0 c 1 > 0 is an absolute constant.
Proof: The random-path argument in [16 proofs of Lemmas 4.2–4.4] produces an induced minor model of H H H if
Pr [ P and P ′ share a vertex or are joined by an edge ] ≤ c 1 ∣ V ( H ) ∣ + ∣ E ( H ) ∣ . \Pr[P \text{ and } P' \text{ share a vertex or are joined by an edge}] \le\frac{c_1}{|V(H)|+|E(H)|}. Pr [ P and P ′ share a vertex or are joined by an edge ] ≤ ∣ V ( H ) ∣ + ∣ E ( H ) ∣ c 1 .
for some absolute constant c 1 > 0 c_1 > 0 c 1 > 0 . Once this probability bound is given, their local-lemma argument only needs independent vertex images and independent conditional path choices, so it applies to the endpoint distribution π \pi π . Since G G G is H H H -induced-minor-free, it follows that
Pr [ P and P ′ share a vertex or are joined by an edge ] > c 1 ∣ V ( H ) ∣ + ∣ E ( H ) ∣ . \Pr[P \text{ and } P' \text{ share a vertex or are joined by an edge}] > \frac{c_1}{|V(H)|+|E(H)|}. Pr [ P and P ′ share a vertex or are joined by an edge ] > ∣ V ( H ) ∣ + ∣ E ( H ) ∣ c 1 .
Proof of Lemma 5. The proof will be similar to that of Lemma 3. The case λ = 0 \lambda= 0 λ = 0 is immediate, so assume λ ≠ 0 \lambda\ne0 λ = 0 . Construct P , P ′ P,P' P , P ′ and their root paths Q 1 , Q 2 , Q 1 ′ , Q 2 ′ Q_1,Q_2,Q'_1,Q'_2 Q 1 , Q 2 , Q 1 ′ , Q 2 ′ exactly as in the proof of Lemma 3. The terminal-counting argument in that proof gives, for i , j ∈ { 1 , 2 } i,j \in\{1,2\} i , j ∈ { 1 , 2 } and every vertex v v v ,
Pr [ v ∈ V ( Q i ) ∣ C 1 , C 2 ] ≤ 3 2 p C i [ v ] , Pr [ v ∈ V ( Q j ′ ) ∣ C 1 ′ , C 2 ′ ] ≤ 3 2 p C j ′ [ v ] . \Pr[v \in V(Q_i) \mid C_1,C_2] \le\frac{3}{2}p_{C_i}[v], \qquad\Pr[v \in V(Q'_j) \mid C'_1,C'_2] \le\frac{3}{2}p_{C'_j}[v]. Pr [ v ∈ V ( Q i ) ∣ C 1 , C 2 ] ≤ 2 3 p C i [ v ] , Pr [ v ∈ V ( Q j ′ ) ∣ C 1 ′ , C 2 ′ ] ≤ 2 3 p C j ′ [ v ] .
Fix i , j ∈ { 1 , 2 } i,j \in\{1,2\} i , j ∈ { 1 , 2 } and condition on all four connectors. The unprimed and primed terminal choices remain independent. For any vertices u , v u,v u , v , it follows that
Pr [ u ∈ V ( Q i ) , v ∈ V ( Q j ′ ) ∣ C 1 , C 2 , C 1 ′ , C 2 ′ ] = Pr [ u ∈ V ( Q i ) ∣ C 1 , C 2 ] Pr [ v ∈ V ( Q j ′ ) ∣ C 1 ′ , C 2 ′ ] ≤ 9 4 p C i [ u ] p C j ′ [ v ] . \begin{aligned}
\Pr[u \in V(Q_i),\,v \in V(Q'_j) \mid C_1,C_2,C'_1,C'_2]
&= \Pr[u \in V(Q_i) \mid C_1,C_2]\Pr[v \in V(Q'_j) \mid C'_1,C'_2] \\
&\le\frac{9}{4}p_{C_i}[u]p_{C'_j}[v].
\end{aligned} Pr [ u ∈ V ( Q i ) , v ∈ V ( Q j ′ ) ∣ C 1 , C 2 , C 1 ′ , C 2 ′ ] = Pr [ u ∈ V ( Q i ) ∣ C 1 , C 2 ] Pr [ v ∈ V ( Q j ′ ) ∣ C 1 ′ , C 2 ′ ] ≤ 4 9 p C i [ u ] p C j ′ [ v ] .
If C i ≠ C j ′ C_i \ne C'_j C i = C j ′ , a union bound over shared vertices and both orientations of each joining edge therefore bounds the conditional probability that Q i , Q j ′ Q_i,Q'_j Q i , Q j ′ share a vertex or are joined by an edge by
9 4 ( ∑ v p C i [ v ] p C j ′ [ v ] + ∑ u v ∈ E ( G ) ( p C i [ u ] p C j ′ [ v ] + p C i [ v ] p C j ′ [ u ] ) ) = 9 4 H 1 , 1 ( p C i , p C j ′ ) , \frac{9}{4}\left(\sum_v p_{C_i}[v]p_{C'_j}[v]+\sum_{uv\in E(G)}\left(p_{C_i}[u]p_{C'_j}[v]+p_{C_i}[v]p_{C'_j}[u]\right)\right)=\frac{9}{4}H_{1,1}(p_{C_i},p_{C'_j}), 4 9 v ∑ p C i [ v ] p C j ′ [ v ] + uv ∈ E ( G ) ∑ ( p C i [ u ] p C j ′ [ v ] + p C i [ v ] p C j ′ [ u ] ) = 4 9 H 1 , 1 ( p C i , p C j ′ ) ,
where the equality is the definition of H 1 , 1 H_{1,1} H 1 , 1 in Eq. (12) . If C i = C j ′ C_i=C'_j C i = C j ′ , both paths contain the same root, so the conditional probability is 1. Averaging over all four connector choices gives
Pr [ Q i and Q j ′ share a vertex or are joined by an edge ] ≤ ∑ C λ [ C ] 2 ∥ λ ∥ 1 2 + 9 4 ∑ C ≠ D λ [ C ] λ [ D ] ∥ λ ∥ 1 2 H 1 , 1 ( p C , p D ) . \Pr[Q_i \text{ and } Q'_j \text{ share a vertex or are joined by an edge}]
\le\sum_C \frac{\lambda[C]^2}{\|\lambda\|_1^2}+\frac{9}{4}\sum_{C\ne D}\frac{\lambda[C]\lambda[D]}{\|\lambda\|_1^2}H_{1,1}(p_C,p_D). Pr [ Q i and Q j ′ share a vertex or are joined by an edge ] ≤ C ∑ ∥ λ ∥ 1 2 λ [ C ] 2 + 4 9 C = D ∑ ∥ λ ∥ 1 2 λ [ C ] λ [ D ] H 1 , 1 ( p C , p D ) .
Erasing cycles only removes vertices, so any shared vertex or joining edge between P , P ′ P,P' P , P ′ also occurs for at least one of the four pairs ( Q i , Q j ′ ) (Q_i,Q'_j) ( Q i , Q j ′ ) . A union bound over these pairs yields
Pr [ P and P ′ share a vertex or are joined by an edge ] ≤ 4 ∑ C λ [ C ] 2 + 9 ∑ C ≠ D λ [ C ] λ [ D ] H 1 , 1 ( p C , p D ) ∥ λ ∥ 1 2 . \Pr[P \text{ and } P' \text{ share a vertex or are joined by an edge}]
\le\frac{4\sum_C\lambda[C]^2+9\sum_{C\ne D}\lambda[C]\lambda[D]H_{1,1}(p_C,p_D)}{\|\lambda\|_1^2}. Pr [ P and P ′ share a vertex or are joined by an edge ] ≤ ∥ λ ∥ 1 2 4 ∑ C λ [ C ] 2 + 9 ∑ C = D λ [ C ] λ [ D ] H 1 , 1 ( p C , p D ) .
The endpoints of P P P are r C 1 , r C 2 r_{C_1},r_{C_2} r C 1 , r C 2 , independently sampled from
π ( v ) = ∑ C : r C = v λ [ C ] ∥ λ ∥ 1 . \pi(v)=\sum_{C:r_C=v}\frac{\lambda[C]}{\|\lambda\|_1}. π ( v ) = C : r C = v ∑ ∥ λ ∥ 1 λ [ C ] .
We apply Proposition 1 to P , P ′ P,P' P , P ′ and get the corresponding lower bound c 1 / ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) c_1/(|V(H)|+|E(H)|) c 1 / ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) . Using Eq. (11) and λ [ C ] 2 ≤ λ [ C ] \lambda[C]^2\le\lambda[C] λ [ C ] 2 ≤ λ [ C ] , we obtain
c 1 ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ≤ 4 ∑ C λ [ C ] 2 + 18 ( ∥ λ ∥ 1 − F 1 , 1 ( λ ) ) ∥ λ ∥ 1 2 ≤ 22 ∥ λ ∥ 1 − 18 F 1 , 1 ( λ ) ∥ λ ∥ 1 2 . \frac{c_1}{|V(H)|+|E(H)|}\le\frac{4\sum_C\lambda[C]^2+18(\|\lambda\|_1-F_{1,1}(\lambda))}{\|\lambda\|_1^2}\le\frac{22\|\lambda\|_1-18F_{1,1}(\lambda)}{\|\lambda\|_1^2}. ∣ V ( H ) ∣ + ∣ E ( H ) ∣ c 1 ≤ ∥ λ ∥ 1 2 4 ∑ C λ [ C ] 2 + 18 ( ∥ λ ∥ 1 − F 1 , 1 ( λ )) ≤ ∥ λ ∥ 1 2 22∥ λ ∥ 1 − 18 F 1 , 1 ( λ ) .
Rearranging gives
F 1 , 1 ( λ ) ≤ 11 9 ∥ λ ∥ 1 − c 1 ∥ λ ∥ 1 2 18 ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) . F_{1,1}(\lambda) \le\frac{11}{9}\lVert\lambda\rVert_1-\frac{c_1\lVert\lambda\rVert_1^2}{18(|V(H)|+|E(H)|)}. F 1 , 1 ( λ ) ≤ 9 11 ∥ λ ∥ 1 − 18 ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) c 1 ∥ λ ∥ 1 2 .
The right-hand side is a concave quadratic in ∥ λ ∥ 1 \lVert\lambda\rVert_1 ∥ λ ∥ 1 , maximized at
∥ λ ∥ 1 = 11 ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) c 1 . \lVert\lambda\rVert_1=\frac{11(|V(H)|+|E(H)|)}{c_1}. ∥ λ ∥ 1 = c 1 11 ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) .
Substituting this value gives
F 1 , 1 ( λ ) ≤ 121 18 c 1 ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) = O ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) . F_{1,1}(\lambda)\le\frac{121}{18c_1}(|V(H)|+|E(H)|)=O(|V(H)|+|E(H)|). F 1 , 1 ( λ ) ≤ 18 c 1 121 ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) = O ( ∣ V ( H ) ∣ + ∣ E ( H ) ∣ ) .
Computing a Cluster or a Balanced Separator
In this section, we prove Theorem 7, restated below.
Theorem 7. Let h ≥ 2 h\ge2 h ≥ 2 , and let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph with n n n vertices and m m m edges that excludes K h ( 1 ) K_h^{(1)} K h ( 1 ) as an induced minor. Let w : V → Z ≥ 1 w:V\to\mathbb{Z}_{\ge1} w : V → Z ≥ 1 be vertex weights, W : = ∑ v ∈ V w ( v ) W:=\sum_{v\in V}w(v) W := ∑ v ∈ V w ( v ) , and 0 < D ≤ n 0<D\le n 0 < D ≤ n . There is a randomized algorithm CutOrCluster( G , h , w , D ) (G,h,w,D) ( G , h , w , D ) that returns one of the following:
a cluster : a set K ⊆ V K\subseteq V K ⊆ V with ∣ K ∣ > 3 n / 4 |K|>3n/4 ∣ K ∣ > 3 n /4 such that G [ K ] G[K] G [ K ] has vertex-weight diameter at most D D D : every two vertices of K K K are joined by a path P P P in G [ K ] G[K] G [ K ] with w ( P ) ≤ D w(P)\le D w ( P ) ≤ D , or
a balanced separator : a set S ⊆ V S\subseteq V S ⊆ V with ∣ S ∣ = O ( W log ( h W / n ) / D ) |S|=O(W\log(hW/n)/D) ∣ S ∣ = O ( W log ( hW / n ) / D ) such that every connected component of G − S G-S G − S has at most 3 n / 4 3n/4 3 n /4 vertices.
Its expected running time is O ( h 5 ( TSSSP ( n + 1 , m + n , 2 W ) + m + n ) ) O(h^5(\operatorname{TSSSP}(n+1,m+n,2W)+m+n)) O ( h 5 ( TSSSP ( n + 1 , m + n , 2 W ) + m + n )) , where TSSSP ( N , M , L ) \operatorname{TSSSP}(N,M,L) TSSSP ( N , M , L ) is the time to compute a shortest-path tree from a single source in a graph with at most N N N vertices, at most M M M edges, and integer edge lengths with maximum distance at most L L L .
For X ⊆ V X\subseteq V X ⊆ V , let w ( X ) : = ∑ v ∈ X w ( v ) w(X):=\sum_{v\in X}w(v) w ( X ) := ∑ v ∈ X w ( v ) . Following [11 ] , the vertex weight function w w w induces an edge length function ℓ : E → R ≥ 0 \ell:E\to\mathbb{R}_{\ge0} ℓ : E → R ≥ 0 where for each edge e = ( u , v ) e=(u,v) e = ( u , v ) , we set ℓ ( e ) = w ( u ) + w ( v ) 2 \ell(e)=\frac{w(u)+w(v)}{2} ℓ ( e ) = 2 w ( u ) + w ( v ) . The graph distance (for vertex-weighted graphs) in this section is the distance w.r.t. the length function ℓ \ell ℓ , unless explicitly noted otherwise. Thus, a path P P P from u u u to v v v has length ℓ ( P ) = w ( P ) − ( w ( u ) + w ( v ) ) / 2 \ell(P)=w(P)-(w(u)+w(v))/2 ℓ ( P ) = w ( P ) − ( w ( u ) + w ( v )) /2 . For a vertex-weighted subgraph H H H of G G G , X ⊆ V ( H ) X\subseteq V(H) X ⊆ V ( H ) and r ≥ 0 r\ge0 r ≥ 0 , let B H ( X , r ) : = { v ∈ V ( H ) : d H ( X , v ) ≤ r } B_H(X,r):=\{v\in V(H):d_H(X,v)\le r\} B H ( X , r ) := { v ∈ V ( H ) : d H ( X , v ) ≤ r } .
We will need two results for this theorem. The first result is the following lemma, which is an efficient implementation of [11 Theorem 3.4] , whose proof will be delayed to Section 6.1.
Lemma 7. Let h ≥ 2 h\ge2 h ≥ 2 , and let G G G be a connected K h ( 1 ) K_h^{(1)} K h ( 1 ) -induced-minor-free graph with n n n vertices, m m m edges and edge lengths in ( 0 , 1 ] (0,1] ( 0 , 1 ] . Distances are w.r.t. these edge lengths. Let b : = n / ( 8 h 2 ) b:=n/(8h^2) b := n / ( 8 h 2 ) . There is a randomized algorithm, denoted by BallOrPair( G , h ) (G,h) ( G , h ) , that returns one of the following:
a vertex x x x with ∣ B G ( x , 11 ) ∣ > b |B_G(x,11)|>b ∣ B G ( x , 11 ) ∣ > b ,
a pair ( A , B ) (A,B) ( A , B ) of vertex-disjoint subsets of vertices, each of size at least b b b and d G ( A , B ) > 1 d_G(A,B)>1 d G ( A , B ) > 1 .
It makes O ( h 3 ) O(h^3) O ( h 3 ) shortest-path computations (from sets of sources) and an additional O ( h 3 ( m + n ) ) O(h^3(m+n)) O ( h 3 ( m + n )) time, in expectation.
Intuitively, Lemma 7 says that either we get a low-diameter cluster containing many vertices, or we have two large sets A A A and B B B that are sufficiently far apart. In the former case, we get a cluster as stated in Theorem 7. In the latter case, we do not immediately get the separator. W.l.o.g., we assume that ∣ B G ( A , 1 / 2 ) ∣ ≤ ∣ B G ( B , 1 / 2 ) ∣ |B_G(A,1/2)|\le|B_G(B,1/2)| ∣ B G ( A , 1/2 ) ∣ ≤ ∣ B G ( B , 1/2 ) ∣ and we call A A A the smaller side of the pair ( A , B ) (A,B) ( A , B ) . Then we need one more step: grow the smaller side to find a larger subset R ⊇ A R\supseteq A R ⊇ A whose boundary, denoted by ∂ R \partial R ∂ R , is small. Here ∂ R \partial R ∂ R contains all the vertices in R R R that have at least one neighbor outside R R R . The following lemma formalizes this step and follows from a simple region-growing argument of Leighton and Rao [23 ] .
Lemma 8. Let δ ≥ 1 \delta\ge1 δ ≥ 1 be a parameter and let G = ( V , E ) G = (V,E) G = ( V , E ) be a vertex-weighted graph with n n n vertices, m m m edges and integer vertex weights w ( v ) ∈ [ 1 , δ ] w(v) \in[1,\delta] w ( v ) ∈ [ 1 , δ ] . Let X ⊆ V X \subseteq V X ⊆ V be nonempty. There is a set R R R with X ⊆ R ⊆ B G ( X , 2 δ ) X \subseteq R \subseteq B_G(X,2\delta) X ⊆ R ⊆ B G ( X , 2 δ ) such that ∣ ∂ R ∣ ≤ 1 δ ln w ( V ) w ( X ) ⋅ w ( R ) |\partial R| \le\frac{1}{\delta}\ln\frac{w(V)}{w(X)} \cdot w(R) ∣ ∂ R ∣ ≤ δ 1 ln w ( X ) w ( V ) ⋅ w ( R ) . Furthermore, if { d G ( X , v ) } v ∈ V \{d_G(X,v)\}_{v\in V} { d G ( X , v ) } v ∈ V is given, then R R R can be found in O ( m + n + δ ) O(m+n+\delta) O ( m + n + δ ) time, and in this case we denote the algorithm by GROW ( G , X , δ , { d G ( X , v ) } v ∈ V ) \operatorname{GROW}(G,X,\delta,\{d_G(X,v)\}_{v\in V}) GROW ( G , X , δ , { d G ( X , v ) } v ∈ V ) .
Proof. For each vertex v v v , represent it by an interval I v = [ d G ( X , v ) − w ( v ) / 2 , d G ( X , v ) + w ( v ) / 2 ] I_v = [d_G(X,v)-w(v)/2,d_G(X,v)+w(v)/2] I v = [ d G ( X , v ) − w ( v ) /2 , d G ( X , v ) + w ( v ) /2 ] , which is centered at d G ( X , v ) d_G(X,v) d G ( X , v ) and has width w ( v ) w(v) w ( v ) . Then for any edge e = ( u , v ) e=(u,v) e = ( u , v ) , I v ∩ I u ≠ ∅ I_v\cap I_u\ne\varnothing I v ∩ I u = ∅ since ℓ ( e ) = w ( u ) + w ( v ) 2 \ell(e)=\frac{w(u)+w(v)}{2} ℓ ( e ) = 2 w ( u ) + w ( v ) . Let r ∈ [ δ / 2 , 3 δ / 2 ] r\in[\delta/2,3\delta/2] r ∈ [ δ /2 , 3 δ /2 ] be a parameter. Let Λ ( r ) \Lambda(r) Λ ( r ) be the total length of the parts of the intervals to the left of r r r ; see Figure 1 . Formally:
Figure 1. Illustrating the region growing algorithm in the proof of Lemma 8 , with X = { x } X = \{x\} X = { x } , δ = 4 \delta= 4 δ = 4 and r = 4 r = 4 r = 4 . (a) Each vertex v v v is a disc of diameter proportional to w ( v ) w(v) w ( v ) ; the boundary vertices of R r R_r R r have a thick orange outline. (b) The intervals I v I_v I v ; the filled parts sum to Λ ( r ) \Lambda(r) Λ ( r ) .
Λ ( r ) = ∑ v ∈ V max { min { r , d G ( X , v ) + w ( v ) 2 } − ( d G ( X , v ) − w ( v ) 2 ) , 0 } (31) \Lambda(r)=\sum_{v\in V}\max\left\{\min\left\{r,d_G(X,v)+\frac{w(v)}{2}\right\}-\left(d_G(X,v)-\frac{w(v)}{2}\right),0\right\} \tag*{(31)} Λ ( r ) = v ∈ V ∑ max { min { r , d G ( X , v ) + 2 w ( v ) } − ( d G ( X , v ) − 2 w ( v ) ) , 0 } (31)
Let R r R_r R r be the set of vertices whose intervals start before r r r . We observe that:
Λ ′ ( r ) \Lambda'(r) Λ ′ ( r ) is the number of intervals containing r r r when r r r is not the endpoint of an interval. (And there are only finitely many such points, whose total measure is 0 in [ δ / 2 , 3 δ / 2 ] [\delta/2,3\delta/2] [ δ /2 , 3 δ /2 ] .)
Every vertex u ∈ R r u\in R_r u ∈ R r such that I u I_u I u ends before r r r only has neighbors inside R r R_r R r . Thus, every u ∈ ∂ R r u\in\partial R_r u ∈ ∂ R r must have r ∈ I u r\in I_u r ∈ I u , which implies ∣ ∂ R r ∣ ≤ Λ ′ ( r ) |\partial R_r|\le\Lambda'(r) ∣ ∂ R r ∣ ≤ Λ ′ ( r ) .
Λ ( r ) ≤ w ( R r ) \Lambda(r)\le w(R_r) Λ ( r ) ≤ w ( R r ) .
Finally, we observe that:
∫ δ / 2 3 δ / 2 Λ ′ ( r ) Λ ( r ) d r = ln ( Λ ( 3 δ / 2 ) ) − ln ( Λ ( δ / 2 ) ) ≤ ln ( w ( V ) ) − ln ( w ( X ) ) = ln w ( V ) w ( X ) . \int_{\delta/2}^{3\delta/2}\frac{\Lambda'(r)}{\Lambda(r)}\,dr=\ln(\Lambda(3\delta/2))-\ln(\Lambda(\delta/2))\le\ln(w(V))-\ln(w(X))=\ln\frac{w(V)}{w(X)}. ∫ δ /2 3 δ /2 Λ ( r ) Λ ′ ( r ) d r = ln ( Λ ( 3 δ /2 )) − ln ( Λ ( δ /2 )) ≤ ln ( w ( V )) − ln ( w ( X )) = ln w ( X ) w ( V ) .
Thus, there exists r ∈ [ δ / 2 , 3 δ / 2 ] r\in[\delta/2,3\delta/2] r ∈ [ δ /2 , 3 δ /2 ] such that Λ ′ ( r ) ≤ Λ ( r ) 1 δ ln w ( V ) w ( X ) \Lambda'(r)\le\Lambda(r)\frac{1}{\delta}\ln\frac{w(V)}{w(X)} Λ ′ ( r ) ≤ Λ ( r ) δ 1 ln w ( X ) w ( V ) , giving:
∣ ∂ R r ∣ ≤ Λ ′ ( r ) ≤ Λ ( r ) 1 δ ln w ( V ) w ( X ) ≤ 1 δ ln w ( V ) w ( X ) w ( R r ) (32) |\partial R_r|\le\Lambda'(r)\le\Lambda(r)\frac{1}{\delta}\ln\frac{w(V)}{w(X)}\le\frac{1}{\delta}\ln\frac{w(V)}{w(X)}w(R_r) \tag*{(32)} ∣ ∂ R r ∣ ≤ Λ ′ ( r ) ≤ Λ ( r ) δ 1 ln w ( X ) w ( V ) ≤ δ 1 ln w ( X ) w ( V ) w ( R r ) (32)
as claimed. To find such r r r , we simply sweep over endpoints in [ δ / 2 , 3 δ / 2 ] [\delta/2,3\delta/2] [ δ /2 , 3 δ /2 ] sorted in increasing order, using bucket sort. The running time is O ( n + m + δ ) O(n+m+\delta) O ( n + m + δ ) . □
Algorithm 3 CUTORCLUSTER(G , h , w , D G,h,w,D G , h , w , D )
1: δ : = D / 25 \delta:= D/25 δ := D /25 2: S ← { v ∈ V : w ( v ) > δ / 4 } S \leftarrow\{v \in V : w(v) > \delta/4\} S ← { v ∈ V : w ( v ) > δ /4 } 3: H ← H \leftarrow H ← largest connected component of G ∖ S G \setminus S G ∖ S 4: while ∣ V ( H ) ∣ > 3 n / 4 |V(H)| > 3n/4 ∣ V ( H ) ∣ > 3 n /4 do 5: ( x , A , B ) ← (x,A,B) \leftarrow ( x , A , B ) ← BALLORPAIR(H , h H,h H , h ) with edge lengths divided by δ \delta δ . ▷ if x = NULL x = \text{NULL} x = NULL , then A A A is the smaller side 6: if x ≠ NULL x \ne\text{NULL} x = NULL then 7: if ∣ B H ( x , 12 δ ) ∣ > 3 n / 4 |B_H(x,12\delta)| > 3n/4 ∣ B H ( x , 12 δ ) ∣ > 3 n /4 then 8: return B H ( x , 12 δ ) B_H(x,12\delta) B H ( x , 12 δ ) ▷ return a cluster 9: X ← B H ( x , 11 δ ) X \leftarrow B_H(x,11\delta) X ← B H ( x , 11 δ ) 10: else ▷ it returns two sets 11: X ← A X \leftarrow A X ← A ▷ ∣ B H ( A , δ / 2 ) ∣ ≤ ∣ B H ( B , δ / 2 ) ∣ |B_H(A,\delta/2)| \le|B_H(B,\delta/2)| ∣ B H ( A , δ /2 ) ∣ ≤ ∣ B H ( B , δ /2 ) ∣ and d H ( A , B ) > δ d_H(A,B) > \delta d H ( A , B ) > δ 12: compute { d H ( X , v ) } v ∈ V \{d_H(X,v)\}_{v\in V} { d H ( X , v ) } v ∈ V 13: R ← R \leftarrow R ← GROW(H , X , δ / 4 , { d H ( X , v ) } v ∈ V H,X,\delta/4,\{d_H(X,v)\}_{v\in V} H , X , δ /4 , { d H ( X , v ) } v ∈ V ) ▷ apply the algorithm in Lemma 8 14: S ← S ∪ ∂ H ( R ) S \leftarrow S \cup\partial_H(R) S ← S ∪ ∂ H ( R ) 15: H ← H \leftarrow H ← largest connected component of H ∖ ∂ H ( R ) H \setminus\partial_H(R) H ∖ ∂ H ( R ) ▷ also is the largest connected component of G ∖ S G \setminus S G ∖ S 16: return S S S ▷ return a cut
Now we are ready to prove Theorem 7. We write ∂ H R \partial_H R ∂ H R to denote the boundary of R R R in a graph H H H .
Proof of Theorem 7. Algorithm 3 implements CUTORCLUSTER(G , h , w , D G,h,w,D G , h , w , D ). We now describe the intuition of the algorithm. Let δ = D / 25 \delta= D/25 δ = D /25 . First, we include all vertices of weight at least δ / 4 \delta/4 δ /4 in a set S S S , our intended balanced separator. This ensures that all edges have length at most δ / 4 \delta/4 δ /4 . The algorithm is iterative, starting from the largest connected component H H H of G ∖ S G \setminus S G ∖ S . If at any point of the algorithm H H H contains at most 3 n / 4 3n/4 3 n /4 vertices, then we know that S S S is balanced.
In each iteration, we apply BALLORPAIR(H , h H,h H , h ) (in Lemma 7) with edge lengths divided by δ \delta δ , so that every edge has length in ( 0 , 1 ] (0,1] ( 0 , 1 ] . By Lemma 7, we either get:
a vertex x x x such that (in the unscaled edge lengths), B H ( x , 11 δ ) B_H(x,11\delta) B H ( x , 11 δ ) contains more than ∣ V ( H ) ∣ / ( 8 h 2 ) |V(H)|/(8h^2) ∣ V ( H ) ∣/ ( 8 h 2 ) vertices. Then we check if B H ( x , 12 δ ) B_H(x,12\delta) B H ( x , 12 δ ) contains more than 3 n / 4 3n/4 3 n /4 vertices, then we return B H ( x , 12 δ ) B_H(x,12\delta) B H ( x , 12 δ ) , which is a cluster satisfying item 1 of Theorem 7 since the diameter of G [ B H ( x , 12 δ ) ] G[B_H(x,12\delta)] G [ B H ( x , 12 δ )] is at most 2 ( 12 δ ) + 2 ( δ / 4 ) < 25 δ = D 2(12\delta)+2(\delta/4)<25\delta=D 2 ( 12 δ ) + 2 ( δ /4 ) < 25 δ = D . Otherwise, we have found a set X = B H ( x , 11 δ ) X=B_H(x,11\delta) X = B H ( x , 11 δ ) ; we clarify the role of X X X below. We note that:
∣ B H ( X , δ / 2 ) ∣ ≤ ∣ B H ( x , 12 δ ) ∣ ≤ 3 n / 4 (33) |B_H(X,\delta/2)| \le|B_H(x,12\delta)| \le3n/4 \tag*{(33)} ∣ B H ( X , δ /2 ) ∣ ≤ ∣ B H ( x , 12 δ ) ∣ ≤ 3 n /4 (33)
a pair ( A , B ) (A,B) ( A , B ) where A A A is the smaller side, i.e., ∣ B H ( A , δ / 2 ) ∣ ≤ ∣ B H ( B , δ / 2 ) ∣ |B_H(A,\delta/2)| \le|B_H(B,\delta/2)| ∣ B H ( A , δ /2 ) ∣ ≤ ∣ B H ( B , δ /2 ) ∣ . In this case, we take X = A X=A X = A . Since d H ( A , B ) > δ d_H(A,B)>\delta d H ( A , B ) > δ , the sets B H ( A , δ / 2 ) B_H(A,\delta/2) B H ( A , δ /2 ) and B H ( B , δ / 2 ) B_H(B,\delta/2) B H ( B , δ /2 ) are disjoint, and since A A A is the smaller side, ∣ B H ( X , δ / 2 ) ∣ = ∣ B H ( A , δ / 2 ) ∣ ≤ ∣ V ( H ) ∣ / 2 |B_H(X,\delta/2)|=|B_H(A,\delta/2)|\le|V(H)|/2 ∣ B H ( X , δ /2 ) ∣ = ∣ B H ( A , δ /2 ) ∣ ≤ ∣ V ( H ) ∣/2 .
In both cases, X X X has the following properties: (i) X X X contains at least ∣ V ( H ) ∣ / ( 8 h 2 ) |V(H)|/(8h^2) ∣ V ( H ) ∣/ ( 8 h 2 ) vertices, and (ii) ∣ B H ( X , δ / 2 ) ∣ ≤ 3 n / 4 |B_H(X,\delta/2)|\le3n/4 ∣ B H ( X , δ /2 ) ∣ ≤ 3 n /4 . This means if we grow X X X by a radius at most δ / 2 \delta/2 δ /2 to get a set R ⊆ B H ( X , δ / 2 ) R\subseteq B_H(X,\delta/2) R ⊆ B H ( X , δ /2 ) by applying Lemma 8 with parameter δ / 4 \delta/4 δ /4 (line 13 in Algorithm 3), it is guaranteed that if the largest connected component C C C of H ∖ ∂ H ( R ) H\setminus\partial_H(R) H ∖ ∂ H ( R ) has size more than 3 n / 4 3n/4 3 n /4 , then C ⊆ B H ( X , δ / 2 ) C\subseteq B_H(X,\delta/2) C ⊆ B H ( X , δ /2 ) . Thus, by adding ∂ H ( R ) \partial_H(R) ∂ H ( R ) to S S S , in the next iteration we continue with the (largest) connected component of H ∖ ∂ H ( R ) H\setminus\partial_H(R) H ∖ ∂ H ( R ) that is disjoint from R R R . Since w ( X ) ≥ ∣ X ∣ ≥ ∣ V ( H ) ∣ / ( 8 h 2 ) > 3 n / ( 32 h 2 ) w(X)\ge|X|\ge|V(H)|/(8h^2)>3n/(32h^2) w ( X ) ≥ ∣ X ∣ ≥ ∣ V ( H ) ∣/ ( 8 h 2 ) > 3 n / ( 32 h 2 ) , by Lemma 8 , each step we add to S S S at most:
4 δ ln w 3 n / ( 32 h 2 ) w ( R ) = 4 w ( R ) δ ln 32 h 2 w 3 n . (34) \frac{4}{\delta}\ln\frac{w}{3n/(32h^2)}w(R)=\frac{4w(R)}{\delta}\ln\frac{32h^2w}{3n}. \tag*{(34)} δ 4 ln 3 n / ( 32 h 2 ) w w ( R ) = δ 4 w ( R ) ln 3 n 32 h 2 w . (34)
Over the course of the algorithm, the total number of vertices added to S S S in line 14 is:
∑ R 4 w ( R ) δ ln 32 h 2 W 3 n ≤ 4 W δ ln 32 h 2 W 3 n (35) \sum_R \frac{4w(R)}{\delta}\ln\frac{32h^2W}{3n}\le\frac{4W}{\delta}\ln\frac{32h^2W}{3n} \tag*{(35)} R ∑ δ 4 w ( R ) ln 3 n 32 h 2 W ≤ δ 4 W ln 3 n 32 h 2 W (35)
Since in line 2, we add at most 4 W / δ 4W/\delta 4 W / δ vertices to S S S , the total size of S S S is:
∣ S ∣ ≤ 4 W δ + 4 W δ ln 32 h 2 W 3 n = O ( W log ( h W / n ) / D ) . |S| \le\frac{4W}{\delta}+\frac{4W}{\delta}\ln\frac{32h^{2}W}{3n}=O(W\log(hW/n)/D). ∣ S ∣ ≤ δ 4 W + δ 4 W ln 3 n 32 h 2 W = O ( W log ( hW / n ) / D ) .
Now we bound the running time of each iteration. By Lemma 7, each BALLORPAIR( H , h ) (H,h) ( H , h ) requires O ( h 3 ) O(h^{3}) O ( h 3 ) shortest path computations in expectation. Note that in Algorithm 3, we scale edge lengths by δ \delta δ to match the statement of Lemma 7, but we will run the single-source shortest path on unscaled lengths. Also note that since each edge e = ( u , v ) e=(u,v) e = ( u , v ) has length ℓ ( e ) = w ( u ) + w ( v ) 2 \ell(e)=\frac{w(u)+w(v)}{2} ℓ ( e ) = 2 w ( u ) + w ( v ) , which could be fractional, by scaling the edge length by a factor of 2, all the edge lengths are integers. Since the total vertex weight is at most W W W , the maximum distance is at most 2 W 2W 2 W . Hence, the total running time of this procedure is O ( h 3 ( T S S S P ( n + 1 , m + n , 2 W ) + m + n ) ) O(h^{3}(T_{\mathrm{SSSP}}(n+1,m+n,2W)+m+n)) O ( h 3 ( T SSSP ( n + 1 , m + n , 2 W ) + m + n )) .
To compute { d H ( X , v ) } v ∈ V \{d_H(X,v)\}_{v\in V} { d H ( X , v ) } v ∈ V , we can reduce to single-source shortest path by adding a dummy vertex x x x and connecting x x x to every vertex in X X X with the same edge weight, say 1. The running time is O ( T S S S P ( n + 1 , m + n , 2 W ) ) O(T_{\mathrm{SSSP}}(n+1,m+n,2W)) O ( T SSSP ( n + 1 , m + n , 2 W )) . Finally, computing R R R takes O ( n + m + W ) O(n+m+W) O ( n + m + W ) time by Lemma 8. Thus, the maximum time per iteration is O ( h 3 ( T S S S P ( n + 1 , m + n , 2 W ) + m + n ) ) O(h^{3}(T_{\mathrm{SSSP}}(n+1,m+n,2W)+m+n)) O ( h 3 ( T SSSP ( n + 1 , m + n , 2 W ) + m + n )) .
We note that since ∣ X ∣ ≥ ∣ V ( H ) ∣ / ( 8 h 2 ) > 3 n / ( 32 h 2 ) |X|\ge|V(H)|/(8h^{2})>3n/(32h^{2}) ∣ X ∣ ≥ ∣ V ( H ) ∣/ ( 8 h 2 ) > 3 n / ( 32 h 2 ) , each iteration eliminates more than 3 n / ( 32 h 2 ) 3n/(32h^{2}) 3 n / ( 32 h 2 ) vertices from H H H . Thus, the total number of iterations is at most O ( h 2 ) O(h^{2}) O ( h 2 ) , and hence the total running time is O ( h 5 ( T S S S P ( n + 1 , m + n , 2 W ) + m + n ) ) O(h^{5}(T_{\mathrm{SSSP}}(n+1,m+n,2W)+m+n)) O ( h 5 ( T SSSP ( n + 1 , m + n , 2 W ) + m + n )) , as claimed. □
Proof of lem:ball-or-pair
Since G G G is fixed throughout this subsection, we simplify notation by setting d : = d G d:=d_G d := d G and B : = B G B:=B_G B := B G . Recall that b = n / ( 8 h 2 ) b=n/(8h^{2}) b = n / ( 8 h 2 ) and that edge lengths are in ( 0 , 1 ] (0,1] ( 0 , 1 ] .
Lemma 9. Let Y = { y 1 , … , y k } Y=\{y_1,\ldots,y_k\} Y = { y 1 , … , y k } be an (ordered) set of k k k vertices such that ∣ B ( Y , 4 ) ∣ > b |B(Y,4)|>b ∣ B ( Y , 4 ) ∣ > b . Then there is a randomized algorithm, denoted by FINDPREFIX( Y ) (Y) ( Y ) , that returns either (i) a vertex x ∈ V x\in V x ∈ V such that ∣ B ( x , 11 ) ∣ > b |B(x,11)|>b ∣ B ( x , 11 ) ∣ > b or (ii) an index t ∈ [ k ] t\in[k] t ∈ [ k ] such that:
b < ∣ B ( { y 1 , … , y t } , 4 ) ∣ ≤ 3 b . b<|B(\{y_1,\ldots,y_t\},4)|\le3b. b < ∣ B ({ y 1 , … , y t } , 4 ) ∣ ≤ 3 b . The algorithm makes O ( h 2 ) O(h^{2}) O ( h 2 ) single-source shortest-path computations and spends O ( h 2 ( m + n ) ) O(h^{2}(m+n)) O ( h 2 ( m + n )) additional time, in expectation.
Proof. For notational convenience, we also allow the index t = 0 t=0 t = 0 . For every t ∈ [ 0 , k ] t\in[0,k] t ∈ [ 0 , k ] , let Y t = { y 1 , … , y t } Y_t=\{y_1,\ldots,y_t\} Y t = { y 1 , … , y t } be the prefix of Y Y Y with t t t elements; Y k = Y Y_k=Y Y k = Y and Y 0 = ∅ Y_0=\varnothing Y 0 = ∅ . Note that B ( Y 0 , 4 ) = ∅ B(Y_0,4)=\varnothing B ( Y 0 , 4 ) = ∅ . Algorithm 4 implements FINDPREFIX( Y ) (Y) ( Y ) ; see Figure 2 . The idea is to sample a vertex x ∈ V x\in V x ∈ V and check if ∣ B ( x , 11 ) ∣ > b |B(x,11)|>b ∣ B ( x , 11 ) ∣ > b . If so, we have found x x x as in the lemma and return it. Otherwise, let t t t be the smallest index in [ k ] [k] [ k ] such that d ( x , y t ) ≤ 4 d(x,y_t)\le4 d ( x , y t ) ≤ 4 . (If no such t t t exists, then Algorithm 4 would set t = 0 t=0 t = 0 , and the algorithm will try sampling x x x again since in this case ∣ B ( Y t , 4 ) ∣ = ∣ B ( Y 0 , 4 ) ∣ = 0 |B(Y_t,4)|=|B(Y_0,4)|=0 ∣ B ( Y t , 4 ) ∣ = ∣ B ( Y 0 , 4 ) ∣ = 0 .) In the next iteration, the algorithm will continue checking if Y t Y_t Y t satisfies the condition of the lemma, and if so, return it.
Figure 2. FindPrefix (Lemma 9 ). (a) A prefix Y t = { y 1 , … , y t } Y_t=\{y_1,\ldots,y_t\} Y t = { y 1 , … , y t } of the depth-first search order and the ball B ( Y t , 4 ) B(Y_t,4) B ( Y t , 4 ) . A sampled vertex x ∈ B ( Y j , 4 ) ∖ B ( Y i , 4 ) x\in B(Y_j,4)\setminus B(Y_i,4) x ∈ B ( Y j , 4 ) ∖ B ( Y i , 4 ) is within distance 4 of some y t y_t y t with i < t ≤ j i<t\le j i < t ≤ j , and B ( y t , 4 ) ⊆ B ( x , 11 ) B(y_t,4)\subseteq B(x,11) B ( y t , 4 ) ⊆ B ( x , 11 ) , so if ∣ B ( x , 11 ) ∣ ≤ b |B(x,11)|\le b ∣ B ( x , 11 ) ∣ ≤ b then ∣ B ( Y t , 4 ) ∣ ≤ ∣ B ( Y t − 1 , 4 ) ∣ + b ≤ 3 b |B(Y_t,4)|\le|B(Y_{t-1},4)|+b\le3b ∣ B ( Y t , 4 ) ∣ ≤ ∣ B ( Y t − 1 , 4 ) ∣ + b ≤ 3 b . (b) The size of B ( Y s , 4 ) B(Y_s,4) B ( Y s , 4 ) as a function of s s s : i i i is the largest index with at most b b b vertices and j j j the smallest index with more than 2 b 2b 2 b , so the band between them contains more than b b b vertices, and a uniform sample lands in it with probability at least 1 / ( 8 h 2 ) 1/(8h^2) 1/ ( 8 h 2 ) .
Algorithm 4 FINDPREFIX( Y : = { y 1 , … , y k } ) (Y:=\{y_1,\ldots,y_k\}) ( Y := { y 1 , … , y k })
1: t ← k t\gets k t ← k
2: while ∣ B ( Y t , 4 ) ∣ ≤ b |B(Y_t,4)|\le b ∣ B ( Y t , 4 ) ∣ ≤ b or ∣ B ( Y t , 4 ) ∣ > 3 b |B(Y_t,4)|>3b ∣ B ( Y t , 4 ) ∣ > 3 b do
3: sample x ∈ V x\in V x ∈ V uniformly at random
4: if ∣ B ( x , 11 ) ∣ > b |B(x,11)|>b ∣ B ( x , 11 ) ∣ > b then
5: return x x x
6: t ← t\gets t ← the smallest index in [ k ] [k] [ k ] such that d ( x , y t ) ≤ 4 d(x,y_t)\le4 d ( x , y t ) ≤ 4 , or t ← 0 t\gets0 t ← 0 if there is none
7: return t t t
Now we analyze Algorithm 4. Let i ∈ [ 0 , k − 1 ] i\in[0,k-1] i ∈ [ 0 , k − 1 ] be the largest index such that ∣ B ( Y i , 4 ) ∣ ≤ b |B(Y_i,4)|\le b ∣ B ( Y i , 4 ) ∣ ≤ b . Let j ∈ [ 1 , k ] j\in[1,k] j ∈ [ 1 , k ] be the smallest index such that ∣ B ( Y j , 4 ) ∣ > 2 b |B(Y_j,4)|>2b ∣ B ( Y j , 4 ) ∣ > 2 b . If ∣ B ( Y , 4 ) ∣ ≤ 3 b |B(Y,4)|\le3b ∣ B ( Y , 4 ) ∣ ≤ 3 b , the algorithm returns t = k t=k t = k immediately, so assume ∣ B ( Y , 4 ) ∣ > 3 b |B(Y,4)|>3b ∣ B ( Y , 4 ) ∣ > 3 b . Then i ≠ k i\ne k i = k , j j j exists, and i ≤ j i\le j i ≤ j . Observe that ∣ B ( Y j , 4 ) ∖ B ( Y i , 4 ) ∣ > b = n / ( 8 h 2 ) |B(Y_j,4)\setminus B(Y_i,4)|>b=n/(8h^2) ∣ B ( Y j , 4 ) ∖ B ( Y i , 4 ) ∣ > b = n / ( 8 h 2 ) . Then with probability at least 1 / ( 8 h 2 ) 1/(8h^2) 1/ ( 8 h 2 ) , we sample x ∈ B ( Y j , 4 ) ∖ B ( Y i , 4 ) x\in B(Y_j,4)\setminus B(Y_i,4) x ∈ B ( Y j , 4 ) ∖ B ( Y i , 4 ) in line 3. In this case, d ( x , Y ) ≤ 4 d(x,Y)\le4 d ( x , Y ) ≤ 4 and hence t t t in line 6 exists. Furthermore, i < t ≤ j i<t\le j i < t ≤ j since d ( x , Y i ) > 4 d(x,Y_i)>4 d ( x , Y i ) > 4 by the definition of x x x . Thus, by the maximality of i i i , ∣ B ( Y t , 4 ) ∣ > b |B(Y_t,4)|>b ∣ B ( Y t , 4 ) ∣ > b .
It remains to show that ∣ B ( Y t , 4 ) ∣ ≤ 3 b |B(Y_t,4)|\le3b ∣ B ( Y t , 4 ) ∣ ≤ 3 b under the assumption that ∣ B ( x , 11 ) ∣ ≤ b |B(x,11)|\le b ∣ B ( x , 11 ) ∣ ≤ b (otherwise the algorithm correctly returns x x x ). By the minimality of j j j , ∣ B ( Y t − 1 , 4 ) ∣ ≤ 2 b |B(Y_{t-1},4)|\le2b ∣ B ( Y t − 1 , 4 ) ∣ ≤ 2 b . Observe that since B ( y t , 4 ) ⊆ B ( x , 11 ) B(y_t,4)\subseteq B(x,11) B ( y t , 4 ) ⊆ B ( x , 11 ) and ∣ B ( x , 11 ) ∣ ≤ b |B(x,11)|\le b ∣ B ( x , 11 ) ∣ ≤ b , it holds that ∣ B ( y t , 4 ) ∣ ≤ b |B(y_t,4)|\le b ∣ B ( y t , 4 ) ∣ ≤ b . Thus:
∣ B ( Y t , 4 ) ∣ ≤ ∣ B ( Y t − 1 , 4 ) ∣ + ∣ B ( y t , 4 ) ∣ ≤ 2 b + b = 3 b |B(Y_t,4)|\le|B(Y_{t-1},4)|+|B(y_t,4)|\le2b+b=3b ∣ B ( Y t , 4 ) ∣ ≤ ∣ B ( Y t − 1 , 4 ) ∣ + ∣ B ( y t , 4 ) ∣ ≤ 2 b + b = 3 b
as claimed.
The running time follows from the fact that we have O ( h 2 ) O(h^2) O ( h 2 ) iterations in expectation since, as noted above, we (successfully) sample x ∈ B ( Y j , 4 ) ∖ B ( Y i , 4 ) x\in B(Y_j,4)\setminus B(Y_i,4) x ∈ B ( Y j , 4 ) ∖ B ( Y i , 4 ) in line 3 with probability at least 1 / ( 8 h 2 ) 1/(8h^2) 1/ ( 8 h 2 ) . In each iteration, we only need two shortest path computations: one from x x x and another to compute B ( Y t , 4 ) B(Y_t,4) B ( Y t , 4 ) (by adding a dummy vertex and connecting it to every vertex of Y t Y_t Y t ). □
Now we give the algorithm claimed in Lemma 7. Algorithm 5 tries to build an induced minor model of K h ( 1 ) K_h^{(1)} K h ( 1 ) , and if it fails to do so, it will either output a vertex x x x or a pair ( A , B ) (A,B) ( A , B ) as in Lemma 7. The algorithm has two major steps.
Step 1. It finds a set of h h h sets X 1 , … , X h X_1,\ldots,X_h X 1 , … , X h (see Figure 3 ) such that:
Figure 3. Step 1 of BallOrPair (Algorithm 5); all edges have length 1. (a) Case 2: F = X 1 ∪ X 2 F=X_1\cup X_2 F = X 1 ∪ X 2 is the union of the branch sets found so far, the largest component Y Y Y of G ∖ B ( F , 3 ) G\setminus B(F,3) G ∖ B ( F , 3 ) has more than b b b vertices, and X i = { y 1 , … , y t } X_i=\{y_1,\ldots,y_t\} X i = { y 1 , … , y t } is a prefix of a depth-first search order of Y Y Y . (b) The check in line 14: if more than b b b vertices (hollow) lie outside B ( X i , 5 ) B(X_i,5) B ( X i , 5 ) , the pair ( B ( X i , 4 ) , V ∖ B ( X i , 5 ) ) (B(X_i,4),V\setminus B(X_i,5)) ( B ( X i , 4 ) , V ∖ B ( X i , 5 )) is returned in line 15; the annulus between the two balls has width 1, so the two sets are at distance more than 1. (c) Case 1: every component of G ∖ B ( F , 3 ) G\setminus B(F,3) G ∖ B ( F , 3 ) has at most b b b vertices; their parts outside B ( F , 4 ) B(F,4) B ( F , 4 ) are collected into U U U (filled) until ∣ U ∣ > b |U|>b ∣ U ∣ > b , and the pair ( U , V ∖ ( B ( F , 4 ) ∪ U ) ) (U,V\setminus(B(F,4)\cup U)) ( U , V ∖ ( B ( F , 4 ) ∪ U )) is returned in line 9.
d ( X i , X j ) > 3 ( i ≠ j ) , b < ∣ B ( X i , 4 ) ∣ ≤ 3 b , ∣ V ∖ B ( X i , 5 ) ∣ ≤ b (36) d(X_i,X_j)>3\quad(i\ne j),\qquad b<|B(X_i,4)|\le3b,\qquad|V\setminus B(X_i,5)|\le b \tag*{(36)} d ( X i , X j ) > 3 ( i = j ) , b < ∣ B ( X i , 4 ) ∣ ≤ 3 b , ∣ V ∖ B ( X i , 5 ) ∣ ≤ b (36)
Each set corresponds to a vertex of K h K_h K h (but not a subdivision vertex of K h ( 1 ) K_h^{(1)} K h ( 1 ) ). The idea is to find one set at a time: at iteration i ∈ [ h ] i\in[h] i ∈ [ h ] , we find a subset X i X_i X i in G ∖ B ( F , 3 ) G\setminus B(F,3) G ∖ B ( F , 3 ) where F = X 1 ∪ … ∪ X i − 1 F=X_1\cup\ldots\cup X_{i-1} F = X 1 ∪ … ∪ X i − 1 . This is to guarantee that d ( X i , X j ) > 3 d(X_i,X_j)>3 d ( X i , X j ) > 3 ( i ≠ j ) (i\ne j) ( i = j ) . There are two cases.
Case 1. If every connected component of G ∖ B ( F , 3 ) G\setminus B(F,3) G ∖ B ( F , 3 ) has size at most b b b , then add the vertices of each connected component K K K of G ∖ B ( F , 3 ) G\setminus B(F,3) G ∖ B ( F , 3 ) outside B ( F , 4 ) B(F,4) B ( F , 4 ) to U U U , one at a time until ∣ U ∣ > b |U|>b ∣ U ∣ > b . (Our analysis below shows that U U U exists.) Then we return ( U , V ∖ ( B ( F , 4 ) ∪ U ) ) (U,V\setminus(B(F,4)\cup U)) ( U , V ∖ ( B ( F , 4 ) ∪ U )) as the pair. The reason that d ( U , V ∖ ( B ( F , 4 ) ∪ U ) ) > 1 d(U,V\setminus(B(F,4)\cup U))>1 d ( U , V ∖ ( B ( F , 4 ) ∪ U )) > 1 is because every path of length at most 1 that starts outside B ( F , 4 ) B(F,4) B ( F , 4 ) stays outside B ( F , 3 ) B(F,3) B ( F , 3 ) .
Case 2. The largest connected component Y Y Y of G ∖ B ( F , 3 ) G\setminus B(F,3) G ∖ B ( F , 3 ) has more than b b b vertices. Then we form a set { y 1 , … , y k } \{y_1,\ldots,y_k\} { y 1 , … , y k } of its vertices ordered by DFS so that every prefix induces a connected subgraph of Y Y Y . Then we apply Lemma 9 to find either (i) a vertex x x x such that ∣ B ( x , 11 ) ∣ > b |B(x,11)|>b ∣ B ( x , 11 ) ∣ > b or (ii) a prefix X i = { y 1 , … , y t } X_i=\{y_1,\ldots,y_t\} X i = { y 1 , … , y t } such that b < ∣ B ( X i , 4 ) ∣ ≤ 3 b b<|B(X_i,4)|\le3b b < ∣ B ( X i , 4 ) ∣ ≤ 3 b . In the former case, we return x x x as it satisfies Lemma 7. In the latter case, we have found
Algorithm 5 BALLORPAIR($G,h$)
1: $b := n/(8h^2)$
2: for $i = 1,\ldots,h$ do ▷ Step 1
3: $F \leftarrow X_1 \cup \cdots \cup X_{i-1}$
4: $Y \leftarrow$ largest connected component of $G \setminus B(F,3)$
5: if $|V(Y)| \leq b$ then ▷ Case 1, Step 1
6: $U \leftarrow \varnothing$
7: for each component $K$ of $G \setminus B(F,3)$ do
8: $U \leftarrow U \cup (V(K) \setminus B(F,4))$
9: if $|U| > b$ then return $(U,V \setminus (B(F,4) \cup U))$
10: $y_1,\ldots,y_k \leftarrow$ a depth-first search order of $Y$ with $k = |V(Y)|$ ▷ Case 2, Step 1
11: $(x,t) \leftarrow \operatorname{FINDPREFIX}(\{y_1,\ldots,y_k\})$ ▷ In Lemma 9
12: if $x \neq \operatorname{NULL}$ then return $x$
13: $X_i := \{y_1,\ldots,y_t\}$
14: if $|V \setminus B(X_i,5)| > b$ then
15: return $(B(X_i,4),V \setminus B(X_i,5))$ ▷ End of Step 1
16: $C \leftarrow \{v \in V : 4 < d(v,X_i) \leq 5 \text{ for every } i \in [h]\}$ ▷ Step 2
17: for every pair $1 \leq i < j \leq h$ do
18: $c_{ij} :=$ any vertex of $C$
19: if $|B(c_{ij},11)| > b$ then
20: return $c_{ij}$
21: $C \leftarrow C \setminus B(c_{ij},11)$
22: $P_{ij} \leftarrow$ the vertices of shortest paths from $c_{ij}$ to $X_i$ and to $X_j$, except their last vertices ▷ End of Step 2
23: return the induced minor model with branch sets $X_1,\ldots,X_h$ and $P_{ij}$ for $i<j$
a set X i X_i X i that satisfies the second condition of Equation (36) . The only missing condition is ∣ V ∖ B ( X i , 5 ) ∣ ≤ b |V \setminus B(X_i,5)| \leq b ∣ V ∖ B ( X i , 5 ) ∣ ≤ b , and it is guaranteed by line 14. Specifically, if ∣ V ∖ B ( X i , 5 ) ∣ > b |V \setminus B(X_i,5)| > b ∣ V ∖ B ( X i , 5 ) ∣ > b , then we can return ( B ( X i , 4 ) , V ∖ B ( X i , 5 ) ) (B(X_i,4),V \setminus B(X_i,5)) ( B ( X i , 4 ) , V ∖ B ( X i , 5 )) as the pair in Lemma 7 since the two sets are at distance greater than 1, and each of size at least b b b .
Step 2. This step finds a set { c i j } 1 ≤ i < j ≤ h \{c_{ij}\}_{1\leq i<j\leq h} { c ij } 1 ≤ i < j ≤ h (see Figure 4 ) corresponding to the subdivision vertices of K h ( 1 ) K_h^{(1)} K h ( 1 ) in the induced minor model, as well as a vertex subset P i j P_{ij} P ij of the two shortest paths from c i j c_{ij} c ij to X i X_i X i and X j X_j X j (without their last vertices in X i X_i X i and X j X_j X j ). Each c i j c_{ij} c ij belongs to the set C = { v ∈ V : 4 < d ( v , X i ) ≤ 5 for every i ∈ [ h ] } C = \{v \in V : 4 < d(v,X_i) \leq5 \text{ for every } i \in[h]\} C = { v ∈ V : 4 < d ( v , X i ) ≤ 5 for every i ∈ [ h ]} and hence:
Figure 4. Step 2 of BallOrPair and the resulting induced minor model of K h ( 1 ) K_h^{(1)} K h ( 1 ) , drawn for h = 4 h=4 h = 4 . (a) The branch sets X 1 , … , X 4 X_1,\ldots,X_4 X 1 , … , X 4 (black) are connected and pairwise at distance more than 3. Each center c i j c_{ij} c ij (orange) is at distance in ( 4 , 5 ] (4,5] ( 4 , 5 ] from every X ℓ X_\ell X ℓ , and the centers are pairwise at distance more than 11. The set P i j P_{ij} P ij (orange) consists of c i j c_{ij} c ij and the shortest paths from c i j c_{ij} c ij to X i X_i X i and to X j X_j X j without their last vertices, so it is adjacent to X i X_i X i and X j X_j X j and to no other branch set. (b) Contracting each X i X_i X i to a vertex and each P i j P_{ij} P ij to a vertex gives K 4 ( 1 ) K_4^{(1)} K 4 ( 1 ) .
4 < d ( c i j , X ℓ ) ≤ 5 for every ℓ ∈ [ h ] (37) 4 < d(c_{ij},X_\ell) \leq5 \text{ for every } \ell\in[h] \tag*{(37)} 4 < d ( c ij , X ℓ ) ≤ 5 for every ℓ ∈ [ h ] (37)
To get an induced minor model of K h ( 1 ) K_h^{(1)} K h ( 1 ) , we want { P i j } 1 ≤ i < j ≤ h \{P_{ij}\}_{1\leq i<j\leq h} { P ij } 1 ≤ i < j ≤ h to be non-adjacent. We enforce this indirectly by making sure that:
d ( c i j , c i ~ j ~ ) > 11 for { i , j } ≠ { i ~ , j ~ } . (38) d(c_{ij},c_{\tilde{i}\tilde{j}}) > 11 \text{ for } \{i,j\} \neq\{\tilde{i},\tilde{j}\}. \tag*{(38)} d ( c ij , c i ~ j ~ ) > 11 for { i , j } = { i ~ , j ~ } . (38)
Specifically, every time we take a new vertex c i j c_{ij} c ij from C C C , we update C ← C ∖ B ( c i j , 11 ) C \leftarrow C \setminus B(c_{ij},11) C ← C ∖ B ( c ij , 11 ) . If ∣ B ( c i j , 11 ) ∣ > b |B(c_{ij},11)| > b ∣ B ( c ij , 11 ) ∣ > b , then we return c i j c_{ij} c ij as the vertex in Lemma 7; otherwise, we can show that C ≠ ∅ C \neq\varnothing C = ∅ after the update, and hence we can continue the next iterations.
As long as G G G is K h ( 1 ) K_h^{(1)} K h ( 1 ) -induced-minor-free, we will never reach the last line of Algorithm 5 and hence the algorithm always either returns a vertex x x x or a pair ( A , B ) (A,B) ( A , B ) as required by Lemma 7.
Proof of Lemma 7. First, observe that Equation (36) is satisfied for { X 1 , … , X h } \{X_1,\ldots,X_h\} { X 1 , … , X h } (if the algorithm does not terminate early): d ( X i , X k ) > 3 d(X_i,X_k)>3 d ( X i , X k ) > 3 since X i X_i X i is in G ∖ B ( F , 3 ) G \setminus B(F,3) G ∖ B ( F , 3 ) , b ≤ ∣ B ( X i , 4 ) ∣ ≤ 3 b b \leq|B(X_i,4)| \leq3b b ≤ ∣ B ( X i , 4 ) ∣ ≤ 3 b by Lemma 9 , and ∣ V ∖ B ( X i , 5 ) ∣ ≤ b |V \setminus B(X_i,5)| \leq b ∣ V ∖ B ( X i , 5 ) ∣ ≤ b due to line 14.
We have argued in Case 1 that d ( U , V ∖ ( B ( F , 4 ) ∪ U ) ) > 1 d(U,V \setminus(B(F,4) \cup U))>1 d ( U , V ∖ ( B ( F , 4 ) ∪ U )) > 1 . To show that this pair satisfies Lemma 7, it remains to show that each set has size at least b b b . By construction, b < ∣ U ∣ ≤ 2 b b < |U| \leq2b b < ∣ U ∣ ≤ 2 b since every connected component of G ∖ B ( F , 3 ) G\setminus B(F,3) G ∖ B ( F , 3 ) has at most b b b vertices. Since ∣ V ∖ B ( F , 4 ) ∣ ≥ n − h ( 3 b ) > 3 b |V\setminus B(F,4)|\ge n-h(3b)>3b ∣ V ∖ B ( F , 4 ) ∣ ≥ n − h ( 3 b ) > 3 b by (36) , more than b b b vertices of V ∖ B ( F , 4 ) V\setminus B(F,4) V ∖ B ( F , 4 ) are not in U U U . Thus, the pair returned in line 9 is correct. If the algorithm returns a pair ( B ( X i , 4 ) , V ∖ B ( X i , 5 ) ) (B(X_i,4),V\setminus B(X_i,5)) ( B ( X i , 4 ) , V ∖ B ( X i , 5 )) in line 15, we have argued in Case 2 that the two sets are at distance greater than 1, and each of size at least b b b .
If the algorithm returns c i j c_{ij} c ij in line 19, then it is correct as ∣ B ( c i j , 11 ) ∣ > b |B(c_{ij},11)|>b ∣ B ( c ij , 11 ) ∣ > b . Thus, for correctness, we only need to argue that if no c i j c_{ij} c ij is returned, Step 2 would output the induced minor model of K h ( 1 ) K_h^{(1)} K h ( 1 ) (which would contradict that G G G is K h ( 1 ) K_h^{(1)} K h ( 1 ) -induced-minor-free).
First, we show that the algorithm runs exactly ( h 2 ) \binom{h}{2} ( 2 h ) iterations in Step 2 by showing that C C C is never empty. We note that B ( X i , 5 ) B(X_i,5) B ( X i , 5 ) contains at least n − b n-b n − b vertices and since ∣ B ( X i , 4 ) ∣ ≤ 3 b |B(X_i,4)|\le3b ∣ B ( X i , 4 ) ∣ ≤ 3 b , B ( X i , 5 ) ∖ B ( X i , 4 ) B(X_i,5)\setminus B(X_i,4) B ( X i , 5 ) ∖ B ( X i , 4 ) misses at most b + 3 b = 4 b b+3b=4b b + 3 b = 4 b vertices of V V V . Thus, over h h h sets, ∣ C ∣ ≥ n − h ( 4 b ) ≥ 3 n / 4 |C|\ge n-h(4b)\ge3n/4 ∣ C ∣ ≥ n − h ( 4 b ) ≥ 3 n /4 . In each iteration, we remove at most b b b vertices from C C C , over ( h 2 ) \binom{h}{2} ( 2 h ) iterations, we remove:
( h 2 ) b = ( h 2 ) n 8 h 2 < n / 16 \binom{h}{2}b=\binom{h}{2}\frac{n}{8h^2}<n/16 ( 2 h ) b = ( 2 h ) 8 h 2 n < n /16
vertices from C C C . This means C C C will never be empty.
It remains to show that { X i } 1 ≤ i ≤ h ∪ { P i j } 1 ≤ i < j ≤ h \{X_i\}_{1\le i\le h}\cup\{P_{ij}\}_{1\le i<j\le h} { X i } 1 ≤ i ≤ h ∪ { P ij } 1 ≤ i < j ≤ h form an induced minor model of K h ( 1 ) K_h^{(1)} K h ( 1 ) in G G G . Recall that the edge lengths are in ( 0 , 1 ] (0,1] ( 0 , 1 ] . For every 1 ≤ i < j ≤ h 1\le i<j\le h 1 ≤ i < j ≤ h , ℓ ∈ [ h ] ∖ { i , j } \ell\in[h]\setminus\{i,j\} ℓ ∈ [ h ] ∖ { i , j } and every neighbor u u u of X ℓ X_\ell X ℓ in G G G :
d ( c i j , u ) ≥ d ( c i j , X ℓ ) − d ( u , X ℓ ) > 4 − 1 = 3 d ( u , X i ) ≥ d ( X ℓ , X i ) − 1 > 3 − 1 = 2 d ( u , X j ) ≥ d ( X ℓ , X j ) − 1 > 3 − 1 = 2 \begin{aligned}
d(c_{ij},u)&\ge d(c_{ij},X_\ell)-d(u,X_\ell)>4-1=3\\
d(u,X_i)&\ge d(X_\ell,X_i)-1>3-1=2\\
d(u,X_j)&\ge d(X_\ell,X_j)-1>3-1=2
\end{aligned} d ( c ij , u ) d ( u , X i ) d ( u , X j ) ≥ d ( c ij , X ℓ ) − d ( u , X ℓ ) > 4 − 1 = 3 ≥ d ( X ℓ , X i ) − 1 > 3 − 1 = 2 ≥ d ( X ℓ , X j ) − 1 > 3 − 1 = 2
This means P i j P_{ij} P ij cannot contain u u u since d ( c i j , X i ) , d ( c i j , X j ) ≤ 5 d(c_{ij},X_i),d(c_{ij},X_j)\le5 d ( c ij , X i ) , d ( c ij , X j ) ≤ 5 by Equation (37) . Thus, P i j P_{ij} P ij is disjoint from X i X_i X i and X j X_j X j , has neighbors in both, and is not adjacent to any other branch sets.
Distinct sets P i j ⊆ B ( c i j , 5 ) P_{ij}\subseteq B(c_{ij},5) P ij ⊆ B ( c ij , 5 ) and by Equation (38) and the triangle inequality, P i j P_{ij} P ij and P i ′ j ′ P_{i'j'} P i ′ j ′ are at distance more than 1 and hence they are non-adjacent. Thus, { X i } 1 ≤ i ≤ h ∪ { P i j } 1 ≤ i < j ≤ h \{X_i\}_{1\le i\le h}\cup\{P_{ij}\}_{1\le i<j\le h} { X i } 1 ≤ i ≤ h ∪ { P ij } 1 ≤ i < j ≤ h form an induced minor model of K h ( 1 ) K_h^{(1)} K h ( 1 ) in G G G , as claimed.
By Lemma 9 , finding each X i X_i X i takes O ( h 2 ) O(h^2) O ( h 2 ) shortest-path computations in expectation. Step 2 also requires only O ( h 2 ) O(h^2) O ( h 2 ) shortest-path computations: one per c i j c_{ij} c ij . Thus, the overall number of shortest-path computations is O ( h 3 ) O(h^3) O ( h 3 ) .
References