probability theory

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

arXiv:2411.18614

summary

The paper studies algorithms that locate the root of random trees grown by uniform attachment, showing that an optimal method can identify a small set of candidate nodes whose size grows like exp(O(sqrt(log(1/ε)))) to contain the true root with high probability, and extends similar results to regular growing trees.

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 , such an algorithm outputs a set of nodes that contains the root with probability at least . 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 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).

31 pages. Annals of Applied Probability, to appear

Topics & keywords

#root finding#random trees#uniform attachment#regular trees#algorithmic analysisuniform attachmentroot recoveryoptimal algorithmexponential size boundregular growing trees
Optimal root recovery for uniform attachment trees and $d$-regular growing trees · wovepaper