Graphs: find a sink in less than O(|V|) - or show it can't be done

Question

I have a graph with n nodes as an adjacency matrix.

Is it possible to detect a sink in less than O(n) time?

If yes, how? If no, how do we prove it?

Sink vertex is a vertex that has incoming edges from other nodes and no outgoing edges.

Answer 1

Suppose to the contrary that there exists an algorithm that queries fewer than (n-2)/2 edges, and let the adversary answer these queries arbitrarily. By the Pigeonhole Principle, there exist (at least) two nodes v, w that are not an endpoint of any edge queried. If the algorithm outputs v, then the adversary makes it wrong by putting in every edge with sink w, and similarly if the algorithm outputs w.