A new infinity of distance oracles for sparse graphs

TY - GEN

T1 - A new infinity of distance oracles for sparse graphs

AU - Patrascu, Mihai

AU - Roditty, Liam

AU - Thorup, Mikkel

N1 - Conference code: 53

PY - 2012

Y1 - 2012

N2 - Given a weighted undirected graph, our basic goal is to represent all pair wise distances using much less than quadratic space, such that we can estimate the distance between query vertices in constant time. We will study the inherent trade-off between space of the representation and the stretch (multiplicative approximation disallowing underestimates) of the estimates when the input graph is sparse with m= Õ(n) edges. In this paper, for any fixed positive integers k and ℓ, we obtain stretches α=2k+1±2/ℓ = 2k+1-2/ℓ, 2k+1+2/ℓ, using space S(α, m) = Õ(m 1+2/(α+1)). The query time is O(k+ℓ)=O(1). For integer stretches, this coincides with the previous bounds (odd stretches with ℓ=1 and even stretches with ℓ=2). The infinity of fractional stretches between consecutive integers are all new (even though ℓ is fixed as a constant independent of the input, the number of integers ℓ is still countably infinite). % We will argue that the new fractional points are not just arbitrary, but that they, at least for fixed stretches below 3, provide a complete picture of the inherent trade-off between stretch and space in m. Consider any fixed stretch α < 3. Based on the hardness of set intersection, we argue that if ℓ is the largest integer such that 3-2/ℓ ≤ α, then Ω(S(3 - 2/ℓ, m)) space is needed for stretch α. In particular, for ?xed stretch below 2 2/3, we improve Pǎtraşcu and Roditty's lower bound from Ω(m3/2) to Ω(m5/3), thus matching their upper bound for stretch 2. For space in terms of m, this is the first hardness matching the space of a non-trivial/sub-quadratic distance oracle.

AB - Given a weighted undirected graph, our basic goal is to represent all pair wise distances using much less than quadratic space, such that we can estimate the distance between query vertices in constant time. We will study the inherent trade-off between space of the representation and the stretch (multiplicative approximation disallowing underestimates) of the estimates when the input graph is sparse with m= Õ(n) edges. In this paper, for any fixed positive integers k and ℓ, we obtain stretches α=2k+1±2/ℓ = 2k+1-2/ℓ, 2k+1+2/ℓ, using space S(α, m) = Õ(m 1+2/(α+1)). The query time is O(k+ℓ)=O(1). For integer stretches, this coincides with the previous bounds (odd stretches with ℓ=1 and even stretches with ℓ=2). The infinity of fractional stretches between consecutive integers are all new (even though ℓ is fixed as a constant independent of the input, the number of integers ℓ is still countably infinite). % We will argue that the new fractional points are not just arbitrary, but that they, at least for fixed stretches below 3, provide a complete picture of the inherent trade-off between stretch and space in m. Consider any fixed stretch α < 3. Based on the hardness of set intersection, we argue that if ℓ is the largest integer such that 3-2/ℓ ≤ α, then Ω(S(3 - 2/ℓ, m)) space is needed for stretch α. In particular, for ?xed stretch below 2 2/3, we improve Pǎtraşcu and Roditty's lower bound from Ω(m3/2) to Ω(m5/3), thus matching their upper bound for stretch 2. For space in terms of m, this is the first hardness matching the space of a non-trivial/sub-quadratic distance oracle.

U2 - 10.1109/FOCS.2012.44

DO - 10.1109/FOCS.2012.44

M3 - Article in proceedings

SN - 978-1-4673-4383-1

SP - 738

EP - 747

BT - 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)

PB - IEEE

T2 - IEEE 53rd Annual Symposium on Foundations of Computer Science

Y2 - 20 October 2012 through 23 October 2012

ER -