Ramsey Spanning Trees and their Applications
Ittai Abraham Shiri Chechik Michael Elkin Arnold Filtser Ofer Neiman
cs.DS

1]Ittai Abraham
2]Shiri Chechik
3]Michael Elkin
3]Arnold Filtser
3]Ofer Neiman

[1]VMWare. Email: 
[2]Tel-Aviv University. Email: 
[3]Ben-Gurion University of the Negev. Email: 




Ramsey Spanning Trees and their Applications
    [
    
============================================


	
The metric Ramsey problem asks for the largest subset S of a metric space that can be embedded into an ultrametric (more generally into a Hilbert space) with a given distortion. Study of this problem was motivated as a non-linear version of Dvoretzky theorem. Mendel and Naor <cit.> devised the so called Ramsey Partitions to address this problem, and showed the algorithmic applications of their techniques to approximate distance oracles and ranking problems.



	
In this paper we study the natural extension of the metric Ramsey problem to graphs, and introduce the notion of Ramsey Spanning Trees. We ask for the largest subset S⊆ V of a given graph G=(V,E), such that there exists a spanning tree of G that has small stretch for S. Applied iteratively, this  provides a small collection of spanning trees, such that each vertex has a tree providing low stretch paths to all other vertices. The union of these trees  serves as a special type of spanner, a tree-padding spanner. We  use this spanner to devise the first compact stateless routing scheme with O(1) routing decision time, and  labels which are much shorter than in all currently existing schemes.
	
	
We first revisit the metric Ramsey problem, and provide a new deterministic construction. We prove that for every k, any n-point metric space has a subset S of size at least n^1-1/k which embeds into an ultrametric with distortion 8k. This results improves the best previous result of Mendel and Naor that obtained distortion 128k and required randomization. In addition, it provides the state-of-the-art deterministic construction of a distance oracle.
Building on this result, we prove that for every k, any n-vertex graph G=(V,E) has a subset S of size at least n^1-1/k, and a spanning tree of G, that has stretch O(k loglog n) between any point in S and any point in V.



empty





§ INTRODUCTION

Inspired by the algorithmic success of Ramsey Type Theorems for metric spaces, in this paper we study an analogue Ramsey Type Theorem in a graph setting. The classical Ramsey problem for metric spaces was introduced in <cit.>, and is concerned with finding "nice" structures in arbitrary metric spaces. Following <cit.>, <cit.> showed that every n-point metric (X,d) has a subset M⊆ X of size at least n^1-1/k that embeds into an ultrametric (and thus also into Hilbert space) with distortion at most O(k), for a parameter k≥ 1. In fact, they construct an ultrametric on X which has O(k) distortion for any pair in M× X. Additionally, <cit.> demonstrated the applicability of their techniques, which they denoted Ramsey Partitions, to approximate distance oracles and ranking problems.

We introduce a new notion that we call Ramsey Spanning Trees, which is a natural extension of the metric  Ramsey problem to graphs. We show that every graph G=(V,E) with n vertices admits a subset M⊆ V of size at least n^1-1/k, such that there exists a spanning tree of G that has stretch O(kloglog n) on all pairs in M× V. (The extra factor of loglog n in the stretch comes from the state-of-the-art result of O(log nloglog n) for low stretch spanning trees <cit.>. It is quite plausible that if that result is improved to the optimal O(log n), then the stretch in our result would be only O(k).)

By applying this result iteratively, we can obtain a small collection of trees so that each vertex has small stretch to all other vertices in at least one of the trees. Let (u,v,G) denote the shortest path distance in the graph G between the vertices u,v∈ V, then our main result is the following.

Let G=(V,E) be a weighted graph on n vertices, and fix a parameter k≥ 1. There is a polynomial time deterministic algorithm that finds a collection T of k· n^1/k spanning trees of G, and a mapping :V→ T, such that for every u,v∈ V it holds that (v,u,(v))≤ O(kloglog n)·(v,u,G).


A spanner H with stretch t for a graph G, is a sparse spanning subgraph satisfying (v,u,H)≤ t·(v,u,G).
Spanners are a fundamental metric and graph-theoretic constructions; they are very well-studied <cit.>, and have numerous applications <cit.>.
thm:main-col can be viewed as providing a spanner which is the union of k· n^1/k spanning trees, such that every vertex has a tree with low stretch paths to all other vertices.
We call such a spanner a tree-padding spanner of order k · n^1/k. To the best of our knowledge, no previous construction of spanners can be viewed as a tree-padding spanner of order o(n).
 Until now even the following weaker question was open: does there exist a spanner which is a union  of a sublinear in n number of trees, such that every pair of vertices has a low stretch path in one of these trees.

Having a single tree that provides good stretch for any pair containing the vertex v, suggest that routing messages to or from v could be done on this one tree. Our main application of Ramsey spanning trees is a compact routing scheme that has constant routing decision time and improved label size, see sec:apps for more details.




  
Deterministic Ramsey Partitions.
As a first step towards our main result, which is of interest in its own right, we provide a new deterministic Ramsey ultrametric construction. In particular, we show a polynomial time deterministic algorithm, that given an n-point metric space (X,d) and a parameter k≥ 1, finds a set M⊆ X of size at least n^1-1/k and an ultrametric (M,ρ) with distortion at most 8k-2. That is, for each v,u∈ M,

    d(v,u) ≤ρ(v,u) ≤ (8k-2) · d(v,u) .

Even though our construction is deterministic, it has smaller distortion than all previous constructions.
The first result of this flavor was by Mendel and Naor <cit.>, obtaining distortion of 128k.
Belloch et. al <cit.> 
showed that the (randomized) algorithm of <cit.> constructs an ultrametric with distortion 18.5k (they also provided a near-linear time implementation of it).
Naor and Tao  <cit.> declared that 16k is obtainable but that a Ramsey partition with distortion better than 16k-2 seems not to be possible with their current techniques. Moreover, <cit.> mention as a drawback that their solution is randomized (while <cit.> is deterministic).

An application of our improved deterministic Ramsey ultrametric construction is a new distance oracle that has the best space-stretch-query time tradeoff among deterministic distance oracles. See sec:apps below.




  
Techniques.
Our construction of Ramsey ultrametrics uses the by-now-standard deterministic ball growing approach, e.g. <cit.>. 
In this paper we provide tighter and more parameterized analysis of these multi-scale deterministic region growing techniques. Our improved analysis of the deterministic ball growing technique of <cit.> obtains a similar type of improvement as the one obtained by the analysis of Mendel and Naor <cit.> on the randomized partition technique of <cit.>.

Our construction of Ramsey spanning trees is based on combining ideas from our Ramsey ultrametric construction, with the Petal Decomposition framework of <cit.>. The optimal multi-scale partitions of <cit.> cannot be used in this petal decomposition framework, so we must revert to partitions based on <cit.>, which induce an additional factor of O(loglog n) to the stretch. In addition, the refined properties required by the Ramsey partition make it very sensitive to constant factors (these constants can be ignored in the <cit.> analysis of the average stretch, say).
In order to alleviate this issue, we consider two possible region growing schemes, and choose between them according to the densities of points that can still be included in M. One of these schemes is a standard one, while the other grows the region "backwards", in a sense that it charges the remaining graph, rather than the cluster being created, for the cost of making a cut. See subsec:createPetal for more details.








 §.§ Applications





  
Distance Oracles. A distance oracle is a succinct data structure that (approximately) answers distance queries. A landmark result of <cit.> states that any metric (or graph) with n points has a distance oracle of size O(k· n^1+1/k),[We measure size in machine words, each words is Θ(log n) bits.] that can report any distance in O(k) time with stretch at most 2k-1. A deterministic variant with the same parameters was given by <cit.>, and this was the state-of-the-art for deterministic constructions. The oracle of <cit.> has improved size O(n^1+1/k) and O(1) query time, but larger stretch 128k. This oracle was key for subsequent improvements by <cit.>, the latter gave a randomized construction of an oracle with size O(n^1+1/k), query time O(1) and stretch 2k-1 (which is asymptotically optimal assuming Erdos' girth conjecture).

Similarly to <cit.>, our deterministic construction of Ramsey ultrametrics can provide a deterministic construction of an approximate distance oracle.


For any metric space on n points, and any k>1, 0<ϵ<1, there is an efficient deterministic construction of a distance oracle of size O(n^1+1/k), that has stretch 8 (1+)k and query time O(1/).


This is the first deterministic construction of an approximate distance oracle with constant query time and small size O(n^1+1/k).

Moreover, our oracle is an essential ingredient towards de-randomizing the recent distance oracles improvements <cit.>.
Specifically, if we construct <cit.> by replacing
the distance oracle of Mendel and Naor <cit.> by our deterministic version, and replacing the distance oracle of
Thorup and Zwick <cit.> by the deterministic version of Roditty, Thorup, and Zwick <cit.>,
we immediately get a deterministic distance oracle of O(k · n^1+1/k) size, 2k-1 stretch and O(1) query time.
This is a strict improvement over  <cit.>.
In addition, our oracle can be viewed as a first step towards de-randomizing the <cit.> oracle.
A summary of all the previous and current results can be found at tab:DistanceOracle in sec:table.



  
Routing with Short Labels and Constant Decision Time.
A routing scheme in a network is a mechanism that allows packets to be delivered from any node to any other node. The network is represented as a weighted undirected graph, and each node can forward incoming data by using local information stored at the node, often called a routing table, and the (short) packet's header. The routing scheme has two main phases: in the preprocessing phase, each node is assigned a routing table and a short label. In the routing phase, each node receiving a packet should make a local decision, based on its own routing table and the packet's header (which may contain the label of the destination, or a part of it), where to send the packet.
The routing decision time is the time required for a node to make this local decision.
The stretch of a routing scheme is the worst ratio between the length of a path on which a packet is routed, to the shortest possible path. A routing scheme is called stateless if the routing decision does not depend on the path traversed so far.

The classical routing scheme of <cit.>, for a graph on n vertices and integer parameters k,b> 1, provides a scheme with routing tables of size O(k· b· n^1/k), labels of size (1+o(1))klog_bn, stretch 4k-5, and decision time O(1) (but the initial decision time is O(k)). The stretch was improved recently to roughly 3.68k by <cit.>, using a similar scheme as <cit.>. With thm:main-col, we devise a stateless compact routing scheme with very short labels, of size only (1+o(1))log_bn, and with constant decision time, while the stretch increases to O(kloglog n) (and with the same table size as <cit.>).

We wish to point out that our construction of a routing scheme is simpler in some sense that those of <cit.>. In both constructions there is a collection of trees built in the preprocessing phase, such that every pair of vertices has a tree that guarantees small stretch. Routing is then done in that tree. In our construction there are few trees, so every vertex can store information about all of them, and in addition, every vertex v∈ V knows its home tree, and routing towards v from any other vertex on the tree (v) has small stretch. In particular, the header in our construction consists of only the label of the destination. In the <cit.> scheme, however, there are n trees, and a certain process is used to find the appropriate tree to route on, which increases the initial decision time, and also some information must be added to the header of the message after the tree is found. Finally, our routing scheme is stateless, as opposed to <cit.>. (We remark that using ideas from <cit.>, one can devise a stateless routing scheme based on <cit.>, but this scheme seems to suffer from larger header and decision time at each node.)



	Given a weighted graph G=(V,E) on n vertices and integer parameters k,b> 1, there is a stateless routing scheme with stretch O(kloglog n) that has routing tables of size O(k· b· n^1/k) and labels of size (1+o(1))log_bn. The decision time in each vertex is O(1).

Observe that choosing parameters 2k and b=n^1/(2k) for thm:route yields a routing scheme with stretch O(kloglog n) that has tables of size O(k· n^1/k) and labels of size only O(k). Another interesting choice of parameters is b=2 and k=100log n/loglog n, this provides a scheme with stretch O(log n) that has tables of size O(log^1.01n) and labels of size O(log n). Compare this to the <cit.> scheme, which for stretch O(log n) has tables of size O(log n) and labels of size O(log^2 n).





 §.§ Organization

In sec:Ramsey-Partitions we present our deterministic Ramsey partitions, that are used for Ramsey ultrametrics and distance oracles. In sec:Ramsey-spanning we show the Ramsey spanning trees, and the application to routing. Each section can be read independently.



§ PRELIMINARIES

Let G=(V,E) be a weighted undirected graph. We assume that the minimal weight of an edge is 1. For any Y⊆ V and x,y∈ Y, denote by (x,y,Y) the shortest path distance in G[Y] (the graph induced on Y).
For v∈ Y and r≥ 0 let
B(v,r,Y)={u∈ Y|(v,u,Y)≤ r}, when Y=V we simply write B(v,r). We may sometimes abuse notation and not distinguish between a set of vertices and the graph induced by them.

An ultrametric (Z,d) is a metric space satisfying a
strong form of the triangle inequality, that is, for all x,y,z∈ Z,
d(x,z)≤max{ d(x,y),d(y,z)}. The following definition
is known to be an equivalent one (see <cit.>).

	An ultrametric is a metric space (Z,d) whose elements
	are the leaves of a rooted labeled tree T. Each z∈ T is associated
	with a label ℓ(z)≥0 such that if q∈ T is a
	descendant of z then ℓ(q)≤ℓ(z)
	and ℓ(q)=0 iff q is a leaf. The distance between
	leaves z,q∈ Z is defined as d_T(z,q)=ℓ((z,q))
	where (z,q) is the least common ancestor of
	z and q in T.





§ RAMSEY PARTITIONS


Consider an undirected weighted graph G=(V,E), and a parameter k≥ 1.
Let D be the diameter of the graph and let = ⌈log(D+1)⌉.
Let ρ_i = 2^i/(4k).
We start by presenting a construction for a collection S of cluster partial partitions X_i satisfying the following key properties.


[(G,U,k)-Fully Padded Strong Diameter Hierarchical Partial Partition]
	Given a graph G=(V,E), an index k and a set of nodes U⊆ V, a (G,U,k)-Fully Padded Strong Diameter Hierarchical Partial Partition () is a collection X_i
	of subsets of nodes X ∈ X_i with a center r(X) for 0 ≤ i ≤ with the following properties.
	
	
	
		
  * (i)
		For every 0 ≤ i ≤,
		the subsets in X_i are disjoint, namely, for every two different subsets X,X' ∈ X_i, X ∩ X' = ∅.
		
  * (ii)
		For every 0 ≤ i < and
		every subset X ∈ X_i, there exists a subset X' ∈ X_i+1 such that X ⊆ X'.
		
  * (iii)
		For every 0 ≤ i ≤ and
		every X∈ X_i and every v∈ X, (v,r(X),X) < 2^i.
		
  * (iv)
		There exists a set V̂⊆ U such that |V̂| ≥ |U|^1-1/k and
		for every v ∈V̂ and every i, there exists a subset X∈ X_i
		such that B(v,ρ_i) ⊆ X.
	
	


For a node v and index i, we say that v is i-padded in S, if there exists a subset X ∈ X_i such that
B(v,ρ_i) ⊆ X. We would like to maximize the number of nodes that are padded on all levels.




  
Fully Padded Strong Diameter Hierarchical Partial Partition Construction:

Let us now turn to the construction of the collection S of cluster partial partitions X_i given a set U.

In the beginning of the algorithm, all nodes in U are set as marked. The algorithm iteratively unmarks some of the nodes.
The nodes that will remain marked by the end of the process are the nodes that are padded on all levels.
For a given graph H, let B_M(v,d,H) (M stands for marked) be the set of marked nodes at distance at most d from v in H.

For a subgraph G' and a node v ∈ V(G'),
let Z_i(v,G') = |B_M(v,2^i,G')|/|B_M(v,2^i-1,G')|.
The construction given in alg-strong-ramsey.




Let X(v) be a set constructed in line:X(v)def of alg-strong-ramsey, when partitioning X∈ X_i+1.
We say that X is the parent of X(v).
Let H(X(v)) denote the graph in alg-strong-ramsey just before X(v) was constructed (note that this is a graph induced on a subset of X).
We say that B(v,2^i-1 + 2j(v) ρ_i, H(X(v))) is the interior part of X(v)
.
We also say that the set B_M(v,2^i-1 + 2(j(v)+1) ρ_i, H(X(v))) is the responsibility set of X(v), hereafter referred to as (X(v)).
Note that every node u that is still marked after the processing of X is completed, belongs to exactly one set (X(v)) for X(v) ∈ X_i.

We now define by induction the term i-surviving for 0≤ i ≤:
All nodes in U are -surviving.
We say that a node is i-surviving if it is (i+1)-surviving and it belongs to the interior part of some subset in X_i.
Our goal in the analysis is to show that many nodes are 0-surviving, which is exactly the set V̂.
For a subset X ∈ X_i, let (X) be the set of nodes in X that are 0-surviving.
We now turn to the analysis.



The next auxiliary claim helps in showing that property (iii) holds.

	
	Consider a subset X ∈ X_i centered at some node v = r(X).
	The index j(v) defined in line:RG of alg-strong-ramsey, satisfies j(v) ≤ k-1


	Seeking contradiction, assume that for every 0≤ j'≤ k-1, |B_M(v,2^i-1 + 2(j'+1) ρ_i, H(X))| > |B_M(v,2^i-1 + 2j' ρ_i, H(X))| · |Z_i(v,H(X))|^1/k. Then applying this for j'=k-1,k-2,…,0 we get
	
    |B_M(v,2^i,H(X))|     =|B_M(v,2^i-1+2kρ_i,H(X))|
        >|B_M(v,2^i-1+2(k-1)ρ_i,H(X))|·|Z_i(v,H(X))|^1/k
         > …>|B_M(v,2^i-1,H(X))|·|Z_i(v,H(X))|^k/k
        =|B_M(v,2^i,H(X))| ,

	a contradiction.



The next lemma shows that the collection S satisfies properties (i)-(iii).



	
	S satisfy properties (i)-(iii).


	Property (i) is straightforward from line:RemoveX(v).
	Property (ii) holds as each X(v) is selected from the graph H(X(v)), which is an induced graph over a subset of X (the parent of X(v)). Finally, property (iii) follows from
	claim:j-v, as the radius of X(v) is bounded by 2^i-1+(2(k-1)+1)ρ_i<2^i-1+2kρ_i=2^i.


Next we argue that if a vertex is 0-surviving, then it is padded in all the levels.

	Suppose x∈(V), then x is padded in all the levels.


	Fix some x∈(V). To prove that x is i-padded, we assume inductively that x is j-padded for all i< j≤ (the base case i= follows as B(x,ρ_)⊆ V).
	Let X∈𝒳_i+1 such that x∈ X. Set B=B(x,ρ_i). By the induction hypothesis B⊆ B(x,ρ_i+1)⊆ X.
	Let X(v)∈𝒳_i such that x∈ X(v).
	
First we argue that B⊆ H(X(v)). Seeking contradiction, let X(v')∈𝒳_i be the first created cluster such that there is u∈ B∩ X(v').
	By the minimality of v', it follows that B⊆ H(X(v')). Thus (v,u,H(X(v')))=(v,u,G)≤ρ_i.
	Let j(v') the index chosen in line:RG of alg-strong-ramsey. Then X(v')=B(v',2^i-1+(2j(v')+1)ρ_i,H(X(v'))). Using the triangle inequality (x,v',H(X(v')))≤  2^i-1+(2j(v')+2)ρ_i. Therefore x was unmarked in line:unMark, a contradiction.
	
	It remains to show that B⊆ X(v). Set j(v) s.t. X(v)=B(v,2^i-1+(2j(v)+1)ρ_i,H(X(v))). As x is part of the interior of X(v), it holds that
	(x,v,H(X(v)))≤ 2^i-1+2j(v)ρ_i. Therefore B⊆ B(v,2^i-1+(2j(v)+1)ρ_i,H(X(v)))=X(v).



The next lemma bounds the number of surviving nodes.

	For every index i and every subset X = X(v) ∈ X_i, the 0-surviving nodes satisfy
	|(X)|≥|M_i(X)|/|B_M(r(X),2^i-1,H(X))|^1/k


	We prove the lemma by induction on i.
	Consider first the base case where X = X(v) ∈ X_0.
	As the subsets in X_0 contain a single node (their radius is less than 1), it holds that	
	|(X)|=1= 1/1=|M_0(X)|/|B_M(r(X),1/2,H(X))|^1/k (observe that each cluster in X_i has at least 1 marked node, for all 0≤ i≤).
	Assume the claim holds for every subset X' ∈ X_i, and consider X ∈ X_i+1.
	Let v =r(X).
	Consider the children X_1,...,X_j' of X.
	For every 1≤ h ≤ j', set v_h=r(X_h).
	
	Note that by definition of j(v_h) in line:RG of alg-strong-ramsey and by the construction of X_h in line:X(v)def, we have
	that |M_i(X_h)|≥ |(X_h)|/Z_i(v_h,H(X_h))^1/k.
	Moreover, by the induction hypothesis we have that
	|(X_h)|≥|M_i(X_h)|/|B_M(v_h,2^i-1,H(X_h))|^1/k for every h.
	
	
	We claim that |B_M(v,2^i,H(X))|  ≥ |B_M(v_h,2^i,H(X_h))| for every 1≤ h ≤ j'.
	To see this, note that v is the node with maximal |B_M(v,2^i,H(X))|, hence |B_M(v,2^i,H(X))| ≥ |B_M(v_h,2^i,H(X))|.
	In addition, note that H(X_h) ⊆ H(X), hence
	|B_M(v_h,2^i,H(X))| ≥  |B_M(v_h,2^i,H(X_h))|.
	It follows that |B_M(v,2^i,H(X))|  ≥ |B_M(v_h,2^i,H(X_h))|.
	
	Therefore the number of 0-surviving nodes in X_h is at least
	
	
    |(X_h)|
    		   ≥   |M_i(X_h)|/|B_M(v_h,2^i-1,H(X_h))|^1/k≥|(X_h)|/|Z_i(v_h,H(X_h))|^1/k/|B_M(v_h,2^i-1,H(X_h))|^1/k
       =   |(X_h)|/|B_M(v_h,2^i,H(X_h))|^1/k·|B_M(v_h,2^i-1,H(X_h))|^1/k/|B_M(v_h,2^i-1,H(X_h))|^1/k
       ≥   |(X_h)|/|B_M(v,2^i,H(X))|^1/k ,

	we conclude that
	
    |(X)|=∑_h=1^j'|(X_h)|≥∑_h=1^j'|(X_h)|/|B_M(v,2^i,H(X))|^1/k=|M_i+1(X)|/|B_M(v,2^i,H(X))|^1/k .



Using lem:frac-survival on V with i=, combined with lem:SurPaddedAll, implies property (iv).


	The number of marked nodes  V̂ by the end of alg-strong-ramsey is at least |U|^1-1/k.
	Moreover, for every v ∈V̂ and every i, there exists a subset X∈ X_i
	such that B(v,ρ_i) ⊆ X.




	For every n-point metric space and k≥ 1, there exists a subset of size n^1-1/k that can be embedded into an ultrametric with distortion 8k-2.


The hierarchical partial partition S={ X_i} naturally induce an ultrametric on V̂. The singleton sets of V̂ are the leaves, and each X∈ X_i for 0≤ i< will be a tree-node which is connected to its parent. Each set in X_i for i≥ 1 will receive the label 2^i+1(1-1/(4k)), while the leaves in X_0 receive the label 0 (recall def:ultra).

	Consider two nodes u,v ∈V̂. Assume the least common ancestor of u,v is X∈ X_i, for some 1≤ i≤.
	Hence (u,v,G) ≤ 2 · (2^i -  2^i/4k) (they are both in the interior of X - a ball with radius ≤ 2^i-2ρ_i). Since this is the label of X, we conclude that distances in the ultrametric are no smaller than those in G.
	
	Next we argue that distances increase by a factor of at most 8k-2. Consider any u,v as above, and seeking a contradiction, assume that (v,u,G)<2^i+1(1-1/(4k))/8k-2 = ρ_i. Let P be the shortest path from v to u in G.	As v was padded in X, necessarily P⊆ X. Consider the first time a vertex z∈ P was added to a cluster X'∈𝒳_i-1, then P⊆ H(X'). Let j be such that X'= B(r(X'),2^i-2 + (2j+1)ρ_i-1 , H(X')).
Since P is a shortest path, at least one of u,v must be within distance less than ρ_i/2=ρ_i-1 from z, w.l.o.g assume (v,z,H(X'))≤ρ_i-1. This implies that v∈(X')=B(r(X'),2^i-2 + (2j+2)ρ_i-1 , H(X')), and as v is marked it must lie in the interior of X', which is B(r(X'),2^i-2 + 2jρ_i-1 , H(X')). But then the triangle inequality yields that u∈(X')∖ X', which is a contradiction to the fact that u∈V̂.






 §.§ Distance Oracle

We show a distance oracle with O(n^1+1/k) size, (8+)k worst case stretch and O(1/) query time (which is O(1) for any fixed epsilon).

For simplicity we start by showing a construction with O(k · n^1+1/k) size, 16k stretch and O(1) query time. We will later see how to reduce the size and stretch.
Let D be the diameter of the graph.



Our distance oracle is constructed as follows.
enumerate

  * Set U  V.

  * Construct the collection of cluster-partial-partitions S(U) on the graph G and the set U.
Remove from U the set of nodes V̂ that were padded in all levels in S(U).
Continue this process as long as U ≠∅.

  * Let M be the set of all collections S(U) that were constructed by this process.

  * For every S∈ M construct a cluster X( S) as follows.

  * Let S = { X_0,..., X_}.
All nodes V are the leaves (recall that only nodes in V̂ are in X_0).
For every index i and every set X ∈ X_i, add an intermediate node. Connect X to its parent set.
Connect every node v ∈ V to the set X ∈ X_i of minimal i such that v ∈ X.
This completes the construction of X( S).

  * In addition, we preprocess X( S) so that least common ancestor (LCA) queries could be done in constant time.
In order to do that we invoke any scheme that takes a tree and preprocess it in linear time so that LCA queries can be answered in constant time (see <cit.>).

  * Finally, note that for every node v there exists a collection S∈ M, where v is padded in all levels.
Denote this collection by (v).
enumerate


The query phase is done as follows.
Given two nodes s and t.
Let S = (s) and let S = { X_i | 1≤ i ≤}.
Find the least common ancestor of s and t in X( S) and let i be its level.
Namely, let μ∈ X( S) be the least common ancestor of s and t and let X be the cluster μ represents,
the index i is the index such that X ∈ X_i.
Return 2^i+1 (denoted by (s,t)).


	(s,t) ≤(s,t) < 16k·(s,t).


	Let d = (s,t,G) and let j be the  index such that 2^j-1<d ≤ 2^j.
	Let X_i ∈ X_i ∈ S=(s) be the i level subset such that s ∈ X_i.
	Recall that s is padded in all the subsets X_i for 0≤ i ≤.
	
	Note that X_i has diameter smaller than 2· 2^i (follows from property (iii)). Therefore t∈ X_i implies that (s,t,G)<2·2^i=2^i+1. In particular, t ∉ X_i for every i < j-1.
	Hence the least common ancestor is at least at level j-1. Hence the minimal distance returned by the algorithm is  (s,t) ≥ 2^j ≥ d.
	
	It remains to show that (s,t) ≤ 16k· d.
	Let i be the level of s and t's least common ancestor.
	Note that t ∉ X_i-1.
	Also recall that s is padded in X_i-1 and thus B(s,ρ_i-1) ⊆ X_i-1, which implies d≥ρ_i-1 = 2^i-1/(4k) = (s,t)/(16k).



Let U_i be the set U after constructing the first i collections.
Note that |U_i+1| ≤ |U_i| - |U_i|^1-1/k.
By resolving this recurrence relation one can show that the number of phases is O(k n^1/k) (see <cit.>)
.
Notice that for every S∈ M, T( S) is of size O(n).
Hence, the size of our data structure is O(k n^1+1/k).



  
Reducing the size of the data structure:
We now show how to reduce the size of the data structure to O(n^1+1/k).
We only outline the modifications to the algorithm and the analysis and omit the full details.

Here we will use only the metric structure of the graph G, while ignoring the structure induced by the edges.
Specifically, in line (2) of the algorithm, instead of the graph G, we will use the graph G_U which is the complete graph over U, where the weight of each edge {u,v} is equal to (u,v,G).
This change allows us to remove the nodes V̂ from G_U after each iteration.


The query algorithm, given two nodes s and t is as follows.
Let S_s = (s) and S_t = (t), and assume w.l.o.g. that
S_s was constructed before S_t.
Find the least common ancestor of s and t in X ( S_s) and let i be its level.
Return 2^i+1.

Following the analysis of the previous construction we can show that properties (i)-(iv) are satisfied and that the stretch is bound by 16k.

The size of the data structure is bounded by O(n^1+1/k) (see <cit.>, Lemma 4.2.



  
Reducing the stretch to 8(1+)k:
We now explain how to reduce the stretch to 8(1+)k.
Note that we lose a factor of 2 in the stretch since we look on distances in multiplies of two.
Recall that in the algorithm, for a pair of vertices s,t at distance d, we looked on the minimal index j such that d ≤ 2^j.
It may happen that d is only slightly larger than 2^j-1.
Note that by just considering all distances (1+)^i rather than all distances 2^i, we get that the number of nodes that are padded in all levels is a fraction of
1/n^1/( k) rather than 1/n^1/k, which is dissatisfying.
So instead we construct O(1/) different copies of our data structure, one for each 1+ ℓ for 0≤ℓ < 1/.
In the copy ℓ of the data structure we consider distances (1+ℓ)2^i for every 0≤ i ≤.
Specifically, i-clusters have radius bounded by (1+ℓ)2^i, while the padding parameter is ρ_ℓ,i=(1+ℓ)ρ_i.
We denote by _ℓ(s) the collection 𝒮, created for the ℓ's distance oracle, where s is padded in all levels.
The distance estimation of the ℓ's copy (denoted by _ℓ(s,t)),
will be (1+(ℓ+1))2^i_ℓ, where i_ℓ is the level of the least common ancestor of s and t in _ℓ(s).

Set d=(s,t). For every ℓ, we have

    d>ρ_ℓ,i_ℓ-1=(1+ℓ)2^i_ℓ-1/4k=(1+ℓ)/(1+(ℓ+1))·_ℓ(s,t)/8k≥_ℓ(s,t)/8(1+)k .

From the other hand, there exist indices ℓ',j such that  (1+ℓ' )2^j-1 < d≤ (1+(ℓ'+1) )2^j-1. Following the analysis above, as t does not separated from s at level i_ℓ', it holds that i_ℓ'≥ j-1.  Therefore

    _ℓ'(s,t)=(1+(ℓ+1))2^i_ℓ'≥(1+(ℓ+1))2^j-1≥ d .

In the query phase we iterate over all O(1/) copies, invoke the query algorithm in each copy and return the largest distance.
By equations (<ref>) and (<ref>), the stretch is 8(1+)k rather than 16k.
The query time is O(1/) which is O(1) for every fixed .



§ RAMSEY SPANNING TREES


In this section we describe the construction of Ramsey spanning trees, each tree will be built using the petal decomposition framework of <cit.>.
Roughly speaking, the petal decomposition is an iterative method to build a spanning tree of a given graph. In each level, the current graph is partitioned into smaller diameter pieces, called petals, and a single central piece, which are then connected by edges in a tree structure. Each of the petals is a ball in a certain metric. The main advantage of this framework is that it produces a spanning tree whose diameter is proportional to the diameter of the graph, while allowing large freedom for the choice of radii of the petals. Specifically, if the graph diameter is Δ, the spanning tree diameter will be O(Δ), and each radius can be chosen in an interval of length ≈Δ. For the specific choice of radii that will ensure a sufficient number of vertices are fully padded, we use a region growing technique based on ideas from <cit.>.



 §.§ Preliminaries


For subset S⊆ G and a root vertex r∈ S, the radius of S w.r.t r,  Δ_r(S), is the minimal Δ such that B(r,Δ,S)=S.
	(If for every Δ, B(r,Δ,S)≠ S, (this can happen iff S is not connected) we say that Δ_r(S)=∞.)
When the root r is clear from context or is not relevant, we will omit it.

	Given a graph G=(V,E), a Strong Diameter Hierarchical Partition (SDHP) is a collection {𝒜_i}_i∈[Φ] of partitions of V, where each cluster in each partition has a root, such that:
	
		
  * 𝒜_Φ={V} (i.e., the first partition is the trivial one).
        
  * 𝒜_1={{v}_v∈ V} (i.e., in the last partition every cluster is a singleton).
		
  * For every 1≤ i<Φ and A∈𝒜_i, there is A'∈𝒜_i+1 such that A⊆ A' (i.e., 𝒜_i is a refinement of 𝒜_i+1).
		Moreover, Δ(A)≤Δ(A').
		
	


	Given a graph G=(V,E) and a subset A⊆ V, we say that a vertex y∈ A is ρ-padded by a subset A'⊆ A (w.r.t A) if B(y,Δ(A)/ρ,G)⊆ A'. See fig:paddedVertex for illustration.

	We say that x∈ V is ρ-fully-padded in the SDHP {𝒜_i}_i∈[Φ], if for every 2≤ i≤Φ and A∈𝒜_i such that x∈ A, there exists A'∈𝒜_i-1 such that x is ρ-padded by A' (w.r.t A).





 §.§ Petal Decomposition


Here we will give a concise description of the Petal decomposition algorithm, focusing on the main properties we will use.
For proofs and further details we refer to <cit.>.

The  (see alg:h-petal) is a recursive algorithm. The input is G[X] (a graph G=(V,E) induced over a set of vertices X⊆ V), a center x_0∈ X, a target t∈ X, and the radius Δ=Δ_x_0(X).[Rather than inferring Δ=Δ_x_0(X) from G[X] and x_0 as in <cit.>, we can think of Δ as part of the input. We shall allow any Δ≥Δ_x_0(X). We stress that in fact in the algorithm we always use Δ_x_0(X), and consider this degree of freedom only in the analysis.]  The algorithm invokes  to partition X into X_0,X_1,…,X_s (for some integer s), and also provides a set of edges {(x_1,y_1),…,(x_s,y_s)} and targets t_0,t_1,…,t_s.
The  algorithm now recurses on each (G[X_j],x_j,t_j,Δ_x_j(X_j)) for 0≤ j≤ s, to get trees {T_j}_0≤ j≤ s, which are then connected by the edges {(x_j,y_j)}_1≤ j≤ s to form a spanning tree T for G[X] (the recursion ends when X_j is a singleton). See fig:HPDExample for illustration.


Next we describe the  procedure, see alg:petal-d.
Initially it sets Y_0=X, and for j=1,2,…,s it carves out the petal X_j from the graph induced on Y_j-1, and sets Y_j=Y_j-1∖ X_j (in order to control the radius increase, the first petal is cut using different parameters). The definition of petal guarantees that Δ_x_0(Y_j) is non-increasing (see <cit.>), and when at step s it becomes at most 3Δ/4, define X_0=Y_s and then the  routine ends. In carving of the petal X_j⊆ Y_j-1, the algorithm chooses an arbitrary target t_j∈ Y_j-1 (at distance at least 3Δ/4 from x_0) and a range [lo,hi] of size hi-lo∈{Δ/8,Δ/4} which are provided to the sub-routine .



(One may notice that in line:edgeWeightReduce of the  procedure,
the weight of some edges is changed by a factor of 2. This can happen at most once for every edge throughout the   execution, thus it may affect the padding parameter by a factor of at most 2. This re-weighting is ignored for simplicity.)


Both  and  are essentially the algorithms that appeared in <cit.>. The main difference from their work lies in the  procedure, depicted in alg-pick-rad. It carefully selects a radius r∈[lo,hi], which determines the petal X_j together with a connecting edge (x_j,y_j)∈ E, where x_j∈ X_j is the center of X_j and y_j∈ Y_j. It is important to note that the target t_0∈ X_0 of the central cluster X_0 is determined during the creation of the first petal X_1. It uses an alternative metric on the graph, known as cone-metric:
 Given a graph G=(V,E), a subset X⊆ V
	and points x,y∈ X, define the cone-metric ρ=ρ(X,x,y):X^2→ℝ^+
	as ρ(u,v)=|(d_X(x,u)-d_X(y,u))-(d_X(x,v)-d_X(y,v))|.

(The cone-metric is in fact a pseudo-metric, i.e., distances between distinct points are allowed to be 0.) 
The ball B_(X,ρ)(y,r) in the cone-metric
ρ=ρ(X,x,y), contains all vertices u whose shortest path to x is increased (additively) by at most r if forced to go through y.

In the 
algorithm, while working in a subgraph G[Y] with two specified vertices: a center x_0
and a target t, we define W_r(Y,x_0,t)=⋃_p∈ P_x_0t: d_Y(p,t)≤ rB_(Y,ρ(Y,x_0,p))(p,r-d_Y(p,t)/2)
which is union of balls in the cone-metric, where any vertex p
in the shortest path from x_0 to t of distance at most r
from t is a center of a ball with radius r-d_Y(p,t)/2. 




The following facts are from <cit.>.

	 Running  on input (G[X],x_0,t,Δ_x_0(X)) will provide a spanning tree T satisfying
	
    Δ_x_0(T)≤ 4Δ_x_0(X).



	 If the  partitions X with center x_0 into X_0,…,X_s with centers x_0,…,x_s, then for any 0≤ j≤ s we have Δ_x_j(X_j)≤ (3/4)·Δ_x_0(X).


We will need the following observation. Roughly speaking, it says that when the  algorithm is carving out X_j+1, it is oblivious to the past petals X_1,…,X_j, edges and targets – it only cares about Y_j and the original diameter Δ.

Assume that  on input (G[X],x_0,t,Δ_x_0(X)) returns as output (X_0,X_1,…,X_s,{ y_1,x_1} ,…,{ y_s,x_s} ,t_0,…,t_s). Then running  on input (G[Y_j],x_0,t_0,Δ_x_0(X)) will output (X_0,X_j+1…,X_s,{ y_j+1,x_j+1} ,…,{ y_s,x_s} ,t_0,t_j+1…,t_s).






 §.§ Choosing a Radius



Fix some 1≤ j≤ s, and consider carving the petal X_j from the graph induced on Y=Y_j-1. While the algorithm of <cit.> described a specific way to choose the radius, we require a somewhat more refined choice. The properties of the petal decomposition described above (in subsec:PetalDecompDesc) together with FactPetal3/4Radius and FactPetalTreeRadiusBound4,  hold for any radius picked from a given interval. We will now describe the method to select a radius that suits our needs. The  algorithm provides an interval [lo,hi] of size at least Δ/8, and for each r∈[lo,hi] let W_r(Y,x_0,t)⊆ Y denote the petal of radius r (usually we will omit (Y,x_0,t)).
The following fact demonstrates that petals are similar to balls.


For every y∈ W_r and l≥ 0, B(y,l,Y)⊆ W_r+4l.

Note that FctW_rProp implies that W_r is monotone in r, i.e., for r≤ r' it holds that W_r⊆ W_r'.

Our algorithm will maintain a set of marked vertices M⊆ V, and will update it in any petal creation. Roughly speaking, the marked vertices are those that are fully padded in the (partial) hierarchical partition generated so far by the algorithm. If initially |M|=m, we want that at the end of the process at least m^1-1/k vertices will remain marked.
In the partition of X to X_0,…,X_s, some of the marked vertices will be ρ-padded by a petal X_j (w.r.t. X), and some of the others will be unmarked, by the following rule.  FctW_rProp implies that if we choose a radius r when creating some petal X_j=W_r, then all marked vertices in W_r-4Δ/ρ will be ρ-padded by X_j, and thus remain marked. All the marked vertices in W_r+4Δ/ρ∖ W_r-4Δ/ρ are considered unmarked from now on, since their Δ/ρ ball may intersect more than one cluster in the current partition (note that some of these vertices can be outside X_j).


Our algorithm to select a radius is based on region growing techniques, similar to those in alg-strong-ramsey, but rather more involved.

Since in the petal decomposition framework we cannot pick as center a vertex maximizing the "small ball", we first choose an appropriate range that mimics that choice (see e.g. line:a-b in the algorithm below) – this is the reason for the extra factor of loglog n.
The basic idea in region growing is to charge the number of marked vertices whose ball is cut by the partition (those in W_r+4Δ/ρ∖ W_r-4Δ/ρ), to those that are saved (in W_r-4Δ/ρ). In our setting we are very sensitive to constant factors in this charging scheme (as opposed to the average stretch considered in <cit.>), because these constants are multiplied throughout the recursion. In particular, we must avoid a range in [lo,hi] that contains more than half of the marked vertices, a constraint which did not exist in previous manifestation of this region growing scheme. To this end, if the first half [lo,mid] (with mid=(hi+lo)/2) is not suitable, we must "cut backwards" in the regime [mid,hi], and charge the marked vertices that were removed from M to the remaining graph Y_j, rather than to those saved in the created cluster X_j.[We remark that paying a factor of loglog(nW), where W is the maximum edge weight, might have simplified the algorithm slightly.]











 §.§ Proof of Correctness

Let z∈ V be an arbitrary vertex, given a set M⊆ V, let T be the tree returned by calling  on (G[V],z,z,Δ_z(V)) and marked vertices M. There is a natural Strong Diameter Hierarchical Partition (SDHP) X={𝒳_i}_i=1^Φ associated with the tree T, where
𝒳_i consists of all the clusters created in level Φ-i of the recursion (and 𝒳_Φ={V}).
By FactPetal3/4Radius, the radius is always non-increasing. Hence X is indeed a SDHP. Denote by (M)⊆ M the set of vertices that remained marked throughout the execution of .



Suppose x∈(M), then x is ρ-fully-padded in X.


Fix any 2≤ i≤Φ. Let X∈ X_i be the cluster containing x in the (Φ-i)-th level of the recursion with Δ=Δ(X). Assume X was partitioned by  into X_0,…,X_s, and let X_j⊆ X be the cluster containing x∈ X_j. Assuming (inductively) that x was ρ-padded by X, we need to show that it is also ρ-padded by X_j, that is, B=B(x,Δ/ρ,G)⊆ X_j. (Note that B⊆ X since the radii are non-increasing, so x is padded in all higher levels.)

First we argue that none of the petals X_1,…,X_j-1 intersects B. Seeking contradiction, assume it is not the case, and let 1≤ j'<j be the minimal such that there exists y∈ X_j'∩ B. By the minimality of j' it follows that B⊆ Y'=Y_j'-1, and thus (x,y,Y')=(x,y,G)≤Δ/ρ. Let r' be the radius chosen when creating the petal X_j'=W'_r', and FctW_rProp implies that

    x∈ B(y,Δ/ρ,Y')⊆ W'_r'+4Δ/ρ=W'_r'+R/(4Lk) ,

where we recall that Δ=8R and ρ=2^7Lk. This is a contradiction to the fact that x∈(X): clearly x∉ W'_r'-R/(4Lk) since it is not included in X_j'=W'_r' (and using the monotonicity of W'_r), so it should have been removed from M when creating X_j' (in line:M of the algorithm).

For the case j=0 the same reasoning shows B does not intersect any petal X_1,… ,X_s and we are done. For j>0, it remains to show that B⊆ X_j, but this follows by a similar calculation. Let r be the radius chosen for creating the petal X_j=W_r, and Y=Y_j-1. We have B⊆ Y, and since x∈(X) it must be that x∈ W_r-R/(4Lk). Again by FctW_rProp we have

    B=B(x,Δ/ρ,G)=B(x,Δ/ρ,Y)⊆ W_r-R/(4Lk)+4Δ/ρ = W_r=X_j .




	Consider a vertex v∈(M), then for every u∈ V, (v,u,T)≤ 8ρ·(v,u,G).


Let X={𝒳_i}_i=1^Φ be the SDHP associated with T, and for 1≤ i≤Φ let A_i∈ X_i be the cluster containing v. Take the minimal 2≤ i≤Φ such that u∈ A_i (there exists such an i since u∈ A_Φ=V and u∉ A_1={v}). By lem:active-padded v is ρ-fully-padded, so we have that B(v,Δ/ρ,G)⊆ A_i-1, where Δ=Δ(A_i). But as u∉ A_i-1, it must be that (u,v,G)>Δ/ρ. Since both u,v∈ A_i, FactPetalTreeRadiusBound4 implies that the radius of the tree created for A_i is at most 4Δ, so that
	
    (u,v,T)≤ 2· 4Δ≤ 8ρ·(u,v,G) .




|(M)|≥ |M|^1-1/k.



We prove by induction on |X| that if a cluster X∈ X_i (for some 1≤ i≤Φ) has currently m marked vertices, then at the end of the process at least m^1-1/k of them will remain marked.

The base case when X is a singleton is trivial. For the inductive step, assume we call  on (G[X],x_0,t,Δ) with Δ≥Δ_x_0(X) and the current marked vertices M̂. Assume that the  algorithm does a non-trivial partition of X to X_0,…,X_s (if it is the case that all vertices are sufficiently close to x_0, then no petals will be created, and the
  will simply recurse on (G[X],x_0,t,Δ_x_0(X)), so we can ignore this case).  Denote by M_j the marked vertices that remain in X_j (just before the recursive call on X_j), and recall that (X_j) is the set of vertices of M_j that remain marked until the end of the  algorithm. Then (X)=⋃_0≤ j≤ s(X_j), and we want to prove that |(X)|≥ m^1-1/k.

Let X_1=W_r be the first petal created by the  algorithm, and Y_1=X∖ X_1.
Denote by (X_1)=W_r+R/(4Lk)∩M̂ the responsibility set for X_1 (i.e. the marked vertices that are either in M_1 or were removed from M̂ when X_1 was created). Define M'=M̂∖(X_1), the set of marked vertices that remain in Y_1.
By ob:delta, we can consider the remaining execution of  on Y_1 as a new recursive call of  with input (G[Y_1],x_0,t_0,Δ) and marked vertices M'. Since |X_1|,|Y_1|<|X|, the induction hypothesis implies that |(X_1)|≥|M_1|^1-1/k and |(Y_1)|≥|M'|^1-1/k.

We now do a case analysis according to the choice of radius in alg-pick-rad.


  * Case 1: w_mid≤ m/2 and w_lo+R/(2L)=0. In this case we set r=lo+R/(4L). Note that w_r+R/(4Lk)≤ w_lo+R/(2L)=0, so M'=M̂, and by the induction hypothesis on Y_1, the number of fully padded vertices is |(X)|= |(Y_1)|≥|M̂|^1-1/k=m^1-1/k, as required.


  * Case 2: w_mid≤ m/2 and w_lo+R/(2L)>0. In this case we pick a,b∈[lo,hi] so that b-a=R/(2L) and
    
    w_a>w_b^2/m ,
 and also choose r∈[a,b] such that w_r+b-a/2k≤ w_r-b-a/2k·(w_b/w_a)^1/k. As b-a/2k=R/4Lk and |M_1|=w_r-R/(4Lk) we have that
    
    |M_1|≥(X_1)·(w_a/w_b)^1/k .

    By the induction hypothesis on X_1 we have that
	
    |(X_1)|    ≥|M_1|/|M_1|^1/k(<ref>)≥|(X_1)|·(w_a/|M_1|· w_b)^1/k
       (<ref>)≥|(X_1)|·(w_b/m·|M_1|)^1/k≥|(X_1)|/m^1/k ,

    where in the last inequality we use that |M_1|= w_r-(b-a)/(2k)≤ w_b. Now by the induction hypothesis on Y_1 we get
    
    |(X)|     =|(Y_1)|+|(X_1)|
       ≥|M'|^1-1/k+|(X_1)|/m^1/k≥|M'|+|(X_1)|/m^1/k=|M̂|/m^1/k=m^1-1/k



  * Case 3: w_mid> m/2 and q_hi-R/(2L)=0. In this case we set r=hi-R/(4L). Note that q_r-R/(4Lk)≤ q_hi-R/(2L)=0 (recall that q_r is non-increasing in r, by FctW_rProp), so M_1=M̂, and by the induction hypothesis on X_1, |(X)|=|(X_1)|≥|M_1|^1-1/k=m^1-1/k, as required.


  * Case 4: w_mid> m/2 and q_hi-R/(2L)>0. In this case we pick a,b∈[lo,hi] so that a-b=R/(2L) and
    
    q_a>q_b^2/m ,

    and also choose r∈[b,a] such that q_r-b-a/2k≤ q_r+b-a/2k·(q_b/q_a)^1/k. In this case when we cut "backwards", we shift the responsibility for the vertices unmarked by the creation of X_1 to Y_1. This is captured by defining (Y_1)=M̂∖ M_1.
    Since |M'|=q_r+a-b/2k and |(Y_1)|= q_r-a-b/2k we have
    
    |M'|≥|(Y_1)|·(q_a/q_b)^1/k .

    By the induction hypothesis on Y_1 we have that
	
    |(Y_1)|    ≥|M'|/|M'|^1/k(<ref>)≥|(Y_1)|·(q_a/|M'|· q_b)^1/k
       (<ref>)≥|(Y_1)|·(q_b/m·|M'|)^1/k≥|(Y_1)|/m^1/k ,

    where in the last inequality we use that |M'|= q_r+(a-b)/(2k)≤ q_b. Now by the induction hypothesis on X_1 we get
    
    |(X)|     =|(Y_1)|+|(X_1)|
       ≥|(Y_1)|/m^1/k+|M_1|^1-1/k≥|(Y_1)|+|M_1|/m^1/k=|M̂|/m^1/k=m^1-1/k .




From lem:paddedImpliesStretch and lem:SavedTerminals we derive the following theorem.

Let G=(V,E) be a weighted graph, fix a set M⊆ V of size m and a parameter k≥ 1. There exists a spanning tree T of G, and a set (M)⊆ M of size at least m^1-1/k, such that for every v∈(M) and every u∈ V it holds that (v,u,T)≤ O(kloglog m)·(v,u,G).


We conclude with the proof of our main result.

Set M_1=V, and for i≥ 1 define M_i+1=M_i∖(M_i). We shall apply thm:main iteratively, where M_i is the set of vertices given as input to the i-th iteration, that has size |M_i|=m_i. Let T_i be the tree created in iteration i. By thm:main the sizes m_1,m_2,… obey the recurrence m_1=n and m_i+1≤ m_i-m_i^1-1/k, which implies that after k· n^1/k iterations we will have m_k· n^1/k+1<1 (see <cit.>), and thus every vertex is in (M_i) for some 1≤ i≤ k· n^1/k. For each v∈ V, let (v) be the tree T_i such that v∈(M_i).





 §.§ Routing with Short Labels


In this section we prove thm:route.
We first use a result of <cit.> concerning routing in trees.

	For any tree T=(V,E) (where |V|=n), there is a routing scheme with stretch 1 that has routing tables of size O(b) and labels of size (1+o(1))log_bn. The decision time in each vertex is O(1).



Combining thm:main-col and thm:tree-routh we can construct a routing scheme. Let 𝒯 be the set of trees from thm:main-col.
Each tree T∈𝒯 is associated with a routing scheme given by thm:tree-routh. Set L_T(x) be the label of the vertex x in the routing scheme of the tree T.

In our scheme, the routing table of each vertex will be the collection of its routing tables in all the trees in T. Hence the table size is O(b)· |𝒯|=O(k· b· n^1/k).
The label of each x∈ V will be   ((x),L_(x)(x)), i.e., the name of the home tree of x and the label of x in that tree. The label size is 1+(1+o(1))log_bn=(1+o(1))log_bn.

The routing is done in a straightforward manner, to route from y to x, we extract (x) from the given label of x, and simply use the routing scheme of the tree (x). Note that this process takes O(1) time, and is independent of the routing path traversed so far. Since all vertices store in their routing table the appropriate routing information for (x), the routing can be completed.

alpha
















§ PROOF OF CORRECTNESS FOR ALG-PICK-RAD

In this section we prove that the choices made in the  procedure are all legal. In all the Lemmas that follow, we shall use the notation in alg-pick-rad.

	If w_mid≤m/2 and w_lo+R/2L≥1,
	then
	there is [a,b]⊆[lo,mid]
	such that b-a=R/2L and w_a≥ w_b^2/m.


	Seeking contradiction, assume that for every such a,b with b-a=R/2L it holds that w_b>√(m· w_a). Applying this on b=mid-i R/2L and a=mid-(i+1) R/2L for every i=0,1,…,L-2, we have that
	
    w_mid    >m^1/2· w_mid-R/2L^1/2>…
    	 >m^1-2^-(L-1)· w_mid-(L-1)R/2L^2^-(L-1)≥ m·2^-1· w_lo+R/2L^1/(2log m)≥m/2 ,

	where we used that 1+loglog m≤ L≤ 2+loglog m and mid=lo+R/2. In the last inequality we also used that w_a≥ 1, which follows since b=a+R/2L≥ lo+R/2L, thus w_b≥ 1, and in particular w_a≥ w_b^2/m>0. The contradiction follows.


	There is r∈[a,b] such that w_r+b-a/2k≤ w_r-b-a/2k·(w_b/w_a)^1/k.


	Seeking contradiction, assume there is no such choice of r, then applying this for r=b-(i+1/2)·b-a/k for i=0,1,…,k-1 we get
	
    w_b>w_b-b-a/k·(w_b/w_a)^1/k>⋯>w_b-k·b-a/k·(w_b/w_a)^k/k=w_a·w_b/w_a=w_b ,

	a contradiction.

The following two lemmas are symmetric to the two lemmas above.

	If w_mid>m/2 (implies q_mid≤m/2) and q_hi-R/2L≥1,	
	then
	there is [b,a]⊆[mid,hi]
	such that a-b=R/2L and q_a≥ q_b^2/m.


	There is r∈[b,a] such that
	q_r-a-b/2k≤ q_r+a-b/2k·(q_b/q_a)^1/k.



§ TABLE OF DISTANCE ORACLES


