# Graphs: Dectect a sink in $\mathcal{O}(V)$

Given a directed conected graph which representation is its adjacency matrix $A$, design an algorithm to detect a sink in $\mathcal{O}(V)$ time, being $V$ the number of vertices.

As definitions can vary, in this context, a sink is defined as a vertex with $0$ exit degree and $V-1$ enter degree.

Obviously, the problem is reduced to find a $j\in\{1,\dots,V\}$ such as $a_{ji}=0$ for all $i$ and $a_{ij}=1$ for all $i\not=j$, thats what I tried. However, this solution is in $\mathcal{O}(V^2)$.

Any idea?

Assumption :There is at most one row which contains all zero's.

You want to find a row of the adjacency matrix $A$ whose all entries are zero's. Simple observation if say the desired row is $k$th than in the $k$th column of adjacency matrix $A$ will contain all ones except the [k,k] index (it is easy to verify ). Let $n$ is the number of rows and columns in the matrix $A$.

Algorithm :

1. Start from the top right corner of the matrix $A$.
2. If $a_{i,j} = 0$ and $i \neq j$ then it's not your required column, skip this column mean move to $j-1$th column (see you have skipped one column in this step, so the number of columns for your search has been reduced).
3. if $a_{i,j} = 1$ and $i \neq j$ then it is your required column, but it is not required row (think why ? ) so change the row move to $i+1$th keep the column same.

Running time. : In each step you either reducing the number of rows or number of columns, so maximum number of steps is going to be at max $2n$ (number of rows + number of columns ).

• It seems to me that you are you assuming the graph is complete in the sense that every pair of vertices are conected by a single edge. Am I wrong? – Álvaro G. Tenorio Aug 27 '17 at 10:00
• No I am not assuming that given graph is complete. I am only assuming there is at most one sink node – aaag Aug 27 '17 at 10:10
• When you discard a row (step 3 ok) and then step 2 fails, when going again to step 2 you only check $a_{ij}=1$ for the non discarded rows. It does not affect the correctness of the algorithm? – Álvaro G. Tenorio Aug 27 '17 at 10:13
• It does not affect the correctness of the algorithm , because I am carefully ( based on condition ) skipping the rows and columns – aaag Aug 27 '17 at 10:21
• Ok, i got it, tricky but elegant, thanks! – Álvaro G. Tenorio Aug 27 '17 at 10:36

I believe this page provides an answer. The following pseudocode is from that page:

   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"

• Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. – Raphael Aug 27 '17 at 7:55
• I have some unclear points. What's the meaning of "pair vertices into at most n/2 pairs"? Take an arbitrary pairing of "good-vertices"? What happens if there is no edge betwen v and w in a pair (v,w)? – Álvaro G. Tenorio Aug 27 '17 at 9:49