Metric Decompositions of Path-Separable Graphs∗

arXiv:1504.07019v2 [cs.DS] 27 Sep 2016

Lior Kamma†
The Weizmann Institute

Robert Krauthgamer†
The Weizmann Institute

March 1, 2018

Abstract
A prominent tool in many problems involving metric spaces is a notion of randomized lowdiameter decomposition. Loosely speaking, β-decomposition refers to a probability distribution
over partitions of the metric into sets of low diameter, such that nearby points (parameterized by
β > 0) are likely to be “clustered” together. Applying this notion to the shortest-path metric in
edge-weighted graphs, it is known that n-vertex graphs admit an O(ln n)-padded decomposition
[Bar96], and that excluded-minor graphs admit O(1)-padded decomposition [KPR93, FT03,
AGG+ 14].
We design decompositions to the family of p-path-separable graphs, which was defined by
Abraham and Gavoille [AG06] and refers to graphs that admit vertex-separators consisting of
at most p shortest paths in the graph.
Our main result is that every p-path-separable n-vertex graph admits an O(ln(p ln n))decomposition, which refines the O(ln n) bound for general graphs, and provides new bounds for
families like bounded-treewidth graphs. Technically, our clustering process differs from previous
ones by working in (the shortest-path metric of) carefully chosen subgraphs.

1

Introduction

In recent decades, the problem of decomposing a metric space into low-diameter subspaces has become a key step in the solution for many problems, including metric embeddings (e.g. [Ass83,
Bar96, Rao99, GKL03, FRT04, KLMN05]), distance oracles and routing schemes design (e.g.
[AP90, DSB97, Tal04, CGMZ05, MN07]), graph sparsification (e.g. [EGK+ 14, KKN14]) and optimization problems, such as multicommodity cuts [KPR93, GVY96, LR99], 0-extension [CKR04]
and the traveling salesman problem [Tal04].
Following the recent literature, we focus on randomized decompositions, which loosely speaking
refers to a probability distribution over partitions of a metric space into sets (called clusters) of low
diameter, such that nearby points are more likely to be “clustered” together. The formal definitions
follows.
Let (X, d) be a metric space, and denote the ball of radius ̺ > 0 around x ∈ X by B(x, ̺) :=
{y ∈ X : d(x, y) ≤ ̺}. Let Π be a partition of X. Every S ∈ Π is called a cluster, and for every
x ∈ X, let Π(x) denote the unique cluster S ∈ Π such that x ∈ S. We will be using the following
definition of Abraham et al. [AGG+ 14].
∗

The final publication of the paper is available at Springer via http://dx.doi.org/10.1007/s00453-016-0213-0.
Work supported in part by a US-Israel BSF grant #2010418 and an Israel Science Foundation grant #897/13.
Email: {lior.kamma,robert.krauthgamer}@weizmann.ac.il
†

1

Definition 1.1. A metric space (X, d) is called β-decomposable for β > 0 if for every ∆ > 0 there
is a probability distribution µ over partitions of X, satisfying the following properties.
(a). Diameter Bound: For every Π ∈ supp(µ) and S ∈ Π, diam(S) ≤ ∆.
(b). Padding: For every x ∈ X and 0 ≤ γ ≤ 1/100,
Pr [B(x, γ∆) ⊆ Π(x) ] ≥ 2−βγ .

Π∼µ

A slightly different definition that is common in the literature under the name padded decomposition, see e.g. [KLMN05, LN04], is the special case of setting in (b) γ = 1/β, i.e., requiring that
for every x ∈ X, with probability at least 1/2 the entire ball B(x, ∆/β) is contained in a single
cluster of Π. Our results provide constructions that satisfy Definition 1.1, and thus immediately
apply also to the more common definition.
The metric spaces we study arise as shortest-path metrics in (certain) graphs. Specifically, given
G = (V, E, w) a connected graph with non-negative edge weights, let dG denote the shortest-path
metric induced on V by G. Denote by BG (u, ̺) the ball of radius ̺ > 0 around u ∈ V in the
metric space (V, dG ). We say that a graph G is β-decomposable if the metric space (V, dG ) is
β-decomposable.
Bartal [Bar96] proved that for every n-point metric space, β = O(log n), and that this bound
is tight for general metric spaces, thus motivating an extensive research on restricted families of
metric spaces. Notable progress has been made for families defined by topological restrictions, such
as shortest-path metrics in graphs excluding a fixed minor [KPR93, FT03, AGG+ 14] or boundedgenus graphs [LS10, AGG+ 14] and geometric restrictions, such as a bounded doubling dimension
[GKL03] or hyperbolic structure [KL06].
In this paper we consider metrics induced by graphs of bounded “path separability”, which is
a blend of topological and geometric restrictions, as defined below.
Shortest-Path Separators. Given a graph G = (V, E, w) and a set S ⊆ V , an S-flap is a
connected component of G[V \ S]. We say that S is a (balanced) vertex separator if every S-flap U
has size |U | ≤ |V |/2. Vertex separators are widely used in divide-and-conquer algorithms. Thorup
[Tho04] observed that every planar graph has a vertex separator composed of three shortest paths
1 , and used this property to design distance and reachability oracles for planar graphs. Abraham
and Gavoille [AG06] extended this notion and defined path separability. Intuitively, a graph is path
separable if it has a vertex separator composed of a few shortest-paths.
S
Notation 1.2. For sets X1 , . . . , Xm and S ⊆ [m], we denote XS := j∈S Xj .

Definition 1.3. [AG06] A graph G = (V, E, w) is called p-path separable for p ∈ N if there exists
S ⊂ V such that the following holds.
1. There exist P1 , . . . , Pm ⊆ V such that S = P[m] and every Pj is the union of pj shortest-paths
in Gj := G \ P[j−1] .
P
2.
j∈[m] pj ≤ p.

1

If we relax the balance constraint, and require that every S-flap U has size |U | ≤ 2|V |/3, then two shortest paths
suffice.

2

3. S is a vertex separator, and every S-flap is p-path-separable.
Abraham and Gavoille showed that for every graph H there is a number p = p(H) such that
every graph (V, E) that excludes H as a minor is p-path-separable under every edge weights w.
Diot and Gavoille [DG10] proved that every graph of treewidth t is ⌈(t − 1)/2⌉-path-separable with
every edge weights w.

1.1

Main Results

Theorem 1.4. Every p-path-separable graph (V, E, w) is O(ln(p ln |V |))-decomposable.
We further note that if, in addition, for every subgraph G′ of G, we can find a p-path-separator
in polynomial time then we can efficiently sample from the distribution guaranteed in Theorem 1.4.
Combining our theorem with the result of Diot and Gavoille [DG10] we get an upper bound for
bounded treewidth graphs.
Corollary 1.5. Every graph (V, E) of treewidth t with every edge weights w is O(ln(t ln |V |))decomposable.
Previously, no bound was known for p-path-separable graphs other than O(log |V |) due to Bartal
[Bar96]. For graphs of treewidth t the known upper bound is β = O(t) due to [AGG+ 14]. Our
decomposition provides a tradeoff between t and |V | and matches or improves all other bounds
when t ≥ ln ln |V |. It is conjectured that β = O(log t), which would be tight due to the lower
bound of Bartal [Bar96], and our result provide partial evidence in favor of this conjecture.
Many known results “interface” the metric only through decompositions, and thus plugging
in our decomposition bounds immediately yields new results for the aforementioned families of
metric spaces. For example, using a result from [KLMN05] we conclude that every n-vertex graph
of p
treewidth t (with every edge weights w) can be embedded √
in a Hilbert space with distortion
O( ln(t ln n) · ln n), which improves over the known bound O( t ln n) whenever t ≥ ln ln n.

1.2

Techniques

Carving Random Balls. A common approach for constructing a decomposition of a metric
(V, d) is to choose a sequence of centers c1 , . . . , ck ∈ V and corresponding radii R1 , . . . , Rk ≤ ∆/2,
where the choice of centers and/or radii may involve randomization, and then define
Sj = {v ∈ V : j = min{i ∈ [k] : d(v, ci ) ≤ Ri }} .
Clearly, each Sj has diameter at most ∆. This approach goes back to [Bar96], and has seen many
useful variations, for example, randomly ordering the centers [CKR04] or reducing the number of
centers [CKR04, GKL03]. As it turns out, it is enough to bound the number of centers locally.
More formally, for every v ∈ V we control the number of centers cj that threaten v in the sense
that Pr[d(v, cj ) < Rj + γ∆] > 0.
Carving Balls in Subgraphs. Inspired by ideas from [AGG+ 14], we introduce in this paper
another modification to the approach described theretofore. In addition to the above, for every
center cj we choose a corresponding subgraph Gj of G, such that cj ∈ V (Gj ), and define
Sj = {v ∈ V : j = min{i ∈ [k] : v ∈ V (Gi ) and dGi (v, ci ) ≤ Ri }} .
3

(a) Original unit weighted graph
G. When all outer-cycle vertices
are centers and all Ri ∈ [1, 2], vertex x is threatened by 8 centers.

(b) If balls are carved in this subgraph, x is threatened by only 5
centers.

Figure 1: When carving balls in a subgraph of G, the number of threateners to a vertex is smaller.
Choosing the subgraphs and centers carefully allows us to reduce the number of centers that threaten
a vertex v in two ways. The first and more obvious manner is by making sure that v ∈ V (Gi ) for
only a few indices i. The second aspect is a bit more subtle. Since distances are considered in
subgraphs of G, they might be larger than the corresponding distances in the original graph G, as
demonstrated in Figure 1, thus reducing the number of threateners of a vertex v.
Note that we need to ensure that {Sj }j∈[k] is indeed a partition of V , i.e. that the balls
{BGj (cj , Rj )}j∈[k] cover all of V .

1.3

Preliminaries

The Truncated Exponential Distribution. Define the truncated exponential with parameters
λ > 0 and 0 ≤ α < β < ∞, denoted Texp[α,β] (λ), to be distribution given by the probability density
function
1
e−x/λ
∀x ∈ [α, β] .
gλ,[α,β] (x) =
−α/λ
λ(e
− e−β/λ )

Note that this is the pdf of an exponential random variable with mean λ that is conditioned to be
in the range [α, β].
r-Nets. Given a metric space (V, d), an r-net of (V, d) is a set Y ⊆ V satisfying
1. Packing: For all distinct u, v ∈ Y we have d(u, v) > r.
2. Covering: For every v ∈ V , there is some u ∈ Y such that d(v, u) ≤ r.

2

Decomposing Path-Separable Graphs

In this section we prove Theorem 1.4. We present a procedure which, given a p-path-separable
graph G and a parameter ∆ > 0, produces a random partition Π of V . The algorithm works in
4

two phases. The first phase, presented in detail as Algorithm 1, constructs a sequence of centers.
This is performed deterministically and by recursion. The algorithm finds a path-separator S of G
and chooses a ∆/4-net on each path of the separator to serve as centers. For every center vertex,
the algorithm chooses a corresponding subgraph of G. The algorithm is then invoked recursively
on every S-flap. The second phase, presented in detail in Algorithm 2, samples random radii and
carves balls around the centers to obtain a partition of V . The radii are all sampled independently
at random from a truncated exponential distribution.
Denote by Ñ the union of all ∆/4-nets throughout the execution of Algorithm 1. Note that Ñ
is independent of the random radii (in fact, it is constructed deterministically). For sake of clarity,
for a center t ∈ Ñ let Gt , Rt , Bt be the subgraph, radius and ball corresponding to t respectively.
To prove that Algorithm 2 produces a partition of V , consider v ∈ V . During the execution of
Algorithm 1 there exists a subgraph G′ of G such that Algorithm 1 is (recursively) invoked on
G′ and v is in the path-separator S of G′ chosen by the algorithm (in fact, G′ is unique). Let
P be the path in S such that v ∈ P , let c ∈ P be the closest net point to v, and let G′′ be
the respective subgraph, then P ⊆ G′′ . By the definition of a net, dP (v, c) ≤ ∆/4, and
S therefore
v ∈ BP (c, ∆/4) ⊆ BG′′ (c, Rc ) (recall Rc ≥ ∆/4 is the radius chosen for c). Therefore S∈Π S = V ,
and Algorithm 2 indeed outputs a partition of V .
To prove the diameter requirement, let S ∈ Π, and let x, y ∈ S. Then there exists t ∈ Ñ such
that S ⊆ Bt ⊆ BG (t, 2∆/5) and therefore dG (x, y) < ∆.
Next, we prove the padding property of the decomposition. Let x ∈ V , and let 0 ≤ γ ≤ 1/80.
Denote B = BG (x, γ∆). We say that B is settled by t ∈ Ñ if Bt is the first ball (in order of
execution) to have non-empty intersection with B. Therefore, B 6⊆ Π(x) iff B is settled by t and
Bt ∩ B 6= B for some t ∈ Ñ . Let Ñx := {t ∈ Ñ : Pr[Bt ∩ B 6= ∅] > 0} be the set of centers that
threaten x. In order to bound the size of Ñx we consider the execution of Algorithm 1. Consider
′ and G′ , . . . , G′
first a single recursion level. Denote the current graph by G′ , and let P1′ , . . . , Pm
m
1
′
be as in Definition 1.3. Let j ∈ [m] and let P be some path in Pj . Consider the ∆/4-net N picked
by the algorithm. Since P is a shortest-path in G′j ,
{t ∈ N : Pr[Bt ∩ B 6= ∅] > 0} ≤ {t ∈ N : BG′j (t, 2∆/5) ∩ B 6= ∅} .
Let s, t ∈ N be such that BG′j (s, 2∆/5) ∩ B 6= ∅ and BG′j (t, 2∆/5) ∩ B 6= ∅. Since P is a shortest
path in G′j , we get that dP (s, t) ≤ 2∆/5 + 2γ∆ + 2∆/5 < ∆. Therefore
{t ∈ N : BG′j (t, 2∆/5) ∩ B 6= ∅} ≤

∆
=4.
∆/4

Since in every recursive call of Algorithm 1, the number of vertices in the input graph is reduced by
at least a factor of 1/2, the depth of the recursion is at most log n. Every recursion level contains
exactly one subgraph that contains x. Since the number of paths in each such subgraph is at most
p, we conclude that |Ñx | ≤ 4p log n. For simplicity, let us further assume this inequality holds with
equality, and denote k := 4p log n.
Let t1 , . . . , tk be the elements of Ñx in the order in which the algorithm considers them. Denote
by E the event that B 6⊆ Π(x), and for every i ∈ [k], denote by Ei the event that B was not settled
before ti was considered.


(1 − e−20γ ln k ) for all j ∈ [k].
Lemma 2.1. Pr[E | Ej ] ≤ 1 + kk−j+1
3/2 −1
5

Input: A p-path-separable graph G and a parameter ∆.
Output: A sequence (c1 , G1 ), (c2 , G2 ), . . ..
1: let P1 , . . . , Pm , G1 , . . . , Gm be as in Definition 1.3.
2: for j = 1 to m do
3:
for all paths P ∈ Pj do
4:
let (c1 , c2 , . . .) be a ∆/4-net of (P, dG |P ) in an arbitrary order.
5:
let Nj be the sequence (c1 , Gj ), (c2 , Gj ), . . ..
6: let N be the concatenation of N1 , N2 , . . . , Nm in that order.
7: for all connected components G′ of G \ P[m] do
8:
invoke Choose-Centers(G′ , ∆) and append the output sequence to N .
9: return N .
Algorithm 1: Choose-Centers(G, ∆)
Input: A p-path-separable graph G and a parameter ∆.
Output: A partition Π of V .
1: let (c1 , G1 ), (c2 , G2 ), . . . be the sequence returned by Choose-Centers(G, ∆).
∆
2: let λ ← 10 ln(9p
log n) .
3: let Π ← ∅.
4: for all j ≥ 1 do
5:
choose Rj ∼ Texp[∆/4,2∆/5] (λ) independently at random.

S
6:
let Sj ← BGj (cj , Rj ) \
S∈Π S .
7:
let Π ← Π ∪ {Sj }.
8: return Π \ {∅}.
Algorithm 2: Decomposing Path-Separable Graphs

Proof. Consider some j ∈ [k]. Conditioned on Ej , there are three possible outcomes to the jth
round. Either B was not settled also in the jth round, and then (for j ≤ k − 1) the final status
of B is left to the following rounds, or B was settled in the jth round, and in that case, either
B 6⊆ Π(x), (and thus E occurred), or B ⊆ Π(x). The ”bad” event E can therefore only occur (either
in the jth round or some time in the future) if either j ≤ k − 1 and Rtj < dG (x, tj ) − γ∆ or if
Rtj − dG (x, tj ) ≤ γ∆.
Denote a = max{∆/4, d(x, tj ) − γ∆}, b = min{d(x, tj ) + γ∆, 2∆/5}, then
Z b


1
e−x/λ dx
Pr Rtj − dG (x, tj ) ≤ γ∆ =
−10/4
−20/5 )
λ(k
−
k
a
∆/4

Since b − a ≤ 2γ∆, then 1 − e−
Pr



b−a
λ

a−∆/4
b−a
e− λ
= −10/4
(1 − e− λ ) · e− λ .
−20/5
k
−k

≤ 1 − e−20γ ln k . Substituting e−


Rtj − dG (x, tj ) ≤ γ∆ ≤

Similarly we get that

Pr[Rtj < dG (x, tj ) − γ∆] ≤

∆/4
λ

a−∆/4
k3/2
−20γ ln k
− λ
(1
−
e
)
·
e
.
k3/2 − 1

a−∆/4
k3/2
(1 − e− λ ) .
3/2
k −1

6

= k−2.5 we get that
(1)

(2)

The proof proceeds by induction over j = k, k − 1, . . . , 1. As previously noted,


Pr[E | Ek ] ≤ Pr Rtk − dG (x, tk ) ≤ γ∆ .
Plugging (1) we get that

a−∆/4
k3/2
Pr[E | Ek ] ≤ 3/2
(1 − e−20γ ln k ) · e− λ ≤
k −1



1
1 + 3/2
k −1



(1 − e−20γ ln k ) ,

where the last inequality follows from the fact that a ≥ ∆/4. Next, let j ∈ [k − 1]. Then as
previously explained,
h
i
Pr[E | Ej ] = Pr Rtj − dG (x, tj ) ≤ γ∆ + Pr[Rtj < dG (x, tj ) − γ∆] · Pr[E | Ej+1 ] .
(3)

By plugging (1) and (2) into (3) and using the induction hypothesis, we get that
k3/2
k3/2 − 1



k−j
(1 − e−20γ ln k )
) 1 + 3/2
k −1
!
a−∆/4
k3/2
(1 − e− λ )(k − j)
= 3/2
1+
(1 − e−20γ ln k )
k −1
k3/2 − 1


k−j +1
(1 − e−20γ ln k ) ,
≤ 1 + 3/2
k −1

Pr[E | Ej ] ≤



e−

a−∆/4
λ

+ (1 − e−

a−∆/4
λ

which proves Lemma 2.1.
To complete the proof of Theorem 1.4, note that since γ ≤ 1/80 and for k ≥ 3,


k
Pr[E] = Pr[E | E1 ] ≤ 1 + 3/2
(1 − e−20γ ln k )
k −1


≤ 1 + e−20γ ln k (1 − e−20γ ln k ) = (1 − e−40γ ln k ) .

By setting β = 40lnln2 k = O(ln(p ln n)) we get that Pr[B(x, γ∆) ⊆ Π(x) ] ≥ 2−βγ , thus proving the
last part of Theorem 1.4.
Acknowledgements. The authors thank Ittai Abraham, Alex Andoni, and Kunal Talwar for
useful discussions during preliminary stages of this work.

References
[AG06]

I. Abraham and C. Gavoille. Object location using path separators. In Proceedings
of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing,
PODC ’06, pages 188–197, 2006.

[AGG+ 14] I. Abraham, C. Gavoille, A. Gupta, O. Neiman, and K. Talwar. Cops, robbers, and
threatening skeletons: Padded decomposition for minor-free graphs. In Proceedings of
the 46th Annual ACM Symposium on Theory of Computing, STOC ’14, pages 79–88,
New York, NY, USA, 2014. ACM.
7

[AP90]

B. Awerbuch and D. Peleg. Sparse partitions. In 31st Annual IEEE Symposium on
Foundations of Computer Science, pages 503–513, 1990.

[Ass83]

P. Assouad. Plongements lipschitziens dans Rn . Bull. Soc. Math. France, 111(4):429–
448, 1983.

[Bar96]

Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications.
In 37th Annual Symposium on Foundations of Computer Science, pages 184–193. IEEE,
1996.

[CGMZ05] H. T.-H. Chan, A. Gupta, B. M. Maggs, and S. Zhou. On hierarchical routing in
doubling metrics. In 16th Annual ACM-SIAM Symposium on Discrete Algorithms,
pages 762–771. SIAM, 2005.
[CKR04]

G. Calinescu, H. J. Karloff, and Y. Rabani. Approximation algorithms for the 0extension problem. SIAM J. Comput., 34(2):358–372, 2004.

[DG10]

E. Diot and C. Gavoille. Path separability of graphs. In Frontiers in Algorithmics, 4th
International Workshop, FAW, pages 262–273, 2010.

[DSB97]

B. Das, R. Sivakumar, and V. Bharghavan. Routing in ad hoc networks using a spine.
In Sixth International Conference on Computer Communications and Networks., pages
1–20, 1997.

[EGK+ 14] M. Englert, A. Gupta, R. Krauthgamer, H. Rcke, I. Talgam-Cohen, and K. Talwar.
Vertex sparsifiers: New results from old techniques. SIAM Journal on Computing,
43(4):1239–1262, 2014.
[FRT04]

J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary
metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485–497, 2004.

[FT03]

J. Fakcharoenphol and K. Talwar. Improved decompositions of graphs with forbidden
minors. In 6th International workshop on Approximation algorithms for combinatorial
optimization, pages 36–46, 2003.

[GKL03]

A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and lowdistortion embeddings. In 44th Annual IEEE Symposium on Foundations of Computer
Science, pages 534–543, October 2003.

[GVY96]

N. Garg, V. V. Vazirani, and M. Yannakakis. Approximate max-flow min-(multi)cut
theorems and their applications. SIAM Journal on Computing, 25(2):235–251, 1996.

[KKN14]

L. Kamma, R. Krauthgamer, and H. L. Nguyen. Cutting corners cheaply, or how to remove steiner points. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium
on Discrete Algorithms, pages 1029–1040, 2014.

[KL06]

R. Krauthgamer and J. R. Lee. Algorithms on negatively curved spaces. In 47th Annual
IEEE Symposium on Foundations of Computer Science, pages 119–132. IEEE, 2006.

8

[KLMN05] R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor. Measured descent: A new
embedding method for finite metrics. Geometric And Functional Analysis, 15(4):839–
858, 2005.
[KPR93]

P. Klein, S. A. Plotkin, and S. Rao. Excluded minors, network decomposition, and
multicommodity flow. In 25th Annual ACM Symposium on Theory of Computing, pages
682–690, May 1993.

[LN04]

J. R. Lee and A. Naor. Metric decomposition, smooth measures, and clustering,
2004. Unpublished manuscript. Available from: http://www.cims.nyu.edu/~naor/
homepagefiles/cluster.pdf.

[LR99]

T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in
designing approximation algorithms. J. ACM, 46(6):787–832, 1999.

[LS10]

J. R. Lee and A. Sidiropoulos. Genus and the geometry of the cut graph. In Proceedings
of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’10,
pages 193–201. Society for Industrial and Applied Mathematics, 2010.

[MN07]

M. Mendel and A. Naor. Ramsey partitions and proximity data structures. J. Eur.
Math. Soc., 9(2):253–275, 2007.

[Rao99]

S. Rao. Small distortion and volume preserving embeddings for planar and Euclidean
metrics. In Proceedings of the 15th Annual Symposium on Computational Geometry,
pages 300–306. ACM, 1999.

[Tal04]

K. Talwar. Bypassing the embedding: Algorithms for low dimensional metrics. In
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 281–
290, 2004.

[Tho04]

M. Thorup. Compact oracles for reachability and approximate distances in planar
digraphs. J. ACM, 51(6), 2004.

9

