Approximate distance queries and compact routing in sparse graphs

An approximate distance query data structure is a compact representation of a graph, and can be queried to approximate shortest paths between any pair of vertices. Any such data structure that retrieves stretch 2k Ω 1 paths must require space Ω(n^1+1/k) for graphs of n nodes. The hard cases that enforce this lower bound are, however, rather dense graphs with average degree Ω(n^1/k).

I. Introduction

An approximate distance query (ADQ) data structure is a compact representation of a graph that allows retrieval of an approximate distance between any two vertices in the graph. The fundamental trade-off in constructing an ADQ structure is between its size and its stretch: the worst-case ratio of the distance returned by the data structure to the actual shortest distance between the two vertices. For general graphs, the optimal¹

For and , the lower bound relies on a conjecture of Erdos.

space/stretch trade-off was achieved by Thorup and Zwick [1]: their ADQ structure, for any graph with vertices and for any integer , is of size and returns paths with stretch in time . However, the hard instances for the matching lower bound are rather dense graphs, with average degree . The lower bound essentially states that there exist graphs that are incompressible: if a certain stretch is desired, then the size of the data structure is lower bounded by the number of edges in the specially-constructed graph.