Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs

A (1+ε)-stretch tree cover of an edge-weighted n-vertex graph G is a collection of trees, where every pair of vertices has a (1+ε)-stretch path in one of the trees. The celebrated Dumbbell Theorem by Arya et. al. [STOC’95] states that any set of n points in d-dimensional Euclidean space admits a (1+ε)-stretch tree cover with a constant number of trees, where the constant depends on ε and the dimension d. This result was generalized for arbitrary doubling metrics by Bartal et. al. [ICALP’19]. While the total number of edges in the tree covers of Arya et. al. and Bartal et. al. is O(n), all known tree cover constructions incur a total lightness of Ω(logn); whether one can get a tree cover of constant lightness has remained a longstanding open question, even for 2-dimensional point sets. In this work we resolve this fundamental question in the affirmative, as a direct corollary of a new construction of (1+ε)-stretch spanning tree cover for doubling graphs; in a spanning tree cover, every tree may only use edges of the input graph rather than the corresponding metric. To the best of our knowledge, this is the first constant-stretch spanning tree cover construction (let alone for (1+ε)-stretch) with a constant number of trees, for any nontrivial family of graphs. Concrete applications of our spanning tree cover include: - A (1+ε)-stretch tree cover construction, where both the number of trees and lightness are bounded by O(1), for doubling graphs. In doubling metrics, we can also bound the maximum degree of each vertex by O(1) (which is impossible in doubling graphs). - A compact (1+ε)-stretch routing scheme in the labeled model for doubling graphs, which uses the asymptotically optimal (up to the dependencies on ε and d) bound of O(logn) bits on all the involved measures (label, header, and routing tables sizes). This is a significant improvement over the works of Chan et. al. [SODA’05], Abraham et. al. [ICDCS’06], Konjevod et. al. [SODA’07], where the local memory usage either depends on the aspect ratio of the graph or is Ω(log3 n). - The first path-reporting distance oracle for doubling graphs achieving optimal bounds for all important parameters: O(n) space, (1+ε)-stretch, and O(1) query time for constant d and ε.