An efficient algorithm for stopping on a sink in a directed graph

Abstract Vertices of an unknown directed graph of order n are revealed one by one in some random permutation. At each point, we know the subgraph induced by the revealed vertices. Our goal is to stop on a sink, a vertex with no out-neighbors. We show that if a sink exists this can be achieved with probability Θ ( 1 / n ) , which is best possible.