2014/11/12 by Bubeck, Sébastien, Devroye, Luc, Lugosi, Gábor
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #Social and Information Networks (cs.SI) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.1411.3317
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.