3
$\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?

$\endgroup$
0

2 Answers 2

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

$\endgroup$
6
  • $\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$ Aug 27, 2017 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$
    – user35837
    Aug 27, 2017 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$ Aug 27, 2017 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$
    – user35837
    Aug 27, 2017 at 10:21
  • $\begingroup$ Ok, i got it, tricky but elegant, thanks! $\endgroup$ Aug 27, 2017 at 10:36
0
$\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"
$\endgroup$
2
  • 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, 2017 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$ Aug 27, 2017 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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