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

Reading the link provided by SPWorley I was reminded of tournament tree algo for finding the minimum element in an array of numbers. The node at the top of the tree is a minimum element. Since the algorithm in the link also speaks about competition between two nodes (v,w) which is succeeded by w if v->w otherwise by v. We can use an algorithm similar to finding minimum element to find out a sink. However, a node is returned irrespective of the existence of a sink. Though, if a sink exists it is always returned. Hence, we finally have to check that the returned node is a sink.

//pseudo code
//M -> adjacency matrix
int a=0
for(int i=1;i<vertices;++i)
{
  if(M[a,i]) a=i;
}

//check that a is sink by reading out 2V entries from the matrix
return a; //if a is a sink, otherwise -1

Answer 2

This page answers your exact question. The linear time algorithm is

   def find-possible-sink(vertices):
     if there's only one vertex, return it
     good-vertices := empty-set
     pair vertices into at most n/2 pairs
     add any left-over vertex to good-vertices
     for each pair (v,w):
       if v -> w:
         add w to good-vertices
       else:
         add v to good-vertices
     return find-possible-sink(good-vertices)

   def find-sink(vertices):
     v := find-possible-sink(vertices)
     if v is actually a sink, return it
     return "there is no spoon^H^H^H^Hink"