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, can you prove it?
Sink: a node that has incoming edges from all other nodes and no outgoing edges.
+1
A:
In the case of a general directed graph, no, and I don't think it needs a formal proof. At best, detecting a sink requires you to either identify the node and check that it has no outgoing edges, or inspect every other node and see that none of them have connections coming from it. In practice, you combine the two in an elimination algorithm, but there is no shortcut.
By the way, there is disagreement over the definition of sink. It's not usual to require all other nodes connect to the sink, because you can have multiple sinks. For instance, the bottom row in this diagram are all sinks, and the top row are all sources. However, it allows you to reduce the complexity to O(n). See here for some slightly garbled discussion.
Mark
2009-05-11 11:19:10
That page shows how to do it in O(n)
Mark
2009-05-11 15:06:37
+2
A:
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.
Dave
2009-05-15 23:48:46
A:
Yes it is possible , i found it here.
http://supermanhelp.com/view_ques.aspx?data=633941324939340000.txt
rani
2009-11-18 14:31:25