Optimal root recovery for uniform attachment trees and d-regular growing trees

2024/11/27 by Louigi Addario-Berry, Louigi Addario‐Berry, Addario-Berry, Louigi +9 · 1 voice · 1 citation
Mathematics · #Stochastic processes and statistical mechanics #cs.DS #cs.SI #math.PR #math.ST

paper · pdf · doi:10.48550/arxiv.2411.18614

openalex publication_date 2024/11/27 · openalex created_date 2024/12/05 · openalex updated_date 2026/07/28

Abstract

We consider root-finding algorithms for random rooted trees grown by uniform attachment. Given an unlabeled copy of the tree and a target accuracy ε > 0, such an algorithm outputs a set of nodes that contains the root with probability at least 1 - ε. We focus on the algorithm introduced by Bubeck, Devroye and Lugosi (2017) and proved to be optimal by Crane and Xu (2021). We prove that, for the optimal algorithm, an output set of size exp(O(log^1/2(1/ε))) suffices; this bound is sharp and answers a question of Bubeck, Devroye and Lugosi (2017). We prove similar bounds for random regular trees that grow by uniform attachment, strengthening a result of Khim and Loh (2017).

Cited by

• Subcritical percolation and network archaeology on random recursive tree substrate networks

Discussions

• It's looking like all the open problems I have thought about in the last 10 years are now solved (or in some cases on the verge of being solved)? Latest case in point this beautiful new paper: arxiv.o [bsky, 30 points, 3 comments]

Related

• Leaf Stripping on Uniform Attachment Trees
• Finding the seed of uniform attachment trees
• On a Tail Bound for Root-Finding in Randomly Growing Trees
• Root finding algorithms and persistence of Jordan centrality in growing random trees
• Finding Adam in random growing trees