Finding Adam in random growing trees

Original · EN

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.