# Determining whether a digraph has a sink

Let $$G= (V,E)$$ be a directed graph with $$n$$ vertices.
A sink is a vertex $$s\in V$$ such that for all $$v \in V$$, $$(v,s) \notin E$$. Devise an algorithm that, given the adjacency matrix of $$G$$, determines whether or not $$G$$ has a sink in time $$O(n)$$.

Does this pseudocode code look good?

# Input: An adjacency matrix G

# Output: True if G has a sink and False if G does not have a sink.

Algorithm DetermineSink(G)
i←0
j←0
for 0 to len(G)
if G[i,j] = 1 ∧ j ≠ i # if there is an edge emanating from i, it is not a sink.

return False
if G[j,i] = 0 ∧ j ≠ i # there exists no edge and hence it is not a sink

return False
return True

• What does "for 0 to len(G)" do? How are $i,j$ updated? Oct 17 '20 at 9:13
• A simple adversary argument shows that given an adjacency matrix, you need to look at all entries in order to determine whether there is a sink or not. The adversary simply answers $A[i,j] = 0$ to all queries, unless the query is the last one in its row, in which case it answers $A[i,j] = 1$. Oct 17 '20 at 9:16
• Yes I know that but I dont know how to change my code to check all the rows if they are zero when you get the 1 in any one column. Oct 17 '20 at 9:47
• If there is a sink,the adjacency matrix will contain all 1's except diagnol in one column and all 0's(except diagnol)in the corresponding row of the vertex. Oct 17 '20 at 9:55
• The argument implies that any valid algorithm would take $\Omega(n^2)$ time. Oct 17 '20 at 10:25