Succinct Oracles for Exact Distances in Undirected Unweighted Graphs

Let G be an unweighted and undirected graph of n nodes, and
let D be the n x n matrix storing the All-Pairs-Shortest-Path distances
in G. Since D contains integers in [n], its plain storage takes n^2log (n + 1)
bits. However, a simple counting argument shows that n^2/2
bits are necessary to store D. In this paper we investigate the question
of finding a succinct representation of D that requires O(n^2) bits of
storage and still supports constant-time access to each of its entries.
This is asymptotically optimal in the worst case, and far from the
information-theoretic lower-bound by a multiplicative factor
log 3 \simeq 1.585. As a result O(1) bits per pairs of
nodes in G are enough to retain constant-time access to their
shortest-path distance. We achieve this result by reducing the
storage of D to the succinct storage of labeled trees
and ternary sequences, for which we properly adapt and orchestrate
the use of known compressed data structures.