Sharing Helps in Labeling Trees

We resolve the space complexity of labeling schemes for two closely related problems on trees to within lower order terms: the tree distance labeling problem and the level-ancestor labeling problem. In the tree distance labeling problem we are asked to generate labels (i.e., bit strings) for each node in a tree so that, given the labels of two arbitrary nodes u and v, we can compute the distance between u and v. In the level-ancestor labeling problem we are asked to generate distinct labels for each node in a rooted tree so that, given the label of a node u at depth k, we can return the label of the j-th ancestor of u for any j in [1,k-1]. In both problems the goal is to generate labels that minimize the maximum length.