4
$\begingroup$

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?

||cite|improve this question
$\endgroup$
2
$\begingroup$

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 ).

||cite|improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Álvaro G. Tenorio Aug 27 '17 at 10:00
  • $\begingroup$ No I am not assuming that given graph is complete. I am only assuming there is at most one sink node $\endgroup$ – Shiv Aug 27 '17 at 10:10
  • $\begingroup$ 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? $\endgroup$ – Álvaro G. Tenorio Aug 27 '17 at 10:13
  • $\begingroup$ It does not affect the correctness of the algorithm , because I am carefully ( based on condition ) skipping the rows and columns $\endgroup$ – Shiv Aug 27 '17 at 10:21
  • $\begingroup$ Ok, i got it, tricky but elegant, thanks! $\endgroup$ – Álvaro G. Tenorio Aug 27 '17 at 10:36
1
$\begingroup$

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"
||cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael♦ Aug 27 '17 at 7:55
  • $\begingroup$ 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)? $\endgroup$ – Álvaro G. Tenorio Aug 27 '17 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.