-
1.2 (b(a))
Suppose, all vertices in the shortest path P between x and y in graph G lie in Vε(D/2+1).
It implies that the distance between any consecutive pair of vertices in P is at most
ε(D/2 + 1) in G. I would like to show that there exists a vertex in V , the distance of hop
of which from both x and y in graph H is at most ⌈1/ε⌉.
Take into account any vertex z ∈ P . Since P is comprised of vertices lying in Vε(D/2+1),
we know that N (z, ε(D/2 + 1)) ⊆ B(z, n^a) owing to the definition of Vℓ. Hence, for any
vertex v ∈ N (z, ε(D/2 + 1)), an edge is there from z to v in graph H with weight
dist(z, v, G).
Let’s examine the hop-distance of z in graph H from both x and y. The distance between
z and x in graph H is at most the distance between z and the closest vertex in R, which
is p(z), plus the weight of the edge from z to p(z). Because all vertices in P lie in
Vε(D/2 + 1), we have:
dist(z, p(z), G) ⩽ ε(D/2 + 1),
and the edge weight is dist(z, p(z), G). Hence, the distance between z and x in graph H
is at most 2ε(D/2 + 1) = εD.
In a similar way, the distance between z and y in graph H is also at most εD.
Because z was an arbitrary vertex in the shortest path P , this implies that for any vertex
z in P , its hop-distance from both x and y in graph H is at most εD.
To convince the order that the hop-distance from both x and y in graph H is at most
⌈1/ε⌉, we need εD ⩽ ⌈1/ε⌉, which provides us D ⩽ ⌈1/ε2⌉.
1
1.2.1 b(b)
Suppose, the path P contains a vertex from V \ Vε(D/2 + 1). This implies that there is
at least one vertex in P that lies outside of Vε(D/2 + 1), and I would like to show that
there exists a vertex in V \ Vε(D/2 + 1) whose hop distance from either x or y in graph
H is at most ⌈1/ε⌉.
Now, let’s signify this vertex by z. Because z lies outside of Vε(D/2 + 1), I have
dist(x, z, G) > ε(D/2 + 1) or dist(y, z, G) > ε(D/2 + 1). Without the loss of generality,
assume that dist(x, z, G) > ε(D/2 + 1).
Now, taking into account the set N (x, ε(D/2 + 1)) in graph G. Because z is outside of
this set, it implies that z is not within distance ε(D/2 + 1) from x in graph G. But, by
definition of Vℓ, I know that N (x, ε(D/2 + 1)) ⊆ B(x, n^a). Hence, z cannot be within
distance n^a from x.
This implies that z is at a distance greater than n^a from x in graph G. Since z is on the
shortest path P , this implies that there must be a vertex v in P that lies in the path
between x and z such that dist(x, v, G) ⩽ n^a.
Let’s now consider the edge between v and z in graph H. The weight of this edge is
dist(v, z, G), which is less than or equal to n^a. Furthermore, the distance between x and
v in graph H is at most n^a because of the above argument.
This implies that the hop-distance of v from x in graph H is at most n^a, which is at most
n^1/2 since a ⩽ 1/2.
So, in both cases (whether dist(x, z, G) > ε(D/2 + 1) or dist(y, z, G) > ε(D/2 + 1)), I
have found a vertex v (which may be x or another vertex in P ) in V \ Vε(D/2 + 1) whose
hop distance from either x or y in graph H is at most ⌈1/ε⌉.
Explain how to use above two parts to design an oracle of O(n^2−a log n) size that
for any given x, y ∈ V reports a (1 + ϵ, 2)-approximation to (x, y) distance in G in O(n^a⌈1/ϵ⌉)time. (Hint: Use truncated BFS traversal in graph H from x and y).