2021/12/16 by Le, Hung, Milenkovic, Lazar, Solomon, Shay · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2112.09124
In STOC'95 [ADMSS'95] Arya et al. showed that any set of n points in \mathbb Rd admits a (1+ε)-spanner with hop-diameter at most 2 (respectively, 3) and O(n log n) edges (resp., O(n log log n) edges). They also gave a general upper bound tradeoff of hop-diameter at most k and O(n αk(n)) edges, for any k ≥ 2. The function αk is the inverse of a certain Ackermann-style function at the \lfloor k/2 \rfloorth level of the primitive recursive hierarchy, where α0(n) = \lceil n/2 \rceil, α1(n) = \lceil √(n) \rceil, α2(n) = \lceil logn \rceil, α3(n) = \lceil loglogn \rceil, α4(n) = log^* n, α5(n) = \lfloor (1)/(2) log^*n \rfloor, …. Roughly speaking, for k ≥ 2 the function αk is close to \lfloor (k-2)/(2) \rfloor-iterated log-star function, i.e., log with \lfloor (k-2)/(2) \rfloor stars. Also, α2α(n)+4(n) ≤ 4, where α(n) is the one-parameter inverse Ackermann function, which is an extremely slowly growing function. Whether or not this tradeoff is tight has remained open, even for the cases k = 2 and k = 3. Two lower bounds are known: The first applies only to spanners with stretch 1 and the second is sub-optimal and applies only to sufficiently large (constant) values of k. In this paper we prove a tight lower bound for any constant k: For any fixed ε> 0, any (1+ε)-spanner for the uniform line metric with hop-diameter at most k must have at least Ω(n αk(n)) edges.