Optimal Distance Labeling Schemes for Trees

We resolve the complexity of distance labeling schemes for trees. For arbitrary distances, we show how to assign labels of $1/4\log^2n+o(\log^2n)$ bits to every node so that we can determine the distance between any two nodes given only their two labels. This closes the line of research initiated by Gavoille et al. [SODA '01] who gave an $O(\log^2n)$ bits upper bound and a $1/8\log^2n-O(\log n)$ bits lower bound, and followed by Alstrup et al. [ICALP '16] who gave a $1/2 \log^2 n + O(\log n)$ bits upper bound and a $1/4\log^2n-O(\log n)$ bits lower bound. Next, for distances bounded by $k$, we show how to construct labels whose length is the minimum between $\log n+O(k\log(\log n/k))$ and $O(\log n \cdot \log(k/\log n))$. The query time in both cases is constant. We complement our upper bounds 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))$. This line of research was initiated by Kaplan and Milo [WADS '01] who constructed labels of length $\log n+O(k\sqrt{\log n})$, and followed by the $\log n+O(k^2(\log(k\log n))$ labeling scheme of Alstrup, Bille, and Rauhe [SODA '03] whose query-time is $O(k^2)$ and the $\log n+O(k\log(k\log(n/k)))$ labeling scheme of Gavoille and Labourel [PODC '07] whose query-time is $O(k)$. Finally, we consider $(1+\epsilon)$-approximate distances. We prove an $O(\log(1/\epsilon)\cdot \log n)$ upper bound and a matching $\Omega(\log(1/\epsilon)\cdot \log n)$ lower bound. This improves the recent $O(1/\epsilon \cdot \log n)$ upper bound of Alstrup et al. [ICALP '16].