Optimal Distance Labeling Schemes for Trees

Labeling schemes seek to assign a short label to each node in a network, so that a function on two nodes (such as distance or adjacency) can be computed by examining their labels alone. For the particular case of trees, following a long line of research, optimal bounds (up to low order terms) were recently obtained for adjacency labeling [FOCS '15], nearest common ancestor labeling [SODA '14], and ancestry labeling [SICOMP '06]. In this paper we obtain optimal bounds for distance labeling. We present labels of size 1/4\log^2n+o(\log^2n), matching (up to low order terms) the recent 1/4\log^2n-\Oh(\log n) lower bound [ICALP '16].

Prior to our work, all distance labeling schemes for trees could be reinterpreted as universal trees. A tree T is said to be universal if any tree on $n$ nodes can be found as a subtree of T. A universal tree with |T| nodes implies a distance labeling scheme with label size \log |T|. In 1981, Chung et al. proved that any distance labeling scheme based on universal trees requires labels of size 1/2\log^2 n -\log n \cdot \log\log n+\Oh(\log n). Our scheme is the first to break this lower bound, showing a separation between distance labeling and universal trees.

The θ (log^{2 n}) barrier for distance labeling in trees has led researchers to consider distances bounded by k. The size of such labels was shown to be \log n+\Oh(k\sqrt{\log n}) in [WADS '01], and then improved to \log n+\Oh(k^2(\log(k\log n)) in [SODA '03] and finally to \log n+\Oh(k\log(k\log(n/k))) in [PODC '07]. We show how to construct labels whose size is the minimum between \log n+\Oh(k\log((\log n)/k)) and \Oh(\log n \cdot \log(k/\log n)). We complement this with almost tight lower bounds of \log n+\Omega(k\log(\log n / (k\log k))) and \Omega(\log n \cdot \log(k/\log n)). Finally, we consider (1+\eps)-approximate distances. We show that the recent labeling scheme of [ICALP '16] can be easily modified to obtain an \Oh(\log(1/\eps)\cdot \log n) upper bound and we prove a matching \Omega(\log(1/\eps)\cdot \log n) lower bound.