ABSTRACT We consider an algorithmic problem on the Erdős–Rényi random graph with for some fixed constant . At the start of the algorithm, it is not disclosed which pairs of vertices are adjacent or not. In each step of the algorithm, we can query one pair of vertices to reveal whether an edge is present between them. Each query is allowed to depend on the outcome of all previous queries. The objective is to reveal a set of edges that form a path of length with as few queries as possible. Ferber, Krivelevich, Sudakov, and Vieira showed that if , then with positive probability, the algorithm will need to make queries. They conjectured that the factor of could be removed, which would be optimal. We confirm their conjecture. The main ingredient in our proof is a result about path‐packings in random labelled trees of independent interest. Using this, we also give a partial answer to a related question of Ferber, Krivelevich, Sudakov, and Vieira. Namely, we show that if and is chosen uniformly at random from all trees on vertex set , then the maximum number of vertices covered by vertex‐disjoint paths of length at least in is with high probability.
Iršič et al. (Fri,) studied this question.