Optimal cover time for a graph-based coupon collector process

In this paper we study the following covering process defined over an arbitrary directed graph. Each node is initially uncovered and is assigned a random integer rank drawn from a suitable range. The process then proceeds in rounds. In each round, a uniformly random node is selected and its lowest-ranked uncovered outgoing neighbor, if such exists, is covered. We prove that if each node has in-degree Θ(d)Θ(d) and out-degree O(d)O(d), then with high probability, every node is covered within O(n+nlognd) rounds, matching a lower bound due to Alon. A special case of our result is that for any Θ(logn)-regular graph and a small rank range of Θ(logn), every node is covered within Θ(n)Θ(n) rounds. Alon has also shown that, for a certain class of d-regular expander graphs, the upper bound holds no matter what method is used to choose the uncovered neighbor. In contrast, we show that for arbitrary d-regular graphs, the method used to choose the uncovered neighbor can affect the cover time by more than a constant factor.