Finding Adam in random growing trees1. Issue 2 (17th November 2016)

• Record Type: Journal Article
• Authors: Bubeck, Sébastien; Devroye, Luc; Lugosi, Gábor
• Is Part Of: Random structures & algorithms. Volume 50:Issue 2(2017)
• Page Start: 158
• Page End: 172
• Publication Date: 2016-11-17
• Subjects: root‐finding algorithms -- random trees -- polya urns; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20649
• Languages: English
• ISSNs: 1042-9832

Abstract

ABSTRACT: We investigate algorithms to find the first vertex in large trees generated by either the uniform attachment or preferential attachment model. We require the algorithm to output a set of K vertices, such that, with probability at least 1 − ε, the first vertex is in this set. We show that for any ε, there exist such algorithms with K independent of the size of the input tree. Moreover, we provide almost tight bounds for the best value of K as a function of ε . In the uniform attachment case we show that the optimal K is subpolynomial in 1 / ε, and that it has to be at least superpolylogarithmic. On the other hand, the preferential attachment case is exponentially harder, as we prove that the best K is polynomial in 1 / ε . We conclude the paper with several open problems. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 158–172, 2017