pdf

Lower Bounds for Local Monotonicity Reconstruction
from Transitive-Closure Spanners
Arnab Bhattacharyya∗
Elena Grigorescu∗
Sofya Raskhodnikova†
Madhav Jha†
Kyomin Jung‡
David P. Woodruff§
Abstract
Given a directed graph G = (V, E) and an integer k ≥ 1, a k-transitive-closure-spanner (k-TCspanner) of G is a directed graph H = (V, EH ) that has (1) the same transitive-closure as G and (2)
diameter at most k. Transitive-closure spanners are a common abstraction for applications in access
control, property testing and data structures.
We show a connection between 2-TC-spanners and local monotonicity reconstructors. A local monotonicity reconstructor, introduced by Saks and Seshadhri (SIAM Journal on Computing, 2010), is a randomized algorithm that, given access to an oracle for an almost monotone function f : [m]d → R, can
quickly evaluate a related function g : [m]d → R which is guaranteed to be monotone. Furthermore,
the reconstructor can be implemented in a distributed manner. We show that an efficient local monotonicity reconstructor implies a sparse 2-TC-spanner of the directed hypergrid (hypercube), providing
a new technique for proving lower bounds for local monotonicity reconstructors. Our connection is, in
fact, more general: an efficient local monotonicity reconstructor for functions on any partially ordered
set (poset) implies a sparse 2-TC-spanner of the directed acyclic graph corresponding to the poset.
We present tight upper and lower bounds on the size of the sparsest 2-TC-spanners of the directed hypercube and hypergrid. These bounds imply tighter lower bounds for local monotonicity reconstructors
that nearly match the known upper bounds.
∗
Massachusetts Institute of Technology, USA. Email:{abhatt,elena g}@mit.edu.
Pennsylvania State University, USA. Email: {mxj201,sofya}@cse.psu.edu. Supported by NSF CAREER award
0845701.
‡
KAIST, South Korea. Email:[email protected]
§
IBM Almaden Research Center, USA. Email: [email protected].
†
1
Introduction
Graph spanners were introduced in the context of distributed computing [?], and since then have found
numerous applications, such as efficient routing [?, ?, ?, ?, ?], simulating synchronized protocols in unsynchronized networks [?], parallel and distributed algorithms for approximating shortest paths [?, ?, ?], and
algorithms for distance oracles [?, ?]. Several variants on graph spanners have been defined. In this work,
we focus on transitive-closure spanners that were introduced in [?] as a common abstraction for applications
in access control, property testing and data structures.
Definition 1.1 (TC-spanner). Given a directed graph G = (V, E) and an integer k ≥ 1, a k-transitiveclosure-spanner (k-TC-spanner) of G is a directed graph H = (V, EH ) with the following properties:
1. EH is a subset of the edges in the transitive closure of G.
2. For all vertices u, v ∈ V , if dG (u, v) < ∞, then dH (u, v) ≤ k.
Thus, a k-transitive-closure-spanner (or k-TC-spanner) is a graph with small diameter that preserves the
connectivity of the original graph. In the applications above, the goal is to find the sparsest k-TC-spanner
for a given k and G. The number of edges in the sparsest k-TC-spanner of G is denoted by Sk (G).
1.1
Our Contributions
The contributions of this work fall into two categories: (1) We show that an efficient local monotonicity
reconstructor implies a sparse 2-TC-spanner of the directed hypergrid (hypercube), providing a new technique for proving lower bounds for local monotonicity reconstructors. (2) We present tight upper and lower
bounds on the size of the sparsest 2-TC-spanners of the directed hypercube and hypergrid. These bounds
imply tighter lower bounds for local monotonicity reconstructors for these graphs that nearly match the
upper bounds given in [?].
1.2
Lower Bounds for Local Monotonicity Reconstruction
Property-preserving data reconstruction was introduced in [?]. In this model, a reconstruction algorithm,
called a filter, sits between a client and a dataset. A dataset is viewed as a function f : D → R. The client
accesses the dataset using queries of the form x ∈ D to the filter. The filter looks up a small number of
values in the dataset and outputs g(x), where g must satisfy some fixed structural property P. Extending
this notion, Saks and Seshadhri [?] defined local reconstruction. A filter is local if it allows for a local (or
distributed) implementation: namely, if the output function g does not depend on the order of the queries.
Definition 1.2 (Local filter). A local filter for reconstructing property P is an algorithm A that has oracle
access to a function f : D → R, and to an auxiliary random string ρ (the “random seed”), and takes as
input x ∈ D. For fixed f and ρ, A runs deterministically on input x to produce an output Af,ρ (x) ∈ R.
(Note that a local filter has no internal state to store previously made queries.) The function g(x) = Af,ρ (x)
output by the filter must satisfy the following conditions:
• For each f and ρ, the function g must satisfy P.
• If f satisfies P, then g must be identical to f with probability at least 1 − δ, for some error probability
δ ≤ 1/3. The probability is taken over ρ.
In answering query x ∈ D, the filter A may ask for values of f at domain points of its choice (possibly
adaptively) using its oracle access to f . Each such access made to the oracle is called a lookup to distinguish
1
it from the client query x. A local filter is non-adaptive if the set of domain points that the filter looks up to
answer an input query x does not depend on answers given by the oracle.
In [?], the authors also required that g must be sufficiently close to f : With high probability (over the
choice of ρ), Dist(g, f ) ≤ B(n) · Dist(f, P), where B(n) is called the error blow-up. (Dist(g, f ) is the
number of points in the domain on which f and g differ. Dist(f, P) is ming∈P Dist(g, f ).) If a local filter
along with Definition 1.2 satisfies this condition, we call it distance-respecting.
1.2.1
Local Monotonicity Reconstructors
The most studied property in the local reconstruction model is monotonicity of functions [?, ?].
To define monotonicity of functions, consider an n-element poset Vn and let Gn = (Vn , E) be the
relation graph, i.e., the Hasse diagram, for Vn . A function f : Vn → R is called monotone if f (x) ≤ f (y) for
all (x, y) ∈ E. We particularly focus on posets which have the directed hypergrid graph as its relation graph.
The directed hypergrid, denoted Hm,d , has vertex set {1, 2, . . . , m}d and edge set {(x, y) : ∃ unique i ∈
{1, . . . , d} such that yi − xi = 1 and for j 6= i, yj = xj }. For the special case m = 2, H2,d is called a
hypercube and is also denoted by Hd . A monotonicity filter needs to ensure that the output function g is
monotone. For instance, if Gn is a directed line, Hn,1 , the filter needs to ensure that the output sequence
specified by g is sorted.
To motivate monotonicity reconstructors for hypergrids, consider the scenario of rolling admissions:
An admissions office assigns d scores to each application, such as the applicant’s GPA, SAT results, essay
quality, etc. Based on these scores, some complicated (third-party) algorithm outputs the probability that
a given applicant should be accepted. The admissions office wants to make sure “on the fly” that strictly
better applicants are given higher probability, that is, probabilities are monotone in scores. A hypergrid
monotonicity filter may be used here.
A local filter can be implemented in a distributed manner with an additional guarantee that every copy
of the filter will correct to the same monotone function of the scores. This can be done by supplying the
same random seed to each copy of the filter.
[?] gives a distance-respecting local monotonicity filter for the directed hypergrid, Hm,d , that makes
(log m)O(d) lookups per query. No non-trivial monotonicity filter for the hypercube Hd (performing o(2d )
lookups per query) is known. One of the monotonicity filters in [?] is a local filter for the directed line Hm,1
with O(log m) lookups per query (but a worse error blow up than in [?]). As observed in [?], this upper
bound is tight. A lower bound of 2αd , on the number of lookups per query for a distance-respecting local
monotonicity filter on Hd with error blow-up 2βd , where α, β are sufficiently small constants, appeared
in [?]. Notably, all known local monotonicity filters are non-adaptive.
We show how to construct sparse 2-TC-spanners from local monotonicity reconstructors with low
lookup complexity. These constructions, together with our lower bounds on the size of 2-TC-spanners
of the hypergrid and hypercube (Section 1.3), imply lower bounds on lookup complexity of local monotonicity reconstructors for these graphs with arbitrary error blow-up. We state our transformations from
non-adaptive and adaptive reconstructors separately.
Theorem 1.1 (Transformation from non-adaptive Local Monotonicity Reconstructors to
2-TC-spanners). Let Gn = (Vn , E) be a poset on n nodes. Suppose there is a non-adaptive local monotonicity reconstructor A for Gn that looks up at most `(n) values on any query and has error probability at
most δ. Then there is a 2-TC-Spanner of Gn with O(n`(n) · dlog n/ log(1/δ)e) edges.
Next theorem applies even to adaptive local monotonicity reconstuctors. It takes into account how many
lookups on query x are points incomparable to x. In particular, if there are no such lookups, then constructed
2-TC-spanner is of the same size as in Theorem 1.1.
2
Theorem 1.2 (Transformation from adaptive Local Monotonicity Reconstructors to
2-TC-spanners). Let Gn = (Vn , E) be a poset on n nodes. Suppose there is an (adaptive) local monotonicity
reconstructor A for Gn that, for any query x ∈ Vn , looks up at most `1 (n) vertices comparable to x and at
most `2 (n) vertices incomparable to x, and has error probability at most δ. Then there is a 2-TC-Spanner
of Gn with O(n`1 (n) · 2`2 (n) dlog n/ log(1/δ)e) edges.
In Theorem 1.1 and 1.2, when δ is sufficiently small, the bounds on the 2-TC-Spanner size become
O(n`(n)) and O(n`1 (n) · 2`2 (n) ), respectively.
As mentioned earlier, all known monotonicity reconstructors are non-adaptive. It is an open question
whether it is possible to give a transformation from adaptive local monotonicity reconstructors to 2-TCspanners without incurring an exponential dependence on the number of lookups made to points incomparable to the query point. We do not know whether this dependence is an artifact of the proof or an indication
that lookups to incomparable points might be helpful for adaptive local monotonicity reconstructors.
In Theorems 1.5 and 1.6 (Section 1.3), we present nearly tight bounds on the size of the sparsest 2TC-spanners of the hypercube and the hypergrid. Theorems 1.1 and 1.2, together with the lower bounds in
Theorems 1.5 and 1.6, imply the following lower bounds on the lookup complexity of local monotonicity
reconstructors for these graphs with arbitrary error blow-up.
Corollary 1.3. Consider a nonadaptive local monotonicity
filter with constant
error probability δ. If the
logd−1 m
filter is for functions f : Hm,d → R, it must perform Ω dd (2 log log m)d−1 lookups per query. If the filter is
for functions f : Hd → R, it must perform Ω 2αd /d lookups per query, where α ≥ 0.1620.
Corollary 1.4. Consider an (adaptive) local monotonicity filter with constant error probability δ, that for
every query x ∈ Vn , looks
incomparable to x. If the filter is for functions f : Hm,d →
up at most `2 vertices
R, it must perform Ω
logd−1 m
lookups to vertices comparable to x per query x. If the filter is
for functions f : Hd → R, it must perform Ω 2αd−`2 /d comparable lookups, where α ≥ 0.1620.
2`2 dd (2 log log m)d−1
Prior to this work, no lower bounds for monotonicity reconstructors on Hm,d with dependence on both
m and d were known. Unlike the bound in [?], our lower bounds hold for any error blow-up and for
non-distance-respecting filters. Our bounds are tight for non-adaptive reconstructors. Specifically, for the
hypergrid Hm,d of constant dimension d, the number of lookups is (log m)Θ(d) , and for the hypercube Hd ,
it is 2Θ(d) for any error blow-up.
1.2.2
Testers vs. Reconstructors
[?] obtained monotonicity testers from 2-TC-spanners. Unlike in the application to monotonicity testing,
here we use lower bounds on the size of 2-TC-spanners to prove lower bounds on complexity of local
monotonicity reconstuctors. Lower bounds on the size of 2-TC-spanners do not imply corresponding lower
bounds on monotonicity testers. E.g., the best monotonicity tester on Hd runs in O(d2 ) time [?, ?], while,
as shown in Theorem 1.6, every 2-TC-spanner of Hd must have size exponential in d.
1.3
Our Results on 2-TC-Spanners of the Hypercube and Hypergrid
Our main theorem gives a set of explicit bounds on S2 (Hm,d ):
Theorem 1.5 (Hypergrid). Let S2 (Hm,d ) denote the number of edges in the sparsest 2-TC-spanner of Hm,d .
Then1 for m ≥ 3,
!
md logd m
Ω
= S2 (Hm,d ) ≤ md logd m.
(2d log log m)d−1
1
Logarithms are always to base 2 unless otherwise indicated.
3
The upper bound in Theorem 1.5 follows from a general construction of k-TC-spanners for graph products for arbitrary k ≥ 2, presented in Section 4.1. The lower bound is the most technically difficult part of
our work. It is proved by a reduction of the 2-TC-spanner construction for [m]d to that for the 2 × [m]d−1
grid and then directly analyzing the number of edges required for a 2-TC-spanner of 2 × [m]d−1 . We show
a tradeoff between the number of edges in the 2-TC-spanner of the 2 × [m]d−1 grid that stay within the
hyperplanes {1} × [m]d−1 and {2} × [m]d−1 versus the number of edges that cross from one hyperplane to
the other. The proof proceeds in multiple stages. Assuming an upper bound on the number of edges staying within the hyperplanes, each stage is shown to contribute a substantial number of new edges crossing
between the hyperplanes. The proof of this tradeoff lemma is already non-trivial for d = 2 and is presented
first in Section 4.2.1. The proof for d > 2 is presented subsequently in Section 4.2.2.
While Theorem 1.5 is most useful when m is large and d is small, in Section 6, we present bounds on
S2 (Hm,d ) which are optimal up to a factor of d2m and, thus, supersede the bounds from Theorem 1.5 when
m is small. The general form of these bounds is a somewhat complicated combinatorial expression but they
can be estimated numerically. Specifically, S2 (Hm,d ) = 2cm d poly(d), where c2 ≈ 1.1620, c3 ≈ 2.03,
c4 ≈ 2.82 and c5 ≈ 3.24, each significantly smaller than the exponents corresponding to the transitive
closure sizes for the different m.
We first prove the special case of m = 2 (i.e., the hypercube) in Section 5 and then generalize the
arguments to general m. Specifically, we obtain the following theorem for the hypercube.
Theorem 1.6 (Hypercube). Let S2 (Hd ) be the number of edges in the sparsest 2-TC-spanner of Hd . Then
Ω(2cd ) = S2 (Hd ) = O(d3 2cd ), where c ≈ 1.1620.
As a comparison point for our bounds, note that the obvious bounds on S2 (Hd ) are the number of edges
in the d-dimensional hypercube, 2d−1 d, and the number of edges in the transitive closure of Hd , which is
3d − 2d . (An edge in the transitive closure of Hd has 3 possibilities for each coordinate: both endpoints are
0, both endpoints are 1, or the first endpoint is 0 and the second is 1. This includes self-loops, so we subtract
the number of vertices in Hd to get the desired quantity.) Thus, 2d−1 d ≤ S2 (Hd ) ≤ 3d − 2d . Similarly, the
straightforward bounds on the number of edges in a 2-TC-spanner of Hm,d in terms of the number of edges
2 d
in the directed grid and in its transitive closure are dmd−1 (m − 1) and m 2+m − md , respectively.
1.3.1
Previous work on bounding Sk for other families of graphs
Thorup [?] considered a special case of TC-spanners of graphs G that have at most twice as many edges as
G, and conjectured that for all directed graphs G on n nodes there are such k-TC-spanners with k polylogarithmic in n. He proved this for planar graphs [?], but Hesse [?] gave a counterexample for general graphs
1
by constructing a family for which all n 17 -TC-spanners need n1+Ω(1) edges. TC-spanners were studied for
directed trees: implicitly in [?, ?, ?, ?, ?] and explicitly in [?]. For the directed line, [?] (and later, [?])
expressed Sk (Hn,1 ) in terms of the inverse Ackermann function. (See Section 2.2 for a definition.)
Lemma 1.7 ([?, ?, ?]). Let Sk (Hn,1 ) denote the number of edges in the sparsest k-TC-spanner of the
directed line Hn,1 . Then S2 (Hn,1 ) = Θ(n log n), S3 (Hn,1 ) = Θ(n log log n), S4 (Hn,1 ) = Θ(n log∗ n)
and, more generally, Sk (Hn,1 ) = Θ(nλk (n)) where λk (n) is the inverse Ackermann function.
The same bound holds for directed trees [?, ?, ?]. An O(n log n · λk (n)) bound on Sk for H-minor-free
graph families (e.g., bounded genus and bounded tree-width graphs) was given in [?].
4
2
2.1
Preliminaries
Notation
For a positive integer m, we denote {1, . . . , m} by [m]. For x ∈ {0, 1}d , we use |x| to denote the weight of
x, that is, the number of non-zero coordinates in x. Level i in a hypercube contains all vertices of weight
i. The partial order on the hypergrid Hm,d is defined as follows: x y for two vertices x, y ∈ [m]d iff
xi ≤ yi for all i ∈ [d]. Similarly, x ≺ y, if x and y are distinct vertices in [m]d satisfying x y. Vertices
x and y are comparable if either y is above x (that is, x y) or y is below x (that is, y x). We denote a
path from v1 to v` , consisting of edges (v1 , v2 ), (v2 , v3 ), . . . , (v`−1 , v` ) by (v1 , . . . , v` ).
2.2
The Inverse Ackermann Hierarchy
Our definition of inverse Ackermann functions is derived from the discussion in [?]. For a given function
f : R≥0 → R≥0 such that f (x) < x for all x > 2, define the function f ∗ (x) : R≥0 → R≥0 to be the
following:
f ∗ (x) = min{k ∈ Z≥0 : f (k) (x) ≤ 2}, where f (k) denotes f composed with itself k times
We note that the solution to the following recursion:
(
0
if n ≤ 2
T (n) ≤
n
a · n + f (n) · T (f (n)) if n > 2
is T (n) = a · n · f ∗ (n). This follows from the fact that f ∗ (f (n)) = f ∗ (n) − 1 for n > 2.
We define the inverse Ackermann hierarchy to be a sequence of functions λk (·) for k ≥ 0. As the base
√
cases, we have λ0 (n) = n/2 and λ1 (n) = n. For j ≥ 2, we define λj (n) = λ∗j−2 (n). Thus, λ2 (n) =
Θ(log n), λ3 (n) = Θ(log log n) and λ4 (n) = Θ(log∗ n). Note that the λk (·) functions defined here coincide
(upto constant additive differences) with the λ(k, ·) functions in [?] although they were formulated a bit
differently there.
Finally, we define the inverse Ackermann function α(·) to be α(n) = min{k ∈ Z≥0 : λ2k (n) ≤ 3}.
3
Transformation from Local Monotonicity Reconstructors to 2-TC-Spanners
In this section, we prove Theorems 1.1 and 1.2.
3.1
From non-adaptive Local Monotonicity Reconstructors to 2-TC-Spanners
Proof of Theorem 1.1. Let A be a local reconstructor given by the statement of the
theorem. Let F be the
n
set of pairs (x, y) with x, y in Vn such that x ≺ y. Then, F is of size at most 2 . Given (x, y) ∈ F, let
cube(x, y) be the set {z ∈ Vn : x z y}. Define function f (x,y) (v) to be 1 on all v x and all v y,
and 0 everywhere else. Also, define function f (x,y) (v), which is identical to f (x,y) (v) for all v ∈
/ cube(x, y)
and 0 for v ∈ cube(x, y). Both, f (x,y) and f (x,y) , are monotone functions for all (x, y) ∈ F. Let Aρ be
the deterministic algorithm which runs A with the random seed fixed to ρ. We say a string ρ is good for
(x, y) ∈ F if filter Aρ on input f (x,y) returns g = f (x,y) and on input f (x,y) returns g = f (x,y) .
Now we show that there exists a set S of size s ≤ d2 log n/ log(1/2δ)e, consisting of strings used as
random seeds by A, such that for every (x, y) ∈ F some string ρ ∈ S is good for (x, y). We choose S by
picking strings used as random seeds uniformly and independently at random. Since A has error probability
5
at most δ, we know that for every monotone f , with probability at least 1 − δ (with respect to the choice of
ρ), the function Af,ρ is identical to f . Then, for fixed (x, y) ∈ F and uniformly random ρ,
Pr[ρ is not good for (x, y)] ≤
Pr[Aρ on input f (x,y) fails to output f (x,y) ]
+ Pr[Aρ on input f (x,y) fails to output f (x,y) ] ≤ 2δ.
Since strings in S are chosen independently, Pr[no ρ ∈ S is good for (x, y)] ≤ (2 · δ)s , which, for s =
d2 log n/ log(1/2δ)e, is at most 1/n2 < 1/|F|. By a union bound over F,
Pr[for some (x, y) ∈ F, no ρ ∈ S is good for (x, y)] < 1.
Thus, there exists a set S with required properties.
We construct our 2-TC-spanner H = (Vn , EH ) of Gn using set S described above. Let Nρ (x) be the set
consisting of x and all vertices looked up by Aρ on query x. (Note that the set Nρ (x) is well-defined since
algorithm A is assumed to be non-adaptive). For each string ρ ∈ S and each vertex x ∈ Vn , connect x to all
comparable vertices in Nρ (x) (other than itself) and orient these edges according to their direction in Gn .
We prove H is a 2-TC-Spanner as follows. Suppose not, i.e., there exists (x, y) ∈ F with no path of
length at most 2 in H from x to y. Consider ρ ∈ S which is good for (x, y). Define function h by setting
h(v) = f (x,y) (v) for all v ∈
/ cube(x, y). Then h(v) = f (x,y) (v) for all v ∈
/ cube(x, y), by definition of
(x,y)
f
. For a v ∈ cube(x, y), set h(v) to 1 for v ∈ Nρ (x) and to 0 for v ∈ Nρ (y). All unassigned points
are set to 0. By the assumption above, Nρ (x) ∩ Nρ (y) does not contain any points in cube(x, y). Therefore,
h is well-defined. Since ρ is good for (x, y) and h is identical to f (x,y) for all lookups made on query x,
Aρ (x) = h(x) = 1. Similarly, Aρ (y) = h(y) = 0. But x ≺ y, so Ah,ρ (v) is not monotone. Contradiction.
The number of edges
Xin H is at most
|Nρ (x)| ≤ n · `(n) · s ≤ n`(n) · d2 log n/ log(1/2δ)e.
x∈Vn ,ρ∈S
3.2
From adaptive Local Monotonicity Reconstructors to 2-TC-Spanners
The complication in the transformation from an adaptive filter is that the set of vertices looked up by the
filter depends on the oracle that the filter is invoked on.
Proof of Theorem 1.2. Define F, f (x,y) , f (x,y) , Aρ and S as in the proof of Theorem 1.1. As before, for
each x ∈ Vn , we define sets Nρ (x), and construct the 2-TC-Spanner H by connecting each x to comparable
points in Nρ (x) for all ρ ∈ S and orienting the edges according to Gn . However, now Nρ (x) is a union
of several sets Nρb,w (x), indexed by b ∈ {0, 1} and w ∈ {0, 1}`2 (n) . (In addition, Nρ (x) contains x.) For
each x ∈ Vn , b ∈ {0, 1} and w ∈ {0, 1}`2 (n) , let Nρb,w (x) ⊆ Vn be the set of lookups performed by Aρ
on query x, assuming that the oracle answers all lookups as follows. When a lookup y is comparable to x,
answer 0 if y ≺ x, b if y = x, 1 if x ≺ y. Otherwise, if y is the i’th lookup made to an incomparable point
for some i ∈ [`2 ], answer w[i]. Recall that we set Nρ (x) to be the union of Nρb,w for all b ∈ {0, 1} and all
w ∈ {0, 1}`2 (n) . This completes the description of Nρ (x) and construction of H.
The argument that H is a 2-TC-spanner proceeds similarly to that in the proof of Theorem 1.1. The
caveat is that an adaptive local filter might choose lookups based on the answers to previous lookups. The
constructed function h sets h(x) = 1 and h(y) = 0. Further all points comparable to x are set to 0 if they
are below x and 1 if they are above x. However, points incomparable to x might be comparable to y and
are set to 0 or 1, depending on whether they are above or below y. Since we included sets of points queried
under all these possibilities in Nρ (x), we can now conclude that Aρ (x) = h(x) = 1. The same applies for
y. So, Ah,ρ outputs a non-monotone function, witnessed by the pair (x, y). Contradiction.
6
We proceed to bound the number of edges EH in H. For each ρ ∈ S, x ∈ Vn , b ∈ {0, 1}, and
ρ
w ∈ {0, 1}`2 (n) , the number of vertices in Nb,w
(x) comparable to x is at most `1 (n). Therefore,
`2 (n)
|EH | ≤ `1 (n) · 2 · 2
· |S| ≤ O n · `1 (n) · 2`2 (n) dlog n/ log(1/δ)e .
4
2-TC-Spanners for Low-Dimensional Hypergrids
In this section, we describe the proof of Theorem 1.5 which gives explicit bounds on the size of the sparsest
2-TC-spanner for Hm,d . The upper bound in Theorem 1.5 is proved in Section 4.1 and lower bound in
Section 4.2.
4.1
Upper Bound
The upper bound in Theorem 1.5 follows straightforwardly from a more general statement about TCspanners of product graphs presented in the following section. In the same section, we derive the upper
bound in Theorem 1.5.
4.1.1
Construction for Product Graphs
This section explains how to construct a TC-spanner of the Cartesian product of graphs G1 and G2 from TCspanners of G1 and G2 . Since the directed hypergrid is the Cartesian product of directed lines, and optimal
TC-spanner constructions are known for the directed line, our construction yields sparse TC-spanners for
the grid (Corollary 4.2). We start by defining two graph products: Cartesian and strong.
Definition 4.1 (Graph products). Given graphs G1 = (V1 , E1 ) and G2 = (V2 , E2 ), a product of G1 and
G2 is a new graph G with vertex set V1 × V2 . For the Cartesian graph product, denoted by G1 × G2 , graph
G contains an edge from (u1 , u2 ) to (v1 , v2 ) if and only if u1 = v1 and (u2 , v2 ) ∈ E2 , or (u1 , v1 ) ∈ E1
and u2 = v2 . For the strong graph product, denoted by G1 ◦ G2 , graph G contains an edge from (u1 , u2 )
to (v1 , v2 ) if and only if u1 = v1 and (u2 , v2 ) ∈ E2 , or (u1 , v1 ) ∈ E1 and u2 = v2 , or (u1 , v1 ) ∈ E1 and
(u2 , v2 ) ∈ E2 .
For example, Hm,2 = Hm,1 × Hm,1 and TC(Hm,2 ) = TC(Hm,1 ) ◦ T C(Hm,1 ), where TC(G) denotes
the transitive closure of G.
Lemma 4.1. Let G1 and G2 be directed graphs with k-TC-spanners S1 and S2 , respectively. Then S1 ◦ S2
is a k-TC-spanner of G = G1 × G2 .
Proof. Suppose (u, v) and (u0 , v 0 ) are comparable vertices in G1 × G2 . Then, by definition of the Cartesian
product, u u0 in G1 and v v 0 in G2 . Let (u1 , u2 , . . . , u` ) be the shortest path in S1 from u = u1 to
u0 = u` , and (v1 , v2 , . . . , vt ) the shortest path in S2 from v = v1 to v 0 = vt . Assume w.t.o.g. that l ≤ t.
Then ((u1 , v1 ), (u2 , v2 ), . . . , (u` , v` ) . . . , (u` , vt )) is a path in S1 ◦ S2 of length t ≤ k, from (u, v) to (u0 , v 0 ).
Therefore, S1 ◦ S2 is a k-TC-spanner of G = G1 × G2 .
Lemma 4.1 together with previous results on the size of k-TC-spanners for the line Hm,1 , summarized
in Lemma 1.7, imply an upper bound on the size of a k-TC-spanner of the directed hypergrid Hm,d :
Corollary 4.2. Let Sk (Hm,d ) denote the number of edges in the sparsest k-TC-spanner of the directed
d-dimensional hypergrid Hm,d . Then Sk (Hm,d ) = O(md λk (m)d cd ) for appropriate constant c.
More precisely, S2 (Hm,d ) ≤ md logd m for m ≥ 3.
7
Proof. Let S be a k-TC-spanner for the line Hm,1 . By Lemma 4.1, S ◦ · · · ◦ S, where the strong graph
product is applied d times, is a k-TC-spanner for the directed grid Hm,d . By definition of the strong graph
product, the number of edges in the resulting spanner is (|E(S)| + m)d − md . Since the number of edges in
the spanner, |E(S)|, is at least m, the main statement follows.
The more precise statement for k = 2 follows from Claim 4.3 below which gives a more careful analysis
of the size of the sparsest 2-TC-spanner of the line: namely, S2 (Hm,1 ) ≤ m log m − m for m ≥ 3.
Claim 4.3. For all m ≥ 3, the directed line Hm,1 has a 2-TC-spanner with at most m log m − m edges.
Proof. Construct graph S on vertex set [m] recursively. First, define the middle node vmid = d m
2 e. Add
edges (v, vmid ) for all nodes v < vmid and edges (vmid , v) for all nodes v > vmid . Then recurse on the two
line segments resulting from removing vmid from the current line. Proceed until each line segment contains
exactly one node. This construction is implicit in, e.g., [?].
S is a 2-TC-spanner for the line Hm,1 , since every pair of nodes u, v ∈ [m] is connected by a path of
length at most 2 via a middle node. This happens in the stage of the recursion where u and v are separated
into different line segments, or one of these two nodes is removed.
There are t = blog mc stages of the recursion, and in each stage i ∈ [t] each node that is not removed
by the end of the this stage connects to the middle node in its current line segment. Since 2i−1 nodes are
removed in the ith stage, exactly m − (2i − 1) edges are added in that stage. Thus, the total number of edges
in S is m · t − (2t+1 − t − 2) ≤ m log m − m. The last inequality holds for m ≥ 3.
4.2
Lower Bound
In this section, we show the lower bound on S2 (Hm,d ) stated in Theorem 1.5. We first treat the special case
of this lower bound for d = 2, since it already contains most of the difficulty of the larger dimensional case.
The extension to arbitrary dimension is presented in the subsequent section.
4.2.1
Lower Bound for d = 2
In this section, we prove a lower bound on the size of a 2-TC-spanner of the 2-dimensional directed grid,
stated in Theorem 4.4. This is a special case of the lower bound in Theorem 1.5.
2 2 log m
Theorem 4.4. Any 2-TC-spanner of the 2-dimensional grid Hm,2 must have Ω mloglog
edges.
m
One way to prove the Ω(m log m) lower bound on the size of a 2-TC-spanner for the directed line Hm,1 ,
m
stated in Lemma 1.7, is to observe that at least
bm2 c edges are cut when the line is halved: namely, at least
one per vertex pair (v, m − v + 1) for all v ∈ b 2 c . Continuing to halve the line recursively, we obtain the
desired bound.
A natural extension of this approach to proving a lower for the grid is to recursively halve the grid
along both dimensions, hoping that each such operation on an m × m grid cuts Ω(m2 log m) edges. This
would imply that the size S(m) of a 2-TC-spanner of the m × m grid satisfies the recurrence S(m) =
4S(m/2) + Ω(m2 log m); that is, S(m) = Ω(m2 log2 m), matching the upper bound in Theorem 1.5.
An immediate problem with this approach is that in some 2-TC-spanners of the grid only O(m2 ) edges
connect vertices in different quarters. One example of such a 2-TC-spanner is the graph containing the
transitive closure of each quarter and only at most 3m2 edges crossing from one quarter to another: namely,
for each node u and each quarter q with vertices comparable to u, this graph contains an edge (u, vq ), where
vq is the smallest node in q comparable to u.
The TC-spanner in the example above is not optimal because it has too many edges inside the quarters.
The first step in our proof of Theorem 4.4 is understanding the tradeoff between the number of edges
8
left nodes
midline
right nodes R
v
u
L
high nodes &
internal edges
low nodes &
internal edges
block
long internal edge
Figure 1: Illustration of the first stage in the proof of Lemma 4.5.
crossing the cut and the number of edges internal to the subgrids, resulting from halving the grid along
some dimension. The simplest manifestation of this tradeoff occurs when a 2 × m grid is halved into two
lines. (In the case of one line, there is no trade off: the Ω(m) bound on the number of crossing edges holds
even if each half-line contains all edges of its transitive closure.) Lemma 4.5 formulates the tradeoff for the
two-line case, while taking into account only edges needed to connect comparable vertices on different lines
by paths of length at most 2:
Lemma 4.5 (Two-Lines Lemma). Let U be a graph with vertex set [2] × [m] that contains a path of length
at most 2 from u to v for every u ∈ {1} × [m] and v ∈ {2} × [m], where u v. An edge (u, v) in U is
2
m
called internal if u1 = v1 , and crossing otherwise. If U contains at most m log
internal edges, it must
32
m log m
contain at least 16 log log m crossing edges.
Note that if the number of internal edges is unrestricted, a 2-TC-spanner of Hm,2 may have only m
crossing edges.
log m
Proof. The proof proceeds in 2 log
log m stages dealing with pairwise disjoint sets of crossing edges. In each
stage, we show that U contains at least m
8 crossing edges in the prescribed set.
In the first stage, divide U into log2 m blocks, each of length logm2 m : namely, a node (v1 , v2 ) is in block i
i
h
i·m
if v2 ∈ (i−1)·m
+
1,
. Call an edge long if it starts and ends in different blocks, and short otherwise.
log2 m
log2 m
Assume, for contradiction, that U contains fewer than m
8 long crossing edges.
Call a node (v1 , v2 ) low if v1 = 1 (high if v1 = 2), and left if v2 ∈ m
2 (right otherwise). Also, call
an edge (u, v) low-internal if u1 = v1 = 1 and high-internal if u1 = v1 = 2. Let L be the set of low left
nodes that are not incident to long crossing edges. Similarly, let R be the set of high right nodes that are not
m
m
incident to long crossing edges. Since there are fewer than m
8 long crossing edges, |L| > 4 and |R| > 4 .
A node u ∈ L can connect to a node v ∈ R via a path of length at most 2 only by using a long internal
edge. Observe that each long low-internal edge can be used by at most logm2 m such pairs (u, v): one low
node u and high nodes v from one block. This is illustrated in Figure 1. Analogously, every long high2
internal edge can be used by at most logm2 m such pairs. Since |L| · |R| > m
16 pairs in L × R connect via
2
2
2
log m
m
paths of length at most 2, graph U contains more than m
= m log
long internal edges, which is
16 ·
m
16
a contradiction.
In each subsequent stage, call blocks used in the previous stage megablocks, and denote their length by
B. Subdivide each megablock into log2 m blocks of equal size. Call an edge long if it starts and ends in
9
different blocks, but stays within one megablock. Assume, for contradiction, that U contains fewer than m
8
long crossing edges.
Call a node (v1 , v2 ) left if it is in the left half of its megablock, that is, if v2 ≤ `+r
2 whenever (v1 , v2 )
is in a megablock [2] × {`, . . . , r}. (Call it right otherwise). Consider megablocks containing fewer than B4
m
long crossing edges each. By an averaging argument, at least 2B
megablocks are of this type. (Recall that
m
there are B megablocks in total). Within each such megablock more than B4 low left nodes and more than
B
4 high right nodes have no incident long crossing edges. By the argument from the first stage, each such
B2
megablock contributes more than 16b
long internal edges, where b = logB2 m is the size of the blocks. Hence
there must be more than
m log2 m
32
B2
16b
·
m
2B
=
m log2 m
32
long internal edges, which is a contradiction to the fact that U
contains at most
internal edges.
We proceed to the next stage until each block is of length 1. Therefore, the number of stages, t, satisfies
log m
m
m
= 1. That is, t = 2 log
log m , and each stage contributes 8 new crossing edges, as desired.
log2t m
Next we generalize Lemma 4.5 to understand the tradeoff between the number of internal edges and
crossing edges resulting from halving a 2-TC-spanner of a 2` × m grid with the usual partial order.
Lemma 4.6. Let S be a 2-TC-spanner of the directed [2`] × [m] grid. An edge (u, v) in S is called internal
2
m
if u1 , v1 ∈ [`] or u1 , v1 ∈ {` + 1, . . . , 2`}, and crossing otherwise. If S contains at most `m log
internal
64
`m log m
edges, it must contain at least 32 log log m crossing edges.
Proof. For each i ∈ [`], we match the lines {i} × [m] and {2` − i + 1} × [m]. Observe that a path of length
at most 2 between the matched lines cannot use any edges with both endpoints in {i + 1, . . . , 2` − i} × [m].
We modify S to ensure that there are no edges with only one endpoint in {i + 1, . . . , 2` − i} × [m] for all
i ∈ [`], and then apply Lemma 4.5 to the matched pairs of lines.
Call the [`] × [m] subgrid and all vertices and edges it contains low, and the remaining {` + 1, . . . , 2`} ×
[m] subgrid and its vertices and edges high. Transform S into S 0 as follows: change each low internal
edge (u, v) to (u, (u1 , v2 )), change each high internal edge (u, v) to ((v1 , u2 ), v), and finally change each
crossing edge ((i1 , j1 ), (2` − i2 + 1, j2 )) to ((i, j1 ), (2` − i + 1, j2 )), where i = min(i1 , i2 ). Intuitively,
we are projecting the edges in S to be fully contained in one of the matched pairs of lines, while preserving
whether the edge is internal or crossing. Crossing edges are projected onto the outer matched pair of lines
chosen from the two pairs that contain the endpoints of a given edge.
Clearly, S 0 contains at most the number of internal (crossing) edges as S. Observe that S 0 contains a
path of length at most 2 from u to v for every comparable pair (u, v) where u is low, v is high, and u and
v belong to the same pair of matched lines. Indeed, since S is a 2-TC-spanner, it contains either the edge
(u, v) or a path (u, w, v). In the first case, S 0 also contains (u, v). In the second case, if (u, w) is a crossing
edge S 0 contains (u, (v1 , w2 ), v), and if (u, w) is an internal edge S 0 contains (u, (u1 , w2 ), v). As claimed,
each edge in S 0 belongs to one of the matched pairs of lines.
2
m
Finally, we apply Lemma 4.5. If S contains at most `m log
internal edges, then so does S 0 , and so at
64
2
m
least half i.e., 2` of the matched line pairs each contain at most m log
internal edges. By Lemma 4.5,
32
log m
each of these pairs contributes at least 16mlogloglogmm crossing edges. Thus S 0 must contain at least 32`m
log log m
crossing edges. Since S contains as many crossing edges as S 0 , the lemma follows.
Now we prove Theorem 4.4 by recursively halving Hm,2 along the horizontal dimension. Some resulting
` × m subgrids may violate Lemma 4.6, but we can guarantee that the lemma holds for a constant fraction
√
of the recursive steps for which ` ≥ m. This is sufficient for obtaining the lower bound in the theorem.
Proof of Theorem 4.4. Assume m is a power of 2 for simplicity.
For each step i ∈ {1, . . . , 21 log m}, partition Hm,2 into the following 2i−1 equal-sized subgrids: {1, . . . , li }
10
×[m], {li + 1, . . . , 2li } × [m], . . . , {m − li + 1, . . . , m} × [m] where li = m/2i−1 . For each of these
subgrids, define internal and crossing edges as in Lemma 4.6. Now, suppose that there exists a step i such
2
m
that at least half of the 2i−1 subgrids have > li m log
internal edges. Since at a fixed i, the subgrids
64
2
2
i−1
2
are disjoint, there are 2 Ω(li m log m) = Ω(m log m) edges in S, proving the theorem. On the other
2
m
hand, suppose that for every i ∈ {1, . . . , 21 log m}, at least half of the 2i−1 subgrids have ≤ li m log
64
log m
internal edges. Then, applying Lemma 4.6, the number of crossing edges in those subgrids is ≥ 32li m
log log m .
Counting overall steps i and forall appropriate
subgrids
from those steps, the number of edges in S is
log m
log2 m
2
2
bounded by Ω m log m log log m = Ω m log log m .
4.2.2
Lower Bound for general d
In this section, we extend the above proof to establish lower bounds on S2 (Hm,d ) for arbitrary d ≥ 2.
The main technical result is a tradeoff lemma between internal and crossing edges with respect to two
(d − 1)-dimensional hyperplanes. An important part of the generalization is the appropriate definition of the
notions of blocks and megablocks, so that the iterative argument in the proof of Lemma 4.5 applies in the
high-dimensional setting.
The following theorem implies the lower bound expression in Theorem 1.5:
Theorem 4.7. Any 2-TC-spanner of Hm,d has at least
logd m
md
32 (2d log log m)d−1
edges.
The main ingredient in the proof is the Two-Hyperplanes Lemma, an analogue of the Two-Lines Lemma
(Lemma 4.5) for d dimensions. The main difficulty in extending the proof of the Two-Lines lemma to work
for two hyperplanes is in generalizing the definitions of blocks and megablocks, so that, on one hand, each
stage in the proof contributes a substantial number of crossing edges and, on the other hand, the crossing
edges contributed in separate stages are pairwise disjoint.
Lemma 4.8 (Two-Hyperplanes Lemma). Let U be a graph with vertex set [2] × [m]d−1 that contains a path
of length at most 2 from u to v for every u ∈ {1} × [m]d−1 and v ∈ {2} × [m]d−1 , where u v. As in
Lemma 4.5, an edge (u, v) in U is called internal if u1 = v1 , and crossing otherwise. Then, if U contains
d−1
d−1 logd m
log m
md−1
less than m
internal
edges,
it
must
contain
≥
crossing edges.
2d+3
8
2d log log m
(d−1)2
Proof. As for Lemma 4.5, the proof proceeds in several stages. The stages are indexed by (d − 1)-tuples i
d−1
log m
log m
d−1 . Then, the number of stages is
−
1}
in {0, 1, . . . , d log
. We show below that each
log m
d log log m
d−1
stage contributes at least m
separate edges to the set of crossing edges, thus proving our lemma.
2d+2
As in the proof of Lemma 4.5, at each stage vertices are partitioned into megablocks and blocks. In
stage i = (i1 , . . . , id−1 ), we partition U into (log m)d(i1 +···+id−1 ) equal-sized megablocks indexed by b =
(b1 , . . . , bd−1 ), where bj ∈ [logd·ij m] for all j h∈ [d − 1].
i
m
m
+ 1, bj di
for each j ∈ [d − 1]. So,
A vertex v is in a megablock b if vj+1 ∈ (bj − 1) di
log j m
log j m
initially when i = ~0, there is only one megablock, and each time i increases by 1 in one coordinate, the
volume of the megablocks shrinks by a factor of logd m.
d
d−1
Each megablock b is further partitioned into (log m)d(d−1) equal-sized
blocks indexed by c ∈ [log
i m] .
h
`j
`j
A vertex v in a megablock b lies in block c if (v − bmin )j+1 ∈ (cj − 1) logd m + 1, cj logd m for each
j ∈ [d − 1], where bmin denotes the smallest vertex contained in megablock b and `j denotes the length
of b in the the j’th dimension. Note that vertices (1, v2 , . . . , vd ) and (2, v2 , . . . , vd ) belong to the same
(mega)block. At the last stage, each block contains only two vertices (differing by the first coordinate).
Next, we specify the set of crossing edges contributed at each stage. A crossing edge (u, v) in U is said
to be long in stage i if:
11
(i) u and v lie in the same megablock, and
(ii) If u lies in block (c1 , . . . , cd−1 ) and v lies in block (c01 , . . . , c0d−1 ), then cj < c0j for all j ∈ [d − 1].
We claim that if i 6= i0 , the sets of long crossing edges in stages i and i0 are disjoint. To see this, let j be an
index such that ij 6= i0j ; suppose without loss of generality that ij < i0j . Then, the length of the megablocks
in the j’th dimension for stage i0 is at most the length of the blocks in the j’th dimension for stage i. Hence,
condition (ii) above implies that long crossing edges in stage i must have endpoints in different megablocks
of stage i0 , and so violate condition (i) for being a long crossing edge in stage i0 .
d−1
It remains to show that every stage contributes at least m
long crossing edges. For the sake of
2d+2
d−1
contradiction, suppose that the number of long crossing edges at some stage i is < m
. Let B =
2d+2
d−1
d(i
+···+i
)
1
d−1
m /(log m)
be the volume of the megablocks restricted to one of the two hyperplanes. By an
d−1
B
averaging argument, at least m2B megablocks contain < 2d+1
long crossing edges (otherwise, there would
be at least
md−1
2d+2
long crossing edges). But we show next that if a megablock contains <
edges, then there are ≥
B logd m
(d−1)22d+2
B
2d+1
long crossing
internal edges with both endpoints inside the megablock. This would
imply that the total number of internal edges is ≥
md−1
2B
B
·
B logd m
(d−1)22d+2
=
md−1 logd m
,
(d−1)22d+3
a contradiction.
Suppose then that a megablock contains < 2d+1 long crossing edges. Let Low be the set of vertices
in the megablock with each coordinate at most the average value of that coordinate in the megablock, and
High the set of vertices with each coordinate greater than the average value of that coordinate. Then
|Low| ≥ 2Bd , |High| ≥ 2Bd , and each vertex in Low is comparable to each vertex in High. By the bound
B
on the number of long crossing edges, there must exist a set L of at least 2d+1
vertices in Low not incident
B
to any long crossing edge, and a set R of at least 2d+1 vertices in High not incident to any long crossing
edges. L lies in the lower hyperplane, R in the upper hyperplane, and each vertex in L is comparable to each
vertex in R. Call a crossing edge short if it satisfies condition (i), but violates condition (ii) above. A path
in U of length at most 2 from a vertex in L to a vertex in R must consist of one internal edge and one short
crossing edge. The number of short crossing edges incident to a given vertex v is at most (d − 1) logBd m , by
counting, for each of the d − 1 block indices, the number of vertices in the megablock that share the value of
that block index with v. So, each internal edge helps connect at most (d − 1) logBd m pairs of vertices. Since
B2
22d+2
pairs of vertices need to be connected by a path, there must exist at least
internal edges.
B2
22d+2
·
logd m
(d−1)B
=
B logd m
(d−1)22d+2
The analogue of Lemma 4.6 in d dimensions (Lemma 4.9) and the rest of the proof of Theorem 4.7 are
straightforward generalizations of the 2-dimensional case.
Lemma 4.9. Let S be a 2-TC-spanner of the directed [2`]×[m]d−1 grid. An edge (u, v) in S is called internal
d−1 logd m
if u1 , v1 ∈ [`] or u1 , v1 ∈ {` + 1, . . . , 2`}, and crossing otherwise. If S contains less than `m
(d−1)22d+3
d−1
d−1
log m
internal edges, it must contain at least ≥ ` m 8
crossing edges.
2d log log m
Proof sketch. We can generalize the proof of Lemma 4.6 in a straightforward way. For each i ∈ [`], instead
of matching the lines, we match the hyperplanes {i} × [m]d−1 and {2` − i + 1} × [m]d−1 .
Proof of Theorem 4.7. Assume m is a power of 2 for simplicity.
For each step i ∈ {1, . . . , 21 log m}, partition Hm,d into the following 2i−1 equal-sized subgrids: {1, . . . , li }
×[m]d−1 , {li +1, . . . , 2li } × [m]d−1 , . . . , {m−li +1, . . . , m}×[m]d where li = m/2i−1 . For each of these
subgrids, define internal and crossing edges as in Lemma 4.9. Now, suppose that there exists a step i such
md−1 logd m
that at least half of the 2i−1 subgrids have ≥ li(d−1)2
internal edges. Since at a fixed i, the subgrids are
2d+3
12
d−1
d
m
log m
=
disjoint, there are at least 2i−2 li(d−1)2
2d+3
md logd m
(d−1)22d+4
edges in S, which is enough to prove the theorem.
On the other hand, suppose that for every i ∈ {1, . . . , 12 log m}, at least half of the 2i−1 subgrids have
<
li md−1 logd m
(d−1)22d+3
internal edges. Then, applying Lemma 4.9, the number of crossing edges in those subgrids
d−1
log m
li md−1
. Counting over all steps i and for all appropriate subgrids from those steps, the
is ≥ 8
2d log log m
d−1
d−1
d
log m
logd m
=m
number of edges in S is lower-bounded by log2m · 2i−2 · li m8
2d log log m
32 (2d log log m)d−1 .
5
2-TC-Spanners of the Hypercube
In this section we prove Theorem 1.6, namely, we analyze the size of the sparsest 2-TC-spanner of the
d-dimensional hypercube Hd . Lemma 5.1 presents the upper bound on S2 (Hd ). Lemma 5.3 presents the
lower bound. The upper and lower bounds differ only by a factor of O(d3 ), and are dominated by the same
combinatorial expression. A numerical approximation to this expression is given in Lemma 5.5. Remark 5.1
at the end of the section explains why our randomized construction in Lemma 5.1 yields a 2-TC-spanner of
Hd of size within O(d2 ) of the optimal.
5.1
Upper Bound
Lemma 5.1. There is a 2-TC-spanner of Hd with O d3 max min
i,j:i<j k:i≤k≤j
(kd)
j−i max
)
(k−i
n k
i
,
d−k
d−j
o
edges.
Proof. Consider the following probabilistic construction that connects all comparable vertices at levels i
and j of Hd by paths of length at most 2:
Given levels i, j ∈ {0, 1, ..., d}, i < j,
1. Initialize the set Ei,j to ∅.
d
n (k )
2. Let ki,j = argmin j−i
max ki ,
k:i≤k≤j (k−i)
d−k
d−j
o
.
(kd)
j−i vertices chosen uniformly at random from the set of
(k−i
)
in weight level k = ki,j .
3. Let Si,j be a set of 3d
d
k
vertices that are
4. For each vertex v ∈ Si,j , set Ei,j to Ei,j ∪ {(x, v) : |x| = i ∧ x ≺ v} ∪ {(v, y) : |y| = j ∧ v ≺ y}.
That is, connect v to all comparable vertices in levels i and j.
5. Output Ei,j .
Claim 5.2. For all 0 ≤ i < j ≤ d, with probability at least 21 , Ei,j contains a path of length at most 2
between any pair of vertices (x, y) such that x ≺ y, |x| = i, and |y| = j.
Proof. Consider any particular pair of vertices (x, y) such that x ≺ y, |x| =
i, and |y| = j. The number
j−i
of vertices in level k that are greater than x and less than y is exactly k−i
. So, the probability that Si,j
d
(k )
d3d ( j−i )
j−i
k−i ≤ e−3d . The number of comparable pairs (x, y)
does not contain such a vertex is: 1 − k−i / k
d−i
is di d−j
. So, by the union bound, the probability that there exists an (x, y) such that no vertex v ∈ Si,j
d−i −3d
satisfies x ≺ v ≺ y is at most di d−j
e
≤ 22d e−3d < 12 .
13
So, for every i and j, there exists a choice of Si,j such that comparable pairs from the two weight levels
∗ be the set of edges returned by the algorithm when this
are connected by a path of length at most 2. Let Ei,j
S
∗
Si,j is chosen. We set E = 0≤i<j≤d Ei,j . By Claim 5.2, ({0, 1}d , E) is a 2-TC-spanner of Hd .
Now, we show that the size of E is as claimed in the lemma statement. The main observation is that in
step (4), for any specific v ∈ Si,j , |{(x, v) : |x| = i ∧ x ≺ v} ∪ {(v, y) : |y| = j ∧ v ≺ y}| is exactly
ki,j i,j
+ d−k
. Therefore, for all 0 ≤ i < j ≤ d,
i
d−j
d
d
k
d−k
k
d−k
∗
k
k
+
≤ 6d min j−i max
,
.
|Ei,j | ≤ 3d min j−i k:i≤k≤j
k:i≤k≤j
i
d−j
i
d−j
k−i
k−i
P
∗ |, where the sum has O(d2 ) terms, the claimed bound follows.
Since |E| = 0≤i<j≤d |Ei,j
5.2
Lower Bound
Lemma 5.3. Any 2-TC-spanner of Hd has Ω
max min
i,j:i<j k:i≤k≤j
(kd)
j−i max
(k−i
)
n k
i
,
d−k
d−j
o
edges.
Proof. Let S be a 2-TC-spanner for Hd . We will count the edges in S that occur on paths connecting
two particular weight levels of Hd . Let Pi,j be the pairs {(v1 , v2 ) : |v1 | = i, |v2 | = j, v1 ≺ v2 }. We
will lower bound e∗i,j , the number of edges in the paths of length at most 2 in S that connect the pairs
Pi,j . Let ek,` denote the number of edges in S that connect vertices in level k to vertices in level `. Then
Pj−1
e∗i,j = ei,j + k=i+1
(ei,k + ek,j ).
We say that a vertex v covers a pair of vertices (v1 , v2 ) if S contains the edges (v1 , v) and (v, v2 ) or, for
(k)
the special case v = v1 , if S contains (v1 , v2 ). Let Vi,j be the set of vertices of weight k that cover pairs in
(k)
Pi,j . Let αk be the fraction of pairs in Pi,j that are covered by a vertex in Vi,j . Since each pair in Pi,j must
Pj−1
be covered by a vertex in levels i to j − 1,
k=i αk ≥ 1.
(k)
For any vertex v ∈ Vi,j , let inv be the number of incoming edges from vertices of weight i incident
to v and let outv be the number of outgoing edges to vertices of weight j incident to v. For each k ∈
(k)
{i + 1, ..., j − 1}, since each vertex v ∈ Vi,j covers inv · outv pairs,
X
d
d−i
inv · outv ≥ αk |Pi,j | = αk
.
(1)
i
d−j
(k)
v∈Vi,j
P
We upper bound v∈V (k) inv · outv as a function of ei,k + ek,j , and then use Equation (1) to lower bound
i,j
ei,k + ek,j .
For all k ∈ {i + 1, ..., j − 1}, variables inv and outv satisfy the following constraints:
X
X
inv ≤ ei,k + ek,j ,
outv ≤ ei,k + ek,j .
(k)
v∈Vi,j
(k)
v∈Vi,j
k
d−k
(k)
(k)
inv ≤
∀v ∈ Vi,j , outv ≤
∀v ∈ Vi,j .
i
d−j
The last two constraints hold because inv and outv count the number of edges to a vertex of weight k from
from vertices of weight i and from a vertex of weight k to vertices of weight j, respectively. Using these
bounds we obtain
X
X
X k k
k
inv · outv ≤
· outv =
·
outv ≤
· (ei,k + ek,j ).
i
i
i
(k)
(k)
(k)
v∈Vi,j
v∈Vi,j
v∈Vi,j
14
Similarly,
P
(k)
v∈Vi,j
inv · outv ≤
X
d−k
d−j
· (ei,k + ek,j ). Therefore, for all k ∈ {i + 1, ..., j − 1}:
inv · outv ≤ (ei,k + ek,j ) min
(k)
k
d−k
,
.
i
d−j
v∈Vi,j
Let si,k,j =
d−i
(d)(d−j
) o
. From Equation (1), ei,k + ek,j ≥ αk si,k,j for all k ∈ {i + 1, ..., j − 1}.
k
d−k
min ( i ),( d−j )
ni
Therefore,
e∗i,j
= ei,j +
j−1
X
j−1
j−1
X
X
d
d−i
+
αk si,k,j ≥
αk si,k,j ≥ min si,k,j
(ei,k + ek,j ) ≥ αi
k:i≤k≤j
i
d−j
k=i+1
k=i+1
k=i
Since this holds for arbitrary i and j, the number of edges in the 2-TC-spanner
|S| ≥ max min si,k,j .
i,j:i<j k:i≤k≤j
Finally, a simple algebraic manipulation finishes the proof.
n o
(kd)
.
Claim 5.4. si,k,j = j−i
max ki , d−k
d−j
(k−i)
Proof. Take the ratio of the two sides:
si,k,j
n d
(k )
k
max
j−i
i ,
(k−i
)
d−k
d−j
o =
d
i
d−i j−i
d−j k−i
d k d−k
k i d−j
d d−i j−i
i j−i k−i
d k d−k
k i j−k
=
= 1.
The first equality follows from the fact that max(x, y) · min(x, y) = x · y. The last equality
can bej−iproved
either by expanding the binomial coefficients into factorials, or by realizing that both di d−i
j−i k−i and
d k d−k
k i j−k count the number of ways i red balls, j − k blue balls, and k − i green balls can be placed into
d slots, each of which can hold one ball at most. This completes the proof of the claim.
This completes the proof of the lemma.
The following lemma gives a handle on the expression capturing the size of a 2-TC-Spanner.
n o
(kd)
Lemma 5.5. Let s = max min j−i
max ki , d−k
. Then s = 2cd , where c ≈ 1.1620.
d−j
i,j:i<j k:i≤k≤j (k−i)
n
Proof. We use the fact that cn
= 2(Hb (c)−on (1))n , where “on (1)” is a function of n that tends to zero as
n tends to infinity, and Hb (p) = −p log p − (1 − p) log(1 − p) is the binary entropy function. Substituting
i = αd, j = βd and k = γd in the resulting expression for s, and taking the logarithm of both sides, we get
γ−α
α
1−β
log2 s = max min Hb (γ) − Hb
(β − α) + max Hb
γ, Hb
(1 − γ) d
0≤α<β≤1 α≤γ≤β
β−α
γ
1−γ
In other words, log2 s = cd where c is a constant. We can check numerically that c ≈ 1.1620.
Remark 5.1. We note that if the first maximum in the expression for s is replaced with the sum then
Lemma 5.1 holds for O(d · s) instead of O(d3 · s) while Lemma 5.3 holds for Ω(d/s) instead of Ω(s).
The proofs of these modified statements are similar. (We do not have an analogue of Lemma 5.5 for the
modified expression for s.) Observe that the modified bounds differ by a factor of O(d2 ) instead of O(d3 ).
This demonstrates that our randomized construction yields a 2-TC-spanner of Hd of size within O(d2 ) of
the optimal. ♦
15
6
2-TC-Spanners of the Hypergrid
In this section, we generalize the arguments for the hypercube (Section 5) to the directed hypergrid, Hm,d ,
to find the size of the sparsest 2-TC-spanner for Hm,d to within poly(d) factors. This result supersedes the
results of Section 4 when, for instance, m is constant and d is growing. The expression we obtain can be
evaluated numerically for small m using standard approximations of binomial coefficients. For example,
this was done in Lemma 5.5 for the case m = 2.
Before stating Theorem 6.1, we introduce some notation.
Definition 6.1. For the hypergrid Hm,d , define a level to be a set of vertices, indexed by vector i ∈ [d]m
with i1 + · · · + im = d, that consists of vertices x = (x1 , . . . , xd ) ∈ [m]d containing i1 positions of value
1, i2 positions of value 2, . . . , and im positions of value m.
Notice that the number of vertices in level i = (i1 , i2 , . . . , im ) is the multinomial coefficient
P
d − m−1
d − i1 − i2
d
d − i1
d
d
l=1 il
.
...
=
=
im
i3
i2
i1
i
i1 , ..., id
1
Indeed, there are id1 choices for the coordinates of value 1. For each such choice there are d−i
choices
i2
for the coordinates of value 2, and repeating this argument one obtains the above expression.
For levels i, j ∈ [d]m , say j majorizes i, denoted j i, if j contains a vertex which is above some vertex
m
m
X
X
in i, i.e., , if
j` ≥
i` for all t ∈ {m, m − 1, ..., 1}.
`=t
`=t
For j i, the number of vertices y at level i comparable to a fixed vertex x at level j is M(i, j):
Pm Pm
jm
jm + jm−1 − im
jm + jm−1 + jm−2 − im − im−1
l=2 il
l=1 jl −
.
...
im
im−1
i1
im−2
m
choices for the coordinates of value m in y. For each such choice, there are
Indeed, there are jim
jm +jm−1 −im
choices for the coordinates of value m − 1 in y, and one can repeat this argument to obim−1
tain the claimed expression.
For j i, the number of vertices y at level j comparable to a fixed vertex x at level i is
M(i, j) dj
N (i, j) =
.
d
i
d
Indeed, there are M(i, j) j comparable pairs of vertices in levels i and j, and level i contains di vertices.
Since, by symmetry, each vertex in i is comparable to the same number of vertices in level j, we get the
desired expression.
Theorem 6.1. Let
B(m, d) = max
min
i,j:ji k:i≺k≺j
M(i, j)
d
j
M(i, k)N (k, j)
max {M(i, k), N (k, j)} .
Then the number of edges in the sparsest 2-TC-spanner of the directed hypergrid Hm,d is
O d2m B(m, d) and Ω (B(m, d)).
The bounds stated in Theorem 6.1 are presented separately as Lemma 6.2 (upper bound) and Lemma 6.4
(lower bound) below.
16
6.1
Upper Bound
Lemma 6.2. There is a 2-TC-spanner of Hm,d with
2m
O d
max
min
i,j:ji k:i≺k≺j
M(i, j)
d
j
!
M(i, k)N (k, j)
max {M(i, k), N (k, j)}
edges.
Proof. Let v ∈ i denote that vertex v belongs to level i. Consider the following probabilistic construction
that connects comparable vertices at levels i and j of Hm,d by paths of length at most 2:
Given levels i, j ∈ [m]d , j i,
1. Initialize the set Ei,j to ∅.
M(i,j)(dj )
2. Let ki,j = argmin M(i,k)N (k,j) max {M(i, k), N (k, j)} .
k:i≺k≺j
M(i,j)(dj )
3. Let Si,j be a set of dm M(i,k)N (k,j)
vertices chosen uniformly at random from the set of
that are in weight level k = ki,j .
d
k
vertices
4. For each vertex v ∈ Si,j , set Ei,j to Ei,j ∪ {(x, v) : x ∈ i ∧ x ≺ v} ∪ {(v, y) : y ∈ j ∧ v ≺ y}. That
is, connect v to all comparable vertices in levels i and j.
5. Output Ei,j .
Claim 6.3. For all i ≺ j, with probability at least 12 , Ei,j contains a path of length at most 2 between any
pair of vertices (x, y) such that x ≺ y, x ∈ i, and y ∈ j.
Proof. Fix x, y with x ≺ y, and assume x ∈ i, and y ∈ j. We will first show that P rv∈k [x ≺ v ≺ y] ≥ p,
where p = M(i,k)N (k,j)
.
M(i,j)(dj )
Toward that end, notice that there are M(i, j) dj pairs of comparable vertices (u, w) with u ∈ i, w ∈ j.
Each vertex in Si,j connects exactly M(i, k)N (k, j) pairs of nodes from levels i and j. It is enough to
show that for any such pair (u, w), the number of vertices at level k that are comparable to both u and v is
independent of u, w, i.e., that number only depends on the levels i, k, j and it is therefore the same for all
such pairs. To see that, for a vertex u ∈ z, denote by Tl (u) the set of positions of value l in u. Notice
that
jm −im
|Tl (u)| = zl . For x ≺ v ≺ y it is the case that Tm (x) ⊆ Tm (v) ⊆ Tm (y). Hence there are km −im choices
for the m-values in the vectorv. Similarly, we must have Tm−1 (x) ⊆ Tm−1 (v) ⊆ Tm (y) ∪ Tm−1 (y). Hence
−km −im−1
there are jm +jkm−1
choices for the values m − 1 in v. Repeating this process, we obtain that the
m−1 −im−1
number of possible v’s does not depend on the particular choice of x and y.
m
m
Thus the probability that Si,j does not contain such a vertex v with x ≺ v ≺ y is (1 − p)d /p ≤ e−d .
The number of comparable pairs (x, y) is at most m2d , and by the union bound, the probability that there
m
exists (x, y) such that there is no v ∈ Si,j with x ≺ v ≺ y is at most m2d e−d < 1/2.
So, for every i and j, there exists a choice of Si,j such that comparable pairs from the two weight levels
∗ be the set of edges returned by the algorithm when this
are connected by a path of length at most 2. Let Ei,j
S
∗ . By Claim 6.3, ([m]d , E) is a 2-TC-spanner of H
Si,j is chosen. We set E = i<j Ei,j
m,d .
Now, we show that the size of E is as claimed in the lemma statement. The main observation is that
in step (4), for any specific v ∈ Si,j , |{(x, v) : x ∈ i ∧ x ≺ v} ∪ {(v, y) : y ∈ j ∧ v ≺ y}| is exactly
M(i, k) + N (k, j).
17
The claimed bound follows since |E| =
6.2
∗
ji |Ei,j |,
P
where the sum has dm terms.
Lower Bound
Lemma 6.4. Any 2-TC-spanner of Hm,d has at least Ω(B(m, d)) many edges, where B(m, d) is defined as
in Theorem 6.1.
Proof. Let S be a 2-TC-spanner for Hm,d . We count the edges in S that occur on paths connecting two
particular levels of Hm,d . Let Pi,j = {(v1 , v2 ) : v1 ∈ i, v2 ∈ j, v1 ≺ v2 }. We will lower bound e∗i,j , the
number of edges in the paths of length at most 2 in S, that connect the pairs Pi,j . Notice that |P (i, j)| =
d
j M(i, j).
Let ek,` denote the number of edges in S that connect vertices in level k to vertices in level `. Then
X
(ei,k + ek,j ).
(2)
e∗i,j = ei,j +
i≺k≺j
We say that a vertex v covers a pair of vertices (v1 , v2 ) if S contains the edges (v1 , v) and (v, v2 ) or, for
(k)
the special case v = v1 , if S contains (v1 , v2 ). Let Vi,j be the set of vertices in level k that cover pairs in
(k)
Pi,j . Let αk be the fraction of pairs in Pi,j that are covered by the vertices
P in Vi,j . Since each pair in Pi,j
must be covered by a vertex in levels k with i ≺ k ≺ j, we must have i≺k≺j αk ≥ 1.
(k)
For any vertex v ∈ Vi,j , let inv be the number of incoming edges from vertices of level i incident to
v and let outv be the number of outgoing edges to vertices of level j incident to v. For each level k with
(k)
i ≺ k ≺ j, since each vertex v ∈ Vi,j covers inv · outv pairs,
d
inv · outv ≥ αk |Pi,j | ≥ αk M(i, j)
.
j
(k)
X
(3)
v∈Vi,j
We upper bound
P
(k)
v∈Vi,j
inv · outv as a function of ei,k + ek,j , and then use Equation (3) to lower
bound ei,k + ek,j . For all k with i ≺ k ≺ j, variables inv and outv satisfy the following constraints:
X
X
inv ≤ ei,k ≤ ei,k + ek,j ,
outv ≤ ek,j ≤ ei,k + ek,j ,
(k)
(k)
v∈Vi,j
v∈Vi,j
(k)
(k)
inv ≤ M(i, k) ∀v ∈ Vi,j , outv ≤ N (k, j) ∀v ∈ Vi,j .
The last two constraints hold because inv and outv count the number of edges to a vertex of level k from
vertices of level i, and from a vertex of level k to vertices of level j, respectively. Using these bounds we
obtain
X
X
X
inv · outv ≤
M(i, k) · outv = M(i, k) ·
outv ≤ M(i, k) · (ei,k + ek,j ).
(k)
(k)
v∈Vi,j
Similarly,
P
(k)
v∈Vi,j
(k)
v∈Vi,j
v∈Vi,j
inv · outv ≤ N (k, j) · (ei,k + ek,j ). Therefore,
X
inv · outv ≤ (ei,k + ek,j ) min {M(i, k), N (k, j)} .
(k)
v∈Vi,j
18
d
1
From Equation (3), ei,k + ek,j ≥ αk M(i, j)
for all i ≺ k ≺ j. Applying
min
{M(i,
k), N (k, j)}
j
P
Equation (2) and the fact that i≺k≺j αk ≥ 1, we get
1
d
M(i, j)
min {M(i, k), N (k, j)}
j
i≺k≺j
k
1
d
≥ min
M(i, j)
k min {M(i, k), N (k, j)}
j
d
1
M(i, j)
max {M(i, k), N (k, j)}.
= min
k M(i, k)N (k, j)
j
e∗i,j = ei,j +
X
(ei,k + ek,j ) ≥
X
αk
Since this holds for arbitrary i and j, the size of the 2-TC-spanner is |S| ≥ B(m, d).
19