39 pages. This is the TheoretiCS journal version
]]>A basic primitive in designing divide-and-conquer graph algorithms is partitioning a graph into clusters such that there are only a few edges between clusters. This type of primitive has been extensively applied in the design of divide-and-conquer algorithms. Since guaranteeing a few edges crossing different clusters in the worst case could be very expensive, we often seek a good guarantee in a probabilistic sense: the probability that two vertices u and v are placed into two different clusters is proportional to d G (u, v)/∆ where d G (u, v) is the distance between u and v in the input graph G and ∆ is the upper bound on the diameter of each cluster. A (stochastic) partition of V (G) with this property is called a separating decomposition of G [Fil19a].
In this work, we study a stronger notion of stochastic decomposition, called padded composition. More formally, given a weighed graph G = (V, E, w), a partition is ∆-bounded if the diameter of every cluster is at most ∆. A distribution D over partitions is called a (β, δ, ∆)-padded decomposition, if every partition is ∆-bounded, and for every vertex v ∈ V and γ ∈ [0, δ], we have:
where P (v) is the cluster containing v.
(1)
That is, the probability that the entire ball B G (v, γ∆) of radius γ∆ around v is clustered together, is at least e -βγ . If G admits a (β, δ, ∆)-padded decomposition for every ∆ > 0, we say that G admits (β, δ)-padded decomposition scheme. The parameter β is usually referred to as a padding parameter.
In an influential work, Klein, Plotkin and Rao [KPR93] showed that every K r minor free graph admits a weak (O(r 3 ), Ω(1))-padded decomposition scheme; the padding parameter is O(r 3 ). This result has found numerous algorithmic applications for solving problems in K r -minor-free graphs; a few examples are the flow-cut gap of O(r 3 ) for uniform multicommodity flow [KPR93], extending Lipschitz functions with absolute extendability of O(r 3 ) [LN05], the maxflow-min multicut ratio of O(r 3 ) for the multicommodity flow with maximum total commodities [TV93], an O(r 3 log log(n)) approximation for minimum linear arrangement, minimum containing interval graphs [RR05], an O(r 3 ) approximation for the 0-extension problem [CKR05], and an O(r 3 log n)-approximation for the minimum bisection problem [FK02]. An important takeaway is that key parameters quantifying the quality of these applications depend (linearly) on the padding parameter; any improvement to the padding parameter would imply the same improvement in the applications.
Fakcharoenphol and Talwar [FT03] improved the padding parameter of K r minor free graphs to O(r 2 ). Abraham, Gavoille, Gupta, Neiman, and Talwar [AGG + 19] (see also [Fil19a]) improved the padding parameter to O(r). These improvements imply an O(r) dependency on the minor size of all aforementioned applications. The only lower bound is Ω(log r) coming from the fact that r-vertex expanders (trivially) exclude K r as a minor while having padding parameter Ω(log r) [Bar96]. Closing the gap between the upper bound of O(r) and the lower bound Ω(log r) has been an outstanding problem asked by various authors[FT03, Lee12, AGG + 19, Fil19a].
Conjecture 1. There exists a padded decomposition of any K r -minor-free metric with padding parameter β = O(log r).
Progress on Conjecture 1 has been made on very special classes of minor-free graphs. Specifically, graphs with pathwidth pw admit padding parameter O(log pw) [AGG + 19]. This result implies that n-vertex graphs with treewidth tw admit padding parameter O(log tw + log log n), since the pathwidth of graphs of treewidth tw is O(tw ⋅ log(n)) (also see [KK17]). However, the padding parameter depends on n. Thus, a significant step towards Conjecture 1 is to show that graphs of treewidth tw admit a padded decomposition with padding parameter O(log tw). The best-known result (without the dependency on n) for small treewidth graphs is the same as minor-free graphs, implied by the fact that such graphs of treewidth tw exclude K tw+2 as a minor. Our first main result is to prove Conjecture 1 for the special case of treewidth-tw graphs: Theorem 1. Every weighted graph G with treewidth tw admits a (O(log tw), Ω(1))-padded decomposition scheme. Furthermore, such a partition can be sampled efficiently.
Our Theorem 1 implies that we could replace r 3 with O(log tw) in the aforementioned problems when the input graphs have treewidth tw: O(log(tw)) for uniform multicommodity flow-cut gap, extending Lipschitz functions with absolute extendability of O(log(tw)), the maxflow-min multicut ratio of O(log(tw)), an O(log(tw) log log(n)) approximation for minimum linear arrangement, minimum containing interval graphs, an O(log(tw)) approximation for the 0-extension problem, and an O(log(tw) log n)-approximation for the minimum bisection problem. Furthermore, we obtain the first ℓ 1 embedding of treewidth-tw metrics with distortion O( √ log tw ⋅ log n), an ℓ
embedding with distortion O(log tw), and O(log tw) bound for integrality gap for the uniform sparsest cut. For several of these problems, for example, uniform multicommodity flow-cut gap, maxflow-min multicut ratio, and 0-extension, our results provide the state-of-the-art approximation ratio for an entire range of parameter tw, even when tw = Ω(n). We refer readers to Section 5 for a more comprehensive discussion of these results.
Here we point out another connection to Conjecture 1. Filtser and Le [FL22] showed that one can embed any K r -minor-free metric of diameter ∆ into a graph with treewidth O r (ϵ -2 ⋅(log log n) 2 ) and additive distortion ϵ⋅∆. The dependency of O r (⋅) on r is currently huge; it is the constant in the Robertson-Seymour decomposition. However, if one could manage to get the same treewidth to be O(poly(r/ε)), then in combination with our Theorem 1, one has a positive answer to Conjecture 1. Even an embedding with a treewidth O(poly(r/ε)poly(log(n)) already implies a padding parameter O(log(r) + log log(n)), a significant progress towards Conjecture 1. Sparse Covers. A related notion to padded decompositions is sparse cover. A collection C of clusters is a (β, s, ∆)-sparse cover if it is ∆-bounded, each ball of radius ∆ β is contained in some cluster, and each vertex belongs to at most s different clusters. A graph admits (β, s)-sparse cover scheme if it admits (β, s, ∆)-sparse cover for every ∆ > 0. Sparse covers have been studied for various classes of graphs, such as general graphs [AP90], planar graphs [BLT14], minor-free graphs [KLMN04, BLT14, AGMW10], and doubling metrics [Fil19a].
By simply taking the union of many independently drawn copies of padded decomposition, one can construct a sparse cover. Indeed, given (β, δ, ∆)-padded decomposition, by taking the union of O(e βγ log n) partitions (for γ ≤ δ) one will obtain w.h.p. a (γ, O(e βγ log n), ∆)-sparse cover. In particular, using Theorem 1 one can construct (O(1), O(e log tw log n)) = (O(1), tw O(1) log n))-sparse cover scheme. The main question in this context is whether one can construct sparse covers for bounded treewidth graphs with constant cover parameter (β) and sparseness (s) independent from n. If one is willing to sacrifice a (quadratic) dependency on tw on the cover parameter β, then a sparse cover with parameters independent of n is known [KPR93,FT03,AGGM06]. However, in many applications, for example, constructing sparse spanners, it is desirable to have β = O(1) as it directly governs the stretch of the spanners.
Theorem 2. Every graph G with treewidth tw admits a (6, poly(tw))-sparse cover scheme.
It is sometimes useful to represent the sparse cover C as a union of partitions, for example, in metric embeddings [KLMN04], and the construction of ultrametric covers [FL22,Fil23], leading to the notion of padded partition cover scheme: Definition 1 (Padded Partition Cover Scheme). A collection of partitions P 1 , . . . , P τ is (β, s, ∆)padded partition cover if (a) τ ≤ s, (b) every partition P i is ∆-bounded, and (c) for every point x, there is a cluster C in one of the partitions P i such that B(x, ∆ β ) ⊆ C. A space (X, d X ) admits a (β, s)-padded partition cover scheme if for every ∆, it admits a (β, s, ∆)padded partition cover.
While a padded partition cover implies a sparse cover with the same parameters, the reverse direction is not true. For example, graphs with pathwidth pw admit (10, 5(pw + 1))-sparse cover scheme [Fil20], however, they are only known to admit (O(pw 2 ), 2 pw+1 )-padded partition cover scheme (this is due to K r -minor free graphs [KPR93,FT03] (see also [KLMN04,Fil20]))foot_0 . That is, the sparseness parameter in the padded partition cover scheme is exponentially worse (in terms of pw) than that of the sparse cover scheme. In this work, we construct a padded partition cover scheme with the same quality as our sparse covers.
Theorem 3. Every graph G with treewidth tw admits a (12, poly(tw))-padded partition cover scheme.
Tree-Ordered Net. A key new technical insight to all of our aforementioned results is the notion of tree-ordered net (Definition 2). A tree order net is analogous to the notion of nets, which were used extensively in designing algorithms for metric spaces. More formally, a ∆-net is a set of points N such that every two net points are at a distance at least ∆ (i.e min x,y∈N d X (x, y) ≥ ∆), and every point has a net point at a distance at most ∆ (i.e. max x∈V min y∈N d X (x, y) ≤ ∆). Filtser [Fil19a] showed that if there is a ∆-net such that every ball of radius 3∆ contains at most τ net points, that the metric admits a (O(log τ ), Ω(1), O(∆))-padded decomposition. This result implies that metrics of doubling dimension d have padding parameter O(d) since doubling metrics have sparse nets: τ = 2 O(d) . Unfortunately, graphs of small treewidth do not have sparse nets; this holds even in very simple graphs such as star graphs. Nonetheless, we show that small treewidth graphs possess a structure almost as good: a net that is sparse w.r.t. some partial order. We formalize this property via tree-ordered nets. As we will later show, a sparse tree-ordered net is enough to construct the padded decomposition scheme; see Section 3. We believe that the notion of a tree-ordered net is of independent interest.
x A tree order ⪯ of a set V is a partial order (i.e. transitive, reflexive, and anti-symmetric) associated with a rooted tree T and a map φ ∶ V → V (T ) such that u ⪯ v iff φ(v) is an ancestor of φ(u) in T . Given a weighted graph G = (V, E, w), a tree order ⪯ w.r.t. tree T is a valid order of G if for every edge {u, v} ∈ E, it holds that u ⪯ v or v ⪯ u or both (i.e. v is an ancestor of u, or vice versa). A simple consequence of the validity is that every connected subset C in G must contain a maximum element w.r.t ⪯; see Observation 1. For a vertex v ∈ V , and subset S ⊆ V let S v⪯ = {u ∈ S | v ⪯ u} be the ancestors of v w.r.t. T in S. Similarly, let S ⪯x = {u ∈ S | u ⪯ x} be all the descendants of x in S. See the illustration on the right. Definition 2. Given a weighted graph G = (V, E, w) and parameters τ, α, ∆ > 0, a (τ, α, ∆)-treeordered net is a triple (N, T, φ) where N ⊆ V , and T and φ define a tree order ⪯ of V such that for every v ∈ V :
That is, there exists an ancestor x of v in N such that the distance from v to x in the subgraph of G induced by descendants of x is at most ∆.
• Packing. Denote by
≤ α∆} the set of ancestor centers of v at distance at most α∆ from v (w.r.t the subgraphs induced by descendants of the ancestors). Then |N α∆ v⪯ | ≤ τ .
While we state our main result in terms of treewidth, it will be more convenient to use the notion of bounded tree-partition width [DO96]. We will show that graphs of bounded tree-partition width admit a small tree-ordered net.
Definition 3 (Tree Partition). A tree partition of a graph G = (V, E) is a rooted tree T whose vertices are bijectively associated with the sets of partition {S 1 , S 2 , . . . , S m } of V , called bags, such that for each (u, v) ∈ E, there exists a S i , S j ∈ S such that S j is a parent of S i and {u, v} ⊆ S i ∪ S j . The width of T is max i∈m {|S i |}.
Unlike a tree decomposition, bags of a tree partition are disjoint. Therefore, graphs of boundedtree partition width have a more restricted structure than graphs of bounded treewidth. Indeed, one can show that any graphs of tree-partition width k have treewidth at most 2k -1. However, from a metric point of view, graphs of bounded treewidth are the same as graphs of bounded treepartition width: We could convert a tree decomposition into a tree partition by making copies of vertices; see Lemma 2. We will show in Section 4 that: Lemma 1. Every weighted graph G = (V, E, w) with a tree-partition width tp admits a (poly(tp), 3, ∆)tree-ordered net, for every ∆ > 0.
In Section 3, we show how to use the tree-ordered net in Lemma 1 to obtain all results stated above.
Follow-up Work. Recently, inspired by our technique, [CCL + 23] constructed a tree cover with stretch 1 + ε and 2 (tw/ε) O(tw) trees. This result has applications to constructing distance oracles and approximate labeling schemes for graphs of small treewidth. Filtser [Fil24] showed recently that K r -minor-free graphs admit a (4 + ε, O(1/ε) r )-sparse cover scheme for every ε ∈ (0, 1). While the stretch is an absolute constant, the dependency on the minor size is exponential and hence is incomparable to our Theorem 2.
Graphs. We consider connected undirected graphs G = (V, E) with edge weights w ∶ E → R ≥0 . We say that vertices v, u are neighbors if {v, u} ∈ E. Let d G denote the shortest path metric in G.
The diameter of a graph G is diam(G) = max v,u∈V d G (v, u), i.e. the maximal distance between a pair of vertices. Given a subset A ⊆ V , the weak -diameter of A is diam G (A) = max v,u∈A d G (v, u), i.e. the maximal distance between a pair of vertices in A, w.r.t. to original distances d G . The strong-diameter of A is diam(G[A]), the diameter of the graph induced by A. A graph H is a minor of a graph G if we can obtain H from G by edge deletions/contractions, and isolated vertex deletions. A graph family G is H-minor-free if no graph G ∈ G has H as a minor. We will drop the prefix H in H-minor-free whenever H is not important or clear from the context. Some examples of minor-free graphs are planar graphs (K 5 -and K 3,3 -minor-free), outer-planar graphs (K 4 -and K 3,2 -minor-free), series-parallel graphs (K 4 -minor-free) and trees (K 3 -minor-free).
Treewidth. A tree decomposition of a graph G = (V, E) is a tree T where each node x ∈ T is associated with a subset S x of V , called a bag, such that: (i) ∪ x∈V (T ) S x = V , (ii) for every edge (u, v) ∈ E, there exists a bag S x for some x ∈ V (T ) such that {u, v} ⊆ S, and (iii) for every u ∈ V , the bags containing u induces a connected subtree of T . The width of T is max x∈V (T ) {|S x |}-1. The treewidth of G is the minimum width among all possible tree decompositions of G.
Padded Decompositions. Consider a partition P of V into disjoint clusters. For v ∈ V , we denote by P (v) the cluster P ∈ P that contains v. A partition P is strongly ∆-bounded (resp. weakly ∆-bounded ) if the strong-diameter (resp. weak-diameter) of every P ∈ P is bounded by ∆. If the ball B G (v, γ∆) of radius γ∆ around a vertex v is fully contained in P (v), we say that v is γ-padded by P. Otherwise, if B G (v, γ∆) / ⊆ P (v), we say that the ball is cut by the partition.
Definition 4 (Padded Decomposition). Consider a weighted graph G = (V, E, w). A distribution D over partitions of G is strongly (resp. weakly) (β, δ, ∆)-padded decomposition if every P ∈ supp(D) is strongly (resp. weakly) ∆-bounded and for any 0 ≤ γ ≤ δ, and z ∈ V ,
We say that a graph G admits a strong (resp. weak) (β, δ)-padded decomposition scheme, if for every parameter ∆ > 0 it admits a strongly (resp. weakly) (β, δ, ∆)-padded decomposition that can be sampled in polynomial time.
We first show that any graph of treewidth tw can be embedded isometrically into a graph of tree-partition width tw by duplicating vertices.
Lemma 2. Given an edge-weighed graph G(V, E, w) and its tree decomposition of width tw, there is an isometric polynomial time construable embedding of G into a graph with tree partition of width tw + 1. More formally, there is a graph H = (X, E H , w H ) with with tree partition of width tw + 1 and a map ϕ
Proof. Let B be a tree decomposition of width at most r of G = (V, E, w). We create a graph H and its tree partition as follows (see Figure 1). For each u ∈ V , if u appears in k bags of B, say B 1 , B 2 , . . . , B k , then we make k copies of u, say u 1 , u 2 , . . . , u k and replace u in bag B i with its copies u i , i ∈ [1, k]. This defines the set of vertices X of H. We then set ϕ(u) = u 1 .
If B i and B j are two adjacent bags in B, we create an edge (u i , u j ) and assign a weight w H (u i , u j ) = 0. For each (u, v) ∈ E, there exists at least one bag B j of the tree decomposition of G such that u, v ∈ B j . We add the edge (u j , v j ) of weight w H (u j , v j ) = w(u, v) to E H . This completes the construction of H.
The tree partition of H, say T , has the same structure as the tree decomposition B of G: for each bag B ∈ B, there is a corresponding bag B ˆ∈ T containing copies of vertices of B. As |B| ≤ r +1, the width of T is r + 1. For each u ∈ V , we map it to exactly one copy of u in X. As edges between copies of the same vertex have 0 weight, the distances in G are preserved exactly in H.
Using Lemma 2 together with the tree-ordered net in Lemma 1 we will construct (weak) padded decomposition and sparse covers for graphs of small treewidth.
In this section, we prove three general lemmas constructing a padded decomposition and a sparse cover from a tree-ordered net. These lemmas, together with Lemma 1, imply Theorem 1, Theorem 2, and Theorem 3. We begin with Theorem 2, as its proof is simpler. We observe the following by the definition of a tree order.
Observation 1. Let ⪯ be a valid tree order of G = (V, E, w) defined by a tree T . Every subset of vertices C such that G[C] is connected must contain a single maximum element w.r.t ⪯.
Proof. Suppose that there are t maximal elements u 1 , u 2 , . . . , u t ∈ C for t ≥ 2. Let A i = {v ∶ v ⪯ u i } for every i ∈ [t] and A = {A 1 , . . . , A t }. Then A is a partition of C since {u i } t i=1 are maximal (and T is a tree). As G[C] is connected and t ≥ 2, there must be some edge {x, y} ∈ E such that x ∈ A i and y ∈ A j for i / = j. The validity of T implies that either x ⪯ y or y ⪯ x. However, this means either x is also in A j or y is also in A i , contradicting that A is a partition of C.
The following lemma is a reduction from tree-ordered nets to sparse covers.
Lemma 3. Consider a weighted graph G = (V, E, w) with a (τ, α, ∆)-tree-ordered net (w.r.t. a tree order ⪯, associated with a tree T ), then G admits a strong ( 4α α-1 , τ, 2α∆)-sparse cover that can be computed efficiently.
Proof. Let N be the (τ, α, ∆)-tree-ordered net of G. Let x 1 , x 2 , . . . be an ordering of the centers in N w.r.t distance from the root in T . Specifically, x 1 is closest to the root, and so on. Note that distances in T are unweighted and unrelated to d G ; we break ties arbitrarily. For every vertex x i ∈ N , create a cluster
of all the vertices that are at distances at most α∆ from x i in the subgraph induced by the descendants of x i . We now show that C = {C i } i is the sparse cover claimed in the lemma.
Clearly, by the triangle inequality, every cluster in C has a diameter at most 2α∆. Furthermore, observe that every vertex v belongs to at most τ clusters since it has at most τ ancestors in N at distance at most α∆ (in the respective induced graphs).
Finally, we show that for every vertex v,
Let v B ∈ B be the closest vertex to the root w.r.t. T . Observation 1 implies that for every vertex u ∈ B, u ⪯ v B . By the triangle inequality, for every u ∈ B it holds that:
In particular, for every u ∈ B it holds that:
Thus, B is fully contained in the cluster centered in x B . As the diameter of each cluster is 2α∆, the padding we obtain is 2α∆
Now we are ready to show that Theorem 2 follows from Lemma 1, Lemma 2, and Lemma 3. We restate Theorem 2 for convenience.
Theorem 2. Every graph G with treewidth tw admits a (6, poly(tw))-sparse cover scheme.
Proof. Let ∆ > 0 be a parameter; we will construct a (6, poly(tw), ∆)-sparse cover for G. Let H be the graph of tree-partition width tw + 1 in the isometric embedding ϕ of G in Lemma 2. We abuse notation by using v,
Let ∆ ˆ= ∆/6. By Lemma 1, H admits a (poly(tw), 3, ∆ ˆ)-tree-ordered net. By Lemma 3, we can construct a (6, poly(tw), 6∆ ˆ= ∆)-sparse cover of H, denoted by C ˆ. We then construct
Let C be a cluster in C and we denote by C ˆits corresponding cluster in C ˆ; that is, C = C ˆ∩ V (G). We claim that C is a (6, poly(tw), ∆)-sparse cover for G.
For any C ∈ C, diam(C) ≤ diam(C ˆ) ≤ ∆, since ϕ is an isometric embedding. Thus, C is ∆bounded. Furthermore, any v ∈ V (G) belongs to at most poly(tw) clusters in C ˆand hence it belongs to at most poly(tw) clusters in C. Finally, we consider any ball
In this subsection, we show that the construction in Lemma 3 can be adapted to obtain a padded partition cover scheme (with a small loss in the padding parameter).
Lemma 4. Consider a weighted graph G = (V, E, w) with a (τ, α, ∆)-tree-ordered net (w.r.t. a tree order ⪯, associated with T ) for α > 2, then G admits strong ( 4α α-2 , τ, α∆)-padded partition cover.
By exactly the same argument in the proof of Theorem 2 in Section 3.1, one can show that Theorem 3 follows directly from Lemma 1, Lemma 2 and Lemma 4: first, we isometrically embed G of treewidth tw to a graph H of tree-partition width tw + 1, and then apply Lemma 4 and Lemma 1 to construct a padded partition cover P ˆfor H, which will then be turned into a padded partition cover for G by removing vertices not in G from P ˆ. Our main focus now is to prove Lemma 4.
Proof of Lemma 4. We say that a set of clusters is a partial partition if it is a partition of a subset of vertices; that is, a vertex might not belong to any cluster in a partial partition. We then can turn the partial partitions into partitions of V by adding singleton clusters. Similarly to Lemma 3, we define a set of clusters (note radius α 2 ⋅ ∆ compared to α ⋅ ∆ in Lemma 3):
Our partial partitions will consist of clusters in C only. We construct the partitions greedily: form a partition from a maximal set of disjoint clusters, preferring ones that are closer to the root, and repeat. The pseudocode is given in Algorithm 1.
Algorithm 1: Create Partial Partitions((⪯, T ), N, C)
By construction in Line 7, clusters in every partition P i are pairwise disjoint. Furthermore, for every x ∈ N , C x belongs to one of the created partitions due to Line 3. We next argue that the algorithm creates at most τ partial partitions.
Suppose for contradiction that the algorithm does not terminate after creating τ partial partitions. Thus, after τ iterations, there was still an element x ∈ A. In particular, in every iteration i, there exists some vertex x i ∈ N such that x ⪯ x i , and
By the triangle inequality:
Note that as every cluster in C can join only one partial partition, all these centers {x i } τ i=1 are unique; this contradicts the fact that N is a (τ, α, ∆)-tree-ordered net (as together with x itself,
It remains to show padding property, which is followed by the same proof as in Lemma 3.
and thus B is fully contained in the cluster centered in x B a required.
In the following lemma, we construct a padded decomposition from a tree-ordered net.
Lemma 5. Consider a weighted graph G = (V, E, w) with a (τ, α, ∆)-tree-ordered net (w.r.t. a tree order ⪯, associated with T ), then G admits a weak (16 ⋅ α+1 α-1 ⋅ ln(2τ ), α-1 8⋅(α+1) , (α + 1) ⋅ ∆)-padded decomposition that can be efficiently sampled.
By exactly the same argument in the proof of Theorem 2 in Section 3.1, one can show that Theorem 1 follows directly from Lemma 1, Lemma 2 and Lemma 5. We will use truncated exponential distribution during the proof of Lemma 5: Truncated Exponential Distributions. To create padded decompositions, similarly to previous works, we will use truncated exponential distributions. A truncated exponential distribution is an exponential distribution conditioned on the event that the outcome lies in a certain interval. More precisely, the [θ 1 , θ 2 ]-truncated exponential distribution with parameter λ, denoted by Texp [θ 1 ,θ 2 ] (λ), has the density function: f (y) = λ e -λ⋅y e -λ⋅θ 1 -e -λ⋅θ 2 , for y ∈ [θ 1 , θ 2 ]. Proof of Lemma 5. Let x 1 , x 2 , . . . be an ordering of the centers in N w.r.t distances from the root in T . Set β = α+1 2 . For every vertex
] and create a cluster:
is the ball of radius R i around x i in the graph induced by all the descendants of x i . Thus, the cluster C i of x i consists of all the points in this ball that did not join the clusters centered at the (proper) ancestors of x i . Note that C i might not be connected and that x i might not even belong to C i as it could join a previously created cluster. Nonetheless, C i has a (weak) diameter at most 2R i ≤ 2β∆ = (α + 1) ⋅ ∆ by the triangle inequality. We claim that each vertex will eventually be clustered. Indeed, consider a vertex v ∈ V . There exists some vertex x i ∈ N v⪯ at a distance at most ∆ from v in G[V ⪯x i ] by the definition of the tree-ordered net. If v did not join any cluster centered at an ancestor of x i , then v will join
It remains to prove the padding property. Consider some vertex v ∈ V and parameter γ ≤ α-1 8 . We argue that the ball B = B G (v, γ∆) is fully contained in P (v) with probability at least e -4γ⋅λ . For x i ∈ N , denote by F i the event that some vertex of B joins the cluster C i for the first time. That is, B ∩ C i ≠ ∅ and for all j < i, B ∩ C j = ∅. Denote by C i the event that F i occurred and B is cut by C i (i.e. B ⊈ C i ).
Let v B ∈ B be the vertex closest to the root of T (w.r.t distances in T ). By Observation 1, for every vertex u ∈ B, it holds that u ⪯ v B . Let x B ∈ N be the center that is an ancestor of v B and minimizes B G[V⪯x] (x, v B ). Note that v B will join the cluster of x B , if it did not join any other cluster. It follows that no descendant of x B can be the center of the first cluster having a non-trivial intersection with B. This implies that for every center
It follows from the triangle inequality that:
As N is a (τ, α, ∆)-tree-ordered net, there are at most τ centers in N i satisfying eq. (3), implying the claim.
We continue by bounding the probability of a cut by each center.
Claim 2. For every i,
). Proof. We assume that by the round i, no vertex in B is clustered, and that d G[V⪯x i ] (x i , B) ≤ β∆, as otherwise Pr[C i ] = Pr[F i ] = 0 and we are done. Let ρ be the minimal value of δ i such that if
. By our assumption, ρ ≤ β. Set ρ ˜= max{ρ, 1}. We have:
e -λe -βλ dy = e -ρ ˜⋅λe -βλ e -λe -βλ .
Therefore, if δ i ≥ ρ + 2γ, the entire ball B will be contained in C i . We conclude that:
) .
We now bound the probability that the ball B is cut. As the events {F i } x i ∈N are disjoint, we have that
where the last inequality follows as e -2γλ = e -2γλ (e (β-1)⋅λ -1)
4 ⋅λ e (β-1)⋅λ -1 = τ e (β-1)⋅λ -1 .
The inequality ( * ) holds as
To conclude, we obtain a partition where each cluster has diameter at most 2β∆ ≤ (α + 1) ⋅ ∆, and for every γ ≤ α-1 8 , every ball of radius γ ⋅ ∆ = γ α+1 ⋅ (α + 1) ⋅ ∆ is cut with probability at most e -4γ⋅λ = e -γ α+1 ⋅(α+1)⋅4⋅λ . Thus the padding parameter is (α + 1) ⋅ 4 ⋅ λ = α+1 α-1 ⋅ 16 ⋅ ln(2τ ), while the guarantee holds for balls of radius up to 1 α+1 ⋅ α-1 8 . The lemma now follows.
Herein, let T be a tree partition of G of width tp. Recall that in the definition of a tree order ⪯ realized by a tree T and a map φ ∶ V → V (T ), ⪯ is a partial order, which means ⪯ is anti-symmetric. This means φ is injective, i.e., two different vertices in V will be mapped to two distinct vertices in V (T ). In our construction presented below, it is convenient to drop the anti-symmetric property to allow two distinct vertices to be mapped to the same vertex in V (T ). We call a tree order ⪯ without the anti-symmetric property a semi-tree order.
We then can extend the notion of a tree-ordered net to a semi-tree-ordered net in a natural way: a triple (N, T, φ) is a (τ, α, ∆)-semi-tree-ordered net if T and φ define a semi-tree order on V , and N satisfies the covering and packing properties as in Definition 2. Specifically:
• Packing: for a vertex v ∈ V , denote by
≤ α∆} the set of ancestor centers of v at distance at most α∆ (here
In Section 4.1, we show that graphs of tree-partition width tp admit a good semi-tree-ordered net.
Lemma 6. Every weighted graph G = (V, E, w) with a tree-partition width tp admits a (poly(tp), 3, ∆)semi-tree-ordered net, for every ∆ > 0.
Given Lemma 6, we now show how to construct a good tree-ordered net as claimed in Lemma 1.
Proof of Lemma 1. Let (N, T ˆ, φ ˆ) be a (poly(tp), 3, ∆)-semi-tree-ordered net of G. For each vertex
Roughly speaking, to construct a tree order T for G, we simply replace x ˆin T ˆby a path, say P x ˆ, composed of vertices in φ ˆ-1 (x ˆ). The packing property remains the same, but the covering property might not hold if vertices in φ ˆ-1 (x ˆ) are ordered arbitrarily along P x ˆ. Our idea to guarantee the packing property is to place net points in φ ˆ-1 (x ˆ) closer to the root of the tree. We now formally describe the construction of T . Let N x ˆ= N ∩ φ ˆ-1 (x). N x ˆis the set of net points that are mapped to x ˆby φ ˆ. Let P x ˆbe a rooted path created from vertices in φ ˆ-1 (x) where all vertices in φ ˆ-1 (x) ∖ N x ˆare descendants of every vertex in N x ˆ. Note that if N x ˆ/ = ∅, then the root of P x ˆis a vertex in N x ˆ. Vertices in N x ˆare ordered arbitrarily in P x ˆand vertices in φ ˆ-1 (x) ∖ N x ˆare also ordered arbitrarily. (If φ ˆ-1 (x) = ∅, then P x ˆwill be a single vertex that does not correspond to any vertex in V (G).) Then we create the tree T by connecting all the paths {P x ˆ∶ x ˆ∈ V (T ˆ)} in the following way: if (x ˆ, y ˆ) is an edge in T ˆsuch that x is the parent of y, then we connect the root of P y ˆto the (only) leaf of P x ˆ. The bijection between P x ˆand φ ˆ-1 (x), unless when φ ˆ-1 (x) = ∅, naturally induce an injective map φ ∶ V (G) → T .
Let ⪯ T (⪯ T ˆ) be the tree order (semi-tree order resp.) induced by T and φ (T ˆand φ ˆresp.). To show that T and φ induce a tree order, it remains to show the validity: for every edge {u, v} ∈ E, either u ⪯ T v or v ⪯ T u. Since ⪯ T ˆis a semi-tree ordered, w.l.o.g., we can assume that φ ˆ(u) is an ancestor of φ ˆ(v); it is possible that φ ˆ(u) = φ ˆ(v). If φ ˆ(u) / = φ ˆ(v), then every vertex in P φ ˆ(u) will be an ancestor of every vertex in P φ ˆ(v) , implying that φ(u) is an ancestor of φ(v) and hence u ⪯ T v. If φ ˆ(u) = φ ˆ(v), then u and v belong to the same path P φ ˆ(u) and hence either u ⪯ T v or v ⪯ T u. Thus, the validity follows.
Finally, we show that (N, T, φ) is a (poly(tp), 3, ∆)-tree-ordered net. Observe by the construction of T that:
The converse of Observation 2 might not be true, specifically in the case when u and v are mapped to the same vertex in T ˆby φ ˆ. By Observation 2, for any vertex x ∈ V , V ⪯ T x ⊆ V ⪯ T ˆx. Thus, for any v and
v⪯ T ˆ| = poly(tp), giving the packing property. Next, we show the covering property. By the covering property of (N, T ˆ, φ ˆ), for every v ∈ V , there exists
Proof. Since y ⪯ T ˆx, as y / ∈ V ⪯ T x , it must be the case that φ ˆ(y) = φ ˆ(x) by the construction of T . Let x ˆ= φ ˆ(x). Since net points in φ ˆ-1 (x ˆ) are placed closer to the root in P x ˆand y / ∈ V ⪯ T x , y must also be a net point and x ⪯ T y.
For a bag B in T , we define T B to be the subtree of T rooted at B. For a subtree T ′ of T , we define V [T ′ ] to be the union of all bags in T ′ ; that is,
Constructing Cores. We construct a set R of subsets of the vertex set V whose union covers V ; see Algorithm 2. Each set in R is called a core. We then construct a tree ordering of the vertices of G using these sets.
We describe the notation used in Algorithm 2. For a subset U ⊆ V of vertices, we define B G (U, ∆) = ∪ u∈U B G (u, ∆) to be the ball of radius ∆ centered at U . We say that a vertex is covered if it is part of at least one core constructed so far. For any subset X ⊆ V of vertices, we use Uncov(X) to denote the set of uncovered vertices of X. We say that a bag T is covered if all the vertices in the bag are covered; a bag is uncovered if at least one vertex in the bag is uncovered.
The algorithm proceeds in rounds-the while loop in line 5-covers vertices in each round and continues until all vertices are covered. During each round, we process each connected component T ′ of the forest induced on T by the uncovered bags of T . Note that T is rooted and T ′ is a rooted subtree of T . The algorithm then works on T ′ in a top-down manner. The basic idea is to take an unvisited bag B of T ′ (initially all bags in T ′ are marked unvisited) closest to the root (line 9), carve a ball of radius ∆ centered at the uncovered vertices of B in a subgraph H (defined in line 10) of G as a new core R (line 11), mark all bags intersecting with R as visited, and repeat. We call the bag B in line 9 the center bag of R, and the uncovered vertices in B are called the centers of the core R. Graph H is the subgraph of G induced by uncovered vertices in the subtree of T ′ rooted at B and the attachments of the bags of this subtree-the set A(X) associated with each bag X. We will clarify the role of the attachments below. See Figure 2 for an illustration.
For each bag B of T a subset of vertices, we associated with B a set of vertices V [T B ], which are contained in bags of the subtree T B , called an attachment of B, denoted by A(B). The attachments allowed the cores created in a round to contain vertices in the cores formed in previous rounds. The general idea is that A(B) contains all the cores (in previous rounds) whose center bags are children of B. However, A(B) is also subjected to changes, as described next.
For a subtree T ′ of T , we use A[T ′ ] to denote the union of attachments of all bags of T ′ . Formally, A[T ′ ] = ∪ B∈T ′ A(B). When forming a core from a center bag B in a connected component T ′ , we construct a graph H, which is a subgraph G induced by uncovered vertices in the subtree T ′ B rooted at B and the attachment A[T ′ B ] (line 10). The core R is a ball of radius at most ∆ from uncovered vertices of B in H (line 11). We call H the support graph of R. Note that R may contain vertices in the attachments of the bags in T ′ B , and for each such bag, we remove vertices in R from its attachment (line 14).
Once we construct a core R from the center bag B, we have to update the attachment of the parent bag of B to contain R (line 18), unless B is the root of T ′ . If B is the root of T ′ , either B has no parent bag-B is also the root of T in this case-or the parent bag of B is covered, and hence will not belong to any connected component of uncovered bags. In both cases, the parent of B will not be directly involved in any subsequent rounds; they could be involved indirectly via the attachments. It is useful to keep in mind that if X is already a covered bag, the attachment update in Line 18 by adding a core centered at child bag B has no effect on subsequent rounds as we only consider uncovered bags. for every bag
As alluded above, cores in a specific round could contain vertices of cores in previous rounds via attachments. However, as we will show in the following claim that cores in the same round are vertex-disjoint.
Claim 4. The cores and attachments satisfy the following properties:
2. For any bag X in a connected component of unvisited bags T ′ of T considered in line 6, A(X) contains vertices in the descendant bags of X that are currently not in T ′ . As a corollary, at any point of the algorithm, A(X) only contains vertices in descendant bags of X, excluding X.
3. For every core R ∈ R centered at a bag B, vertices in R are in descendant bags of B. (B is considered its own descendant.) 4. For every core R ∈ R centered at a bag B, if a vertex u ∈ R was covered before R is created, then u is in the attachments of descendant bags of B.
Let R 1 and R 2 be two different cores created from the same connected component T ′ in the same round. Then V (R 1 ) ∩ V (R 2 ) = ∅.
Proof. We observe that the algorithm only terminates when every vertex is covered. Furthermore, the algorithm only marks an uncovered vertex as covered when it is contained in a new core (line 12), implying item 1. Item 2 follows from the fact that whenever we update the attachment of an uncovered bag X in line 18 by a core R, the center bag B of R become covered and hence will be disconnected from the connected component containing X in the next round.
For item 3, we observe that the support graph H of R in line 10 contains uncovered vertices in descendant bags of B and their attachments. By item 2, the attachment of a bag X only contains vertices in the descendant bags of X. Thus, vertices in H are in descendant bags of B, as claimed.
For item 4, observe that the only way for a covered vertex to be considered in subsequent rounds is via the attachments. Thus, item 4 follows from item 3.
For the last item 5, suppose otherwise: there is a vertex v in a bag Z such that v ∈ R 1 ∩ R 2 . W.l.o.g, we assume that R 1 is created before R 2 . Let B 1 (B 2 , resp.) be the center bag of R 1 (R 2 , resp.). Then B 1 is the ancestor of B 2 by construction, and furthermore, by item 3, Z are descendants of both B 1 and B 2 .
If Z ∈ T ′ , then when R 1 was created, all the bags on the path from B 1 to Z will be marked visited, and hence B 2 will also be marked visited, contradicting that R 2 was created from B 2 . Otherwise, Z / ∈ T ′ and that means v belongs to the attachment A(Y ) of some bag Y ∈ T ′ . Since all bags on the path from B 1 to Y are marked when R 1 was created, B 2 is not an ancestor of Y . But this means v cannot belong to a descendant bag of B 2 , contradicting item 3.
A crucial property of the core construction algorithm used in our analysis is that it has a natural hierarchy of clusters associated with it. To define this hierarchy, we need some new notation. Let T ′ be a connected component of uncovered bags in a specific round. Let
be a set of vertices, called the cluster associated with T ′ . Note that V (H) ⊆ C T ′ . The following lemma implies that clusters over different rounds form a hierarchy. Lemma 7. Let T 1 and T 2 be two different connected components of uncovered bags. If T 1 and T 2 belong to the same round, then C T 1 ∩ C T 2 = ∅. If T 1 and T 2 belong to two consecutive rounds such that T 2 is a subtree of T 1 , then C T 2 ⊆ C T 1 .
Proof. We prove the lemma by induction. The base case holds since in round 1, we only have a single tree T whose associated cluster C T = V (G). Let T ′ be a connected component of uncovered bags at round i, and T 1 , T 2 be two different components of uncovered bags that are subtrees of T ′ in round i + 1. It suffices to show that C T i ⊆ C T ′ for any i = 1, 2, and
Observe that in a round i, the attachment of a bag X either shrinks (due to the removal in line line 15) or grows by the addition of the cores. As any core R 1 created from T ′ is a subset of the cluster C T ′ , A(X) remains a subset of C T ′ in both cases. This means all attachments of bags in
Let B 1 and B 2 be the root bag of T 1 and T 2 , respectively. Assume w.l.o.g that B 1 is an ancestor of B 2 . Let X be the (only) leaf of B 1 that is the ancestor of B 2 . By item 4 of Claim 4, only the attachment of X could possibly have a non-empty intersection C T 2 . Suppose that there exists a vertex v ∈ A(X) ∩ C T 2 . Let B be the child bag of X that is an ancestor of B 2 . Then B ∈ T ′ and B the center bag of a core R created in round i. Observe that v ∈ R. When R was created, all the uncovered vertices in T ′ in R were marked covered. This means R ∩ Uncov(V [T 2 ]) = ∅. Thus, v ∈ R ∩ A(Y ) for some bag Y ∈ T ′ in round i + 1. However, by line 15, v will be removed from A(Y ) in round i and hence will not be present in A(Y ) in round i + 1, a contradiction. Thus,
The Semi-tree-ordered Net. We now construct a tree ordering of the vertices using R. We define the rank of a core R, denoted by rank(R), to be the round number when R is constructed. That is, rank(R) = i if R was constructed in the i-th round. Lastly, for a vertex v, we define Q(v) to be the center bag of the smallest-rank core containing v. We observe that: Observation 3. The core R covering v for the first time is the smallest-rank core containing v.
We now define the tree ordering of vertices, and the tree-ordered net as follows.
• Let T be the rooted tree that is isomorphic to the tree partition T of G; each node
x ∈ T corresponds to a bag B x in T .
• The map φ ∶ V → V (T ) maps each vertex v to a node φ(v) such that its corresponding bag B φ(v) is exaclty Q(v). This map naturally induces a partial ordering of vertices in V : u ⪯ v if and only if Q(v) is an ancestor of Q(u) in the tree partition T .
• The tree-ordered net N is the union of all the centers of the cores in R. Recall that the centers of a core is the set of uncovered vertices of the center bag in line 11.
The semi-tree-ordered net for G is (N, T, φ).
The following lemma follows directly from the description of the algorithm and the discussion above.
Lemma 8. Given the tree partition T of G, the semi-tree-ordered net (N, T, φ) can be constructed in polynomial time.
We can see that the tree ordered induced by T and φ is a semi-tree-order since it does not have the anti-symmetric property: there could be two different vertices u and v such that Q(u) = Q(v) and hence they will be mapped to the same vertex of T via φ.
We now show all properties of the tree-ordered net (N, T, φ) as stated in Lemma 1. Specifically, we will show the covering property in Lemma 9 and the packing property in Lemma 14. We start with the covering property.
Lemma 9. Let (N, T, φ) be the tree-ordered net defined in TreeOrdering. For every vertex v ∈ V there is an
Proof. By item 1 of Claim 4, v is in at least one core of R. Let R ∈ R be the core of the smallest rank containing v. Let B be the center bag of R. Note that Q(v) = B by definition.
Let U ⊆ R be the set of uncovered vertices in R when R is created; all vertices in U will be marked as covered in line 12 after R is created. We observe that:
1. All vertices in U are equivalent under the tree ordering ⪯. This is because Q(u) = B for every u ∈ U by Observation 3 and definition of Q(⋅).
2. For any two vertices z ∈ R ∖ U and u ∈ U , z ≺ u. To see this, observe that, by item 4 in Claim 4, z is in the attachment of some bag Y , which is the descendant of the center bag B.
By item 2 and the definition of
Let H be the support graph (in line 10) of R. By the construction of R (line 11),
This means there exists an
The packing property is substantially more difficult to prove. Our argument goes roughly as follows. First, we show that cores satisfy various properties, and one of them is that, for every bag B in T , there are at most O(tp 2 ) cores intersecting B, and moreover, for every vertex v, there are at most O(tp) cores that contain v (Corollary 1). This allows us to bound |N 2∆ v⪯ | via bounding the number of cores that contain at least one vertex in N 2∆ v⪯ . This set of cores can be partitioned into two sets: those that contain v-there are only O(tp) of them-and those that do not contain v.
To bound the size of the latter set, we basically construct a sequence of cores of strictly increasing ranks R * 1 , R * 2 , . . . , R * ℓ for ℓ ≤ tp, and for each R * j , show that there are only O(tp 2 ) ancestral cores of R * j that are not ancestors of lower ranked cores in the sequence. This implies a bound of O(tp 3 ) on the set of cores, giving the packing property.
We begin by analyzing several properties of the cores.
Lemma 10. The cores of the same rank are vertex-disjoint.
Proof. Let R 1 and R 2 be two cores of the same rank, say r. Let B k be the center bags of R k for k = 1, 2. If B 1 and B 2 belong to two different connected components of uncovered bags in round r, then by Lemma 7, R 1 ∩ R 2 = ∅. Thus, we only consider the complementary case where B 1 and B 2 belong to the same connected component. Suppose for contradiction that there exists v ∈ R 1 ∩ R 2 . By item 3 in Claim 4, R k only contains vertices in descendant bags of B k . As R 1 ∩ R 2 / = ∅, either B 1 is an ancestor of B 2 or B 2 is ancestor of B 1 . W.l.o.g., we assume that B 1 is an ancestor of B 2 . Let Y be the bag containing v. Then Y is the descendant of both B 1 and B 2 . As endpoints of edges of G are either in the same bag or in two adjacent bags of the tree partition, R 1 ∩ Y / = ∅ implies that R 1 ∩ B 2 / = ∅. Thus, B 2 will be marked as visited in line 13 of the algorithm, and hence R 2 will not have the same rank as R 1 , a contradiction.
Lemma 11. The algorithm has at most tp iterations. Therefore, rank(R) ≤ tp for every R ∈ R.
Proof. Let B ′ be any bag of T . We claim that in every iteration, at least one uncovered vertex of B ′ gets covered. Thus, after tp iterations, every vertex of B ′ is covered, and hence the algorithm will terminate.
Consider an arbitrary iteration where B ′ remains uncovered; that is, at least some vertex of B ′ is uncovered. Let T ′ be the connected component of uncovered bags of T containing B ′ . If B ′ got picked in line 11, then all uncovered vertices of B ′ are marked as covered (in line 12), and hence the claim holds. Otherwise, B ′ is marked visited in line 13 when a core R ∈ R is created. Let H be the support graph of R. By item 2 in Claim 4, the attachment of every bag in T ′ does not contain any vertex of B ′ . Thus, H only contains uncovered vertices of B ′ . As R ∩ B ′ / = ∅, R contains at least one uncovered vertex of B ′ , which will be marked as covered in line 12; the claim holds.
We obtain the following corollary of Lemma 10 and Lemma 11.
Corollary 1. Each vertex is contained in at most tp cores. Furthermore, the number of cores intersecting any bag is at most tp 2 . Proof. By Lemma 10, cores of the same rank are vertex-disjoint. Thus, each vertex belongs to at most one core of a given rank. As there are tp different ranks by Lemma 11, each vertex belongs to at most tp cores.
Let B be any bag in T . As the cores of the same rank are vertex-disjoint by Lemma 10, there is at most tp cores of a given rank intersecting B. As there are at most tp different ranks by Lemma 11, the total number of cores intersecting any bag is at most tp 2 .
We define the rank of a vertex v, denoted by rank(v), to be the lowest rank among all the cores containing it: rank(v) = min R∈R∧v∈R rank(R). The following also follows from the algorithm.
Lemma 12. Let B be the center bag of a core R, and U be its center. If R has rank i, then every vertex v ∈ B ∖ U has rank strictly smaller than i.
Proof. When R is constructed (in line 11), all uncovered vertices of B are in U and will be marked as covered afterward. Thus, before R is constructed, vertices in B ∖ U must be marked covered, and furthermore, B is not marked as visited. This means vertices in B ∖ U are marked in previous rounds, and hence have ranks strictly smaller than i.
Next, we introduce central concepts in the proof of the packing property. We say that a core R 1 is an ancestor (descendant resp.) of R 2 if the center-bag of R 1 is an ancestor (descendant resp.) of R 2 . For any bag of T , we define its level to be the hop distance from the root in T . Also, we define the graph rooted at B to be the subgraph of G induced by the subtree of T rooted at B. For any core R, we define a graph G T [R] to be the subgraph of G induced by vertices in the bags of the subtrees of T rooted at the center-bag of R; see Figure 3(a).
Let A ≺ (R) be the set of cores that are ancestors of R and have rank strictly less than R. We define the shadow domain of a core R to be the graph obtained from G T [R] by removing the vertices that are contained in at least one core in A ≺ (R). The shadow of a core R, denoted by shadow(R), is defined as the ball of radius ∆ centered around R in the shadow domain of R. The strict shadow of R is defined as its shadow minus itself, i.e., shadow(R) ∖ R. To bound the size of N 2∆ v⪯ , for a vertex v we are interested in the cores and their shadows where v is located. See Figure 3(b).
We observe the following properties of ranks and shadow domains.
Lemma 13. Let R 1 and R 2 be two cores such that rank(R 1 ) ≥ rank(R 2 ) and R 1 is an ancestor of R 2 . For each i ∈ {1, 2}, let D i , B i , and Y i be the shadow domain, the center bag, and the center of R i , respectively. (Note that
rooted at its center bag, (b) the shadow domain, shadow and strict shadow of core R 2 .
○ Rank of R: the round number when R is constructed.
○ Central bag of R -the bag from line 9, from which we grew the core. ○ Core R1 is an ancestor of R2 if the center-bag of R1 is an ancestor of R2 (independent of round).
○ The level of a bag B is the hop distance from the root in T . 2. If rank(R 1 ) > rank(R 2 ) and there are no cores of rank smaller than R 2 whose center bag is in the path between
Proof. We first show item 1. Let x be a vertex in V (D 1 ) ∩ (B 2 ∖ Y 2 ). By Lemma 12, rank(x) < rank(R 2 ), implying that x is contained in a core R 3 such that rank(R 3 ) < rank(R 2 ). Furthermore, R 3 is a descendant of R 1 as otherwise, by the definition of shadow domain, R 3 ∩ V (D 1 ) = ∅ and hence x / ∈ V (D 1 ), a contradiction. Also, R 3 is an ancestor of R 2 as the center-bag of R 2 contains a vertex of R 3 , which is x.
We show item 2 by contrapositive. Let x be a vertex in G T [R 2 ] such that x / ∈ V (D 2 ). We show that x / ∈ V (D 1 ). Since x is not in V (D 2 ), there exists an ancestor core R 3 of R 2 such that x ∈ R 3 and rank(R 3 ) < rank(R 2 ). By the assumption in item 2, R 3 is also an ancestor of R 1 and hence R 3 ∈ A ≺ (R 1 ). Thus, x / ∈ V (D 1 ) as claimed.
Equipped with the lemmas above, we are finally ready to prove the packing property with α = 2.
Lemma 14. Let (N, T, φ) be the tree-ordered net defined in TreeOrdering. For every vertex
Proof. Consider a vertex v ∈ V . Recall that the net N is the set of centers of all cores in R. Let C all be the set of cores that have a non-empty intersection with the vertices in N 2∆ v⪯ . Instead of bounding |N 2∆ v⪯ | directly, we bound |C all |. Note that every vertex in N 2∆ v⪯ is in the center of one of the cores in C all .
Let C ∆ ⊆ C all be the cores that contain v and let C ∶= C all ∖ C ∆ . By Corollary 1, |C ∆ | ≤ tp. The bulk of our proof below is to show that |C| ≤ tp 3 . Since each core has at most tp centers, we have
We now focus on proving that |C| ≤ tp 3 . Let B v be the bag containing v. Let P be the path in T from the root bag to B v . We claim that every core in C has a center bag on P. This is because every core R in C contains a vertex, say x, in N 2∆ v⪯ , whose bag is an ancestor of B v . By construction in line 11, every vertex in R is in a descendant of the center bag of R. This means B v is a descendant of the center bag of R, implying the claim.
The rest of our proof goes as follows:
• Let r 1 be the lowest rank among all cores in C. We will show in Claim 5 below that there is only one core in C having rank r 1 . Let this unique core in C with rank r 1 be R * 1 . Let C 1 be the set of all cores in C that are ancestors of R * 1 , including R * 1 . We then show in the next Claim 6 that each core in C 1 intersects the center of R * 1 . Since the center is contained in a bag, Corollary 1 implies that |C 1 | ≤ tp 2 .
• Next, let C ¯1 = C ∖ C 1 . If C ¯1 is non-empty, we define r 2 be the lowest rank among cores in C 1 ¯.
Note that r 2 > r 1 . Claim 5 below again implies that there is only one core in C ¯1 having rank r 2 . Let this unique core in C ¯1 with rank r 2 be R * 2 . Let C 2 be the set of all ancestor cores R * 2 in C ¯1 including R * 2 . Then Claim 6 implies that each core in C 2 intersects the center of R * 2 . Since the center is contained in a bag, Corollary 1 gives that |C 2 | ≤ tp 2 .
• Inductively, we define the sequence of sets of cores C 1 , C 2 , C 3 , . . . , C ℓ and r 1 < r 2 < ⋅ ⋅ ⋅ < r ℓ until C ¯ℓ = C ¯ℓ-1 ∖ C ℓ is empty. Here, r j is defined as the lowest rank among cores in C ¯j-1 , and C ¯0 = C. For each j ∈ [ℓ], Claim 5 implies that there exist a unique core R * j in C ¯j-1 with rank r j . Let C j be the set of all cores in C ¯j that are ancestors of R * j , including R * j . Claim 6 then implies that all cores in C j intersect the center of R * j in. Thus, |C j | ≤ tp 2 for each j ∈ [ℓ] by Corollary 1. By Lemma 11, r 1 < r 2 < ⋅ ⋅ ⋅ < r ℓ ≤ tp, implying that |C| ≤ tp 3 as desired.
For the rest of the proof, we prove two claims.
Claim 5. There is only one core in C ¯j-1 having rank r j for each j ∈ [ℓ].
Proof. Suppose otherwise. Then there are two cores R 1 and R 2 in C ¯j-1 having rank r j . Assume w.l.o.g. that R 1 is an ancestor of R 2 . By Lemma 10, R 1 and R 2 are disjoint as they have the same rank. Also, since R 1 , R 2 ∈ C, the center-bags of R 1 and R 2 lie on the path P. Since R 1 contains a point of N 2∆ v⪯ , v is in the shadow of R 1 . Thus, there is a path Z of length at most 2∆ that goes from the center of R 1 to v in the shadow domain of R 1 . This path Z has to intersect the center bag of R 2 to get to v.
Suppose this intersection occurs at a vertex in the center of R 2 ; see Figure 5(a). Then the path Z goes from the center of R 1 to outside R 1 and then into the center of R 2 and then to outside of R 2 . It has to go outside of R 2 as v is in the strict shadow of R 2 . Also, it has to go outside of R 1 before entering R 2 as R 1 and R 2 are vertex disjoint (however, it is possible that there is an edge from R 1 to R 2 ). This means Z has a length of more than ∆ + ∆ = 2∆, a contradiction. Now, suppose this intersection occurs at a vertex in the center-bag of R 2 that is not in the center of R 2 ; see Figure 5(b). Then by item 1 (of Lemma 13) it follows that there is at least one core that is ancestor of R 2 and descendant of R 1 , and having rank lower than r j . Let R 3 be the one among such cores whose center-bag has the smallest level.
We claim that the path Z intersects the center of R 3 . Suppose otherwise. However, the path has to intersect the center-bag of R 3 to get to v. Then, by item 1 (of Lemma 13) it follows that there is a core that is ancestor of R 3 and descendant of R 1 , and having rank lower than r j , a contradiction to the selection of R 3 .
By definition of shadow domain, R 3 is disjoint from the shadow domain of R 2 . Hence v is not in R 3 . However, v is contained in the shadow of R 3 as the part of the path Z from the center of R 3 to v is contained in the shadow domain of R 3 and has length at most 2∆. Thus, v is contained in the strict shadow of R 3 . Since R 3 is a descendant of R 1 , we have that R 3 ∉ C 1 ∪ C 2 ∪ ⋅ ⋅ ⋅ ∪ C j-1 and hence R 3 ∈ C ¯j-1 . Thus, there is a core in C ¯j-1 that has rank lower than r j , a contradiction to the choice of r j . Claim 6. Each core in C j intersects the center of R * j for each j ∈ [ℓ].
Proof. Suppose this is not true, and let j be the minimum index for which the claim does not hold.
Then there exists a core R ∈ C j that is disjoint from the center of R * j . Note that R * j is a descendant of R by definition of C j and the rank of R * j is strictly less than the rank of R by the definition of R * j . Since v is in the shadow of R there is a path Z of length at most 2∆ that goes from the center of R to v in the shadow domain of R. This path Z has to intersect the center-bag of R * j to get to v.
Suppose this intersection occurs at a vertex in the center of R * j . Then the path Z goes from the center of R outside R and then into the center of R * j and then to outside of R * j . It has to go outside of R * j as v is in the strict shadow of R * j . Also, it has to go outside of R before entering R * j as R and the center of R * j are vertex disjoint (this is what we assumed for the sake of contradiction). This means Z has a length of more than ∆ + ∆ = 2∆, a contradiction. Now, suppose this intersection occurs at a vertex in the center-bag of R * j that is not in the center of R * j . Then, by item 1 (of Lemma 13), there exist at least one core that is an ancestor of R * j and a descendant of R and having rank lower than r j . Let R ′ be the one among such cores whose center-bag has the smallest level. The path Z has to intersect the center of R ′ as otherwise there is a core that is an ancestor of R ′ and a descendant of R and having rank lower than r j , contradicting the selection of R ′ . Note that v is not in R ′ as R ′ is disjoint from the shadow domain of R * j by definition of shadow domain. However, v is contained in the shadow of R ′ as the part of the path Z from center of R ′ to v is contained in the shadow domain of R ′ (by item 2 of Lemma 13) and has length at most 2∆. Thus, v is contained in the strict shadow of R ′ . Since j is the minimum index for which the statement of the claim does not hold, if R ′ ∈ C 1 ∪ . . . C j-1 , then R / ∈ C j . This implies that R ′ ∈ C j . Thus we have a core in C j having rank strictly smaller than r j , a contradiction.
The discussion in the proof outline with Claim 5 and Claim 6 proves the lemma.
In this section, we gave a more detailed exposition of the applications of Theorem 1 and Theorem 2 mentioned in Section 1. The list of applications here is not meant to be exhaustive, and we believe that our result will find further applications.
Given an edge-capacitated graph G = (V, E, c) and a set K ⊆ V of terminals, a K-flow is a flow where all the endpoints are terminals. A flow-sparsifier with quality ρ ≥ 1 is another capacitated graph H = (K, E H , c H ) such that (a) any feasible K-flow in G can be feasibly routed in H, and (b) any feasible K-flow in H can be routed in G with congestion ρ (see [EGK + 14] for formal definitions).
Englert et al. [EGK + 14] showed that given a graph G which admits a (β, 1 β )-padded decomposition scheme, then for any subset K, one can efficiently compute a flow-sparsifier with quality O(β). Using their result, we obtain the following corollary of Theorem 1.
Corollary 2. Given an edge-capacitated graph G = (V, E, c) with treewidth tw, and a subset of terminals K ⊆ V , one can efficiently compute a flow sparsifier with quality O(log tw).
The best previously known result had quality O(tw) approximation [EGK + 14, AGG + 19]. Thus, our result improves the dependency on tw exponentially. For further reading on flow sparsifiers, see [Moi09, MT10, MM10, CLLM10, Chu12, AGK14].
We note that, though the graph G has treewidth tw, the flow-sparsifier H in Corollary 2 can have arbitrarily large treewidth. Having low treewidth is a very desirable property of a graph, and naturally, we would like to have a sparsifier of small treewidth. A flow-sparsifier
That is, H can be obtained from G by deleting/contracting edges, and deleting vertices. Englert et al. [EGK + 14] showed that given a graph G which admits a (β, 1 β )-padded decomposition scheme, then for any subset K, one can efficiently compute a minor-based flow-sparsifier with quality O(β log β). By Theorem 1, we obtain: Corollary 3. Given an edge-capacitated graph G = (V, E, c) with treewidth tw, and a subset of terminals K ⊆ V , one can efficiently compute a minor-based flow-sparsifier H = (K, E H , c H ) with quality O(log tw log log tw). In particular, H also has treewidth tw.
Given a metric space (X, d X ), a (α, τ, ∆)-sparse partition is a partition C of X such that:
• Low Diameter: ∀C ∈ C, the set X has diameter at most ∆;
• Sparsity: ∀x ∈ X, the ball B X (x, ∆ α ) intersects at most τ clusters from C.
We say that the metric (X, d X ) admits a (α, τ )-sparse partition scheme if for every ∆ > 0, X admits a (α, τ, ∆)-sparse partition. Jia et al. [JLN + 05] implicitly proved (see [Fil20] for an explicit proof) that if a space admits a (β, s)-sparse cover scheme, then it admits a (β, s)-sparse partition scheme. Therefore, by g Theorem 2 we obtain: Corollary 4. Every graph G with treewidth tw admits a (O(1), poly(tw))-sparse partition scheme.
Previously, it was only known that graphs with treewidth tw admit (O(tw 2 ), 2 tw )-sparse partition scheme [FT03,Fil20]. Thus, Corollary 4 implies an exponential improvement in the dependency on tw. For further reading on sparse partitions, see [JLN + 05, BDR + 12, Fil20, CJF + 23, Fil24].
We consider the problem of designing a network that allows a server to broadcast a message to a single set of clients. If sending a message over a link incurs some cost, then designing the best broadcast network is classically modeled as the Steiner tree problem [HR92]. However, if the server has to solve this problem repeatedly with different client sets, it is desirable to construct a single network that will optimize the cost of the broadcast for every possible subset of clients. This setting motivates the Universal Steiner Tree (UST) problem.
Given a metric space (X, d X ) and root r ∈ X, a ρ-approximate UST is a weighted tree T over X such that for every S ⊆ X containing r, we have w(T {S}) ≤ ρ ⋅ OPT S where T {S} ⊆ T is the minimal subtree of T connecting S, and OPT S is the minimum weight Steiner tree connecting S in X.
A closely related problem to UST is the Universal Traveling Salesman Problem (UTSP). Consider a postman providing post service for a set X of clients with n different locations (with distance measure d X ). Each morning, the postman receives a subset S ⊂ X of the required deliveries for the day. In order to minimize the total tour length, one solution may be to compute each morning an (approximation of an) Optimal TSP tour for the set S. An alternative solution will be to compute a Universal TSP (UTSP) tour R containing all the points X. Given a subset S, R{S} is the tour visiting all the points in S w.r.t. the order induced by R. Given a tour T , denote its length by |T |. The stretch of R is the maximum ratio among all subsets S ⊆ X between the length of R{S} and the length of the optimal TSP tour on S, max S⊆X |R{S}| |Opt(S)| . Jia et al. [JLN + 05] showed that for every n-point metric space that admits (σ, τ )-sparse partition scheme, there is a polynomial time algorithm that given a root rt ∈ V computes a UST with stretch O(τ σ 2 log τ n). In addition, Jia et al. [JLN + 05] also showed that such a metric admit a UTSP with stretch O(τ σ 2 log τ n). Using our Corollary 4, we conclude: Corollary 5. Consider an n-point graph with treewidth tw. Then it's shortest path metric admits a solution to both universal Steiner tree and universal TSP with stretch poly(tw) ⋅ log n.
The best-known previous result for both problems had a stretch of exp(tw) ⋅ log n [Fil20], which is exponentially larger than ours in terms of the tw dependency. For further reading on the UTSP and TSP problems, see [PBI89, BG89, JLN + 05, GHR06, HKL06, SS08, GKSS10, BCK11, BDR + 12, BLT14, Fil20, Fil24]. Interestingly, our solution to the UST problem in Corollary 5 produces a solution which is not a subgraph of the low treewidth input graph G. If one requires that the UST will be a subgraph of G, the current state of the are is by Busch et al. [BCF + 23] who obtained stretch O(log 7 n). To date, this is also the best known upper bound for graph with bounded treewidth.
Given a graph G = (V, E, w), and a subset of terminals K ⊆ V , in the Steiner point removal problem, we are looking for a graph H = (K, E H , w H ), which is a minor of G. We say that H has stretch t, if for every u
showed that given a graph G which admits a (β, 1 β )-padded decomposition scheme, one can compute a distribution D over minors H = (K, E H , w H ), such that for every u, v ∈ K, and
That is, the minor has expected stretch O(β log(β)). Thus, by Theorem 1, we obtain: Corollary 6. Given a weighted graph G = (V, E, w) with treewidth tw, and a subset of terminals K ⊆ V , one can efficiently sample a minor H
In the 0-Extension problem, the input is a set X, a terminal set K ⊆ X, a metric d K over the terminals, and an arbitrary cost function c( X 2 ) → R + . The goal is to find a retraction f ∶ X → K that minimizes ∑ {x,y}∈( X 2 ) c(x, y) ⋅ d K (f (x), f (y)). A retraction is a surjective function f ∶ X → K that satisfies f (x) = x for all x ∈ K. The 0-Extension problem, first proposed by Karzanov [Kar98], generalizes the Multiway Cut problem [DJP + 92] by allowing d K to be any discrete metric (instead of a uniform metric).
For the case where the metric (K, d K ) on the terminals admits a (β, 1 β )-padded-decomposition, Lee and Naor [LN05] (see also [AFH + 04, CKR04]) showed an O(β) upper bound. By Theorem 1, we get: Corollary 7. Consider an instance of the 0-Extension problem (K ⊆ X, d, k , c ∶ ( X 2 ) → R + ), where the metric (K, d K ) is a sub-metric of a shortest path metric of a graph with treewidth tw. Then, one can efficiently find a solution with cost at most O(log tw) times the cost of the optimal. In particular, there is a O(log tw)-approximation algorithm for the multi-way cut problem for graphs of treewidth tw. to be the Lipschitz parameter of the function. In the Lipschitz extension problem, we are given a map f ∶ Z → Y from a subset Z of X. The goal is to extend f to a function f ˜over the entire space X, while minimizing ∥f ˜∥Lip as a function of ∥f ∥ Lip . Lee and Naor [LN05], proved that if a space admits a (β, 1 β )-padded decomposition scheme, then given a function f from a subset Z ⊆ X into a closed convex set in some Banach space, then one can extend f into f ˜∶ X → C such that ∥f ˜∥Lip ≤ O(β) ⋅ ∥f ∥ Lip . By Theorem 1, we obtain:
Corollary 8 (Lipschitz Extension). Consider a graph G = (V, E, w) with treewidth tw, and let f ∶ V ′ → C be a map from a subset V ′ ⊆ V into C, where C is a convex closed set of some Banach space. Then there is an extension f ˜∶ X → C such that ∥f ˜∥Lip ≤ O(log tw) ⋅ ∥f ∥ Lip .
Metric embedding is a map between two metric spaces that preserves all pairwise distances up to a small stretch. We say that embedding f ∶ X → Y between (X, d X ) and (Y, d Y ) has distortion t if for every x, y ∈ X it holds that d X (x, y) ≤ d Y (f (x), f (y)) ≤ t ⋅ d X (x, y). Krauthgamer, Lee, Mendel and Naor [KLMN04] (improving over Rao [Rao99]) showed that every n-point metric space that admits (β, 1 β )-padded decomposition scheme can be embedded into an ℓ p space with distortion O(β 1-1 p ⋅ (log n) 1 p ). Previously, it was known that the shortest path metric of an n point graph with treewidth tw (or more generally K tw -minor free) embeds into ℓ p space with distortion O((tw) Since every finite subset of the Euclidean space ℓ 2 embed isometrically into ℓ p (for 1 ≤ p ≤ ∞), it follows that for 1 ≤ p ≤ ∞ such G can be embedded into into ℓ p space (in particular ℓ 1 ) with distortion O( √ log tw ⋅ log n). A norm space of special interest is ℓ ∞ , as every finite metric space embeds into ℓ ∞ isometrically (i.e. with distortion 1, this is the so called Fréchet embedding). However the dimension of such embedding is very large: Ω(n). Krauthgamer et al. [KLMN04] proved that every graph with treewidth tw (or more generally K tw -minor free) embeds into ℓ d ∞ with dimension d = O ˜(3 tw ) ⋅ log n and distortion O(tw 2 ). This was recently improved by Filtser [Fil24] who showed that every graph with treewidth tw (or more generally K tw -minor free) embeds into ℓ d ∞ with dimension d = O ˜(tw 2 )⋅log n and distortion O(tw) (alternatively distortion 3+ε and dimension d = O ˜( 1 ε ) tw+1 ⋅log n). More generally, Filtser [Fil24] proved that if a graph G admits a (β, s)-padded partition cover scheme, then G embeds into ℓ
A major open question is to determine the padding parameter of K r -minor-free graphs. The current state of the art is O(r) [AGG + 19] (see also [Fil19a]), while the natural conjecture is exponentially smaller O(log r). A somewhat weaker guarantee, we call (t, p, ∆)-stochastic decomposition, is a distribution over partitions with diameter ∆ such that every pair of vertices at distance at most ∆ t is clustered together with probability at least p. Compared to padded decomposition, the guarantee here is over pairs (instead of balls), and there is a threshold distance for the guarantee (instead of a linear dependence as in padded decomposition). Nonetheless, for many applications, a stochastic decomposition is good enough. Moreover, in most cases, the parameters of padded and stochastic decompositions are the same. The only case that we are aware of where they are different is high-dimensional Euclidean spaces. In particular, for minor-free graphs, the best-known result is a (O(r), 1 2 , ∆)-stochastic decomposition [AGG + 19]. Here, we argue that if the parameters of recently studied stochastic embeddings with additive distortion are improved, then our Theorem 1 will imply much better stochastic decompositions for minor-free graphs. Note that if B G (v, ∆ t ) ⊆ C, that the entire shortest path from u to v is contained in C, and hence d G[C] (u, v) = d G (u, v). Using Markov, the probability that the additive distortion by f C is too large is bounded by:
We conclude Pr [Ψ 2 | Ψ 1 ] ≥ 4 5 . Note that if Ψ 2 indeed occurred, then
Finally in step 3 we sample a padded decomposition C P of H C . As H C has treewidth π(Ω( 1 r ), r, n), the probability that u and v are clustered together is bounded by:
Note that we do not have matching lower bounds, so there is no provable separation.
Tree-Ordered Nets for Graphs of Bounded Tree-partition WidthIn this section, we show that graphs of bounded tree-partition width have small tree-ordered nets as claimed in Lemma 1, which we restate here for convenience.Lemma 1. Every weighted graph G = (V, E, w) with a tree-partition width tp admits a (poly(tp), 3, ∆)tree-ordered net, for every ∆ > 0.