1 files changed, 77 insertions, 9 deletions

diff --git a/main.tex b/main.tex
index ceb8e92..96c5d5b 100644
--- a/main.tex
+++ b/main.tex
@@ -85,13 +85,79 @@ With the assumption that accessing the labels $(u, w)$ takes $\mathcal{O}(1)$ ti
 \section{Reachability}%
 \label{sec:reachability}
 
-First, compute all strongly connected components (SCCs) of $G$ by using~\parencite{tarjanDepthFirst1972} per \emph{page 72} of the \nth{3} lecture notes in $\mathcal{O}(E+V)$ time. Instead of labelling the SCCs with the root node, we will initially label all nodes of the SCC $F'$ with the $min(u)$ of the connected component.
+The intuition for this question can be illustrated as follows;
 
-Then, by ignoring the tree edges, shrink the graph $G$ such that $E' = {(v, w)~|~v \in F', w \in F''}$, leaving only cross links behind. This step takes another $\mathcal{O}(E+V)$ time.
+If $G$ is strongly connected then the answer is trivial; every vertex have the same $\min(u) = 1$.
 
-Now run the topological sort algorithm presented in \emph{page 84} of the \nth{3} lecture notes this operation is yet again $\mathcal{O}(E+V)$.
+For a directed acyclic graph, consider the scenario below;
 
-Finally, reverse the direction of the edges on the graph that have been output by the topological sort and starting from the new root node, traverse the graph downwards and update the $min(u)$ of every SCC as follows;
+\begin{tikzpicture}
+    [vertex/.style={circle,draw,thick,minimum size=6mm,inner sep=10pt},
+    edge/.style={->,>=stealth',line width=1pt]}]
+
+    \node[vertex] (0) {$a$};
+    \node[vertex] (1) [right=of 0] {$b$};
+    \node[vertex] (2) [right=of 1] {$c$};
+    \node[vertex] (3) [right=of 2] {$d$};
+
+    \node [above,xshift=-5mm] at (0.north west) {$L(u) = 4$};
+    \node [above] at (1.north) {$L(u) = 1$};
+    \node [above] at (2.north) {$L(u) = 3$};
+    \node [above,xshift=5mm] at (3.north east) {$L(u) = 2$};
+
+    % \node [red,below] at (0.south) {$\min(u) = 1$};
+    % \node [red,below] at (1.south) {$\min(u) = 1$};
+    % \node [red,below] at (2.south) {$\min(u) = 2$};
+    % \node [red,below] at (3.south) {$\min(u) = 3$};
+
+    \draw [edge] (0) to (1);
+    \draw [edge,bend left=45] (0) to (3);
+    \draw [edge] (1) to (2);
+    \draw [edge] (2) to (3);
+\end{tikzpicture}
+
+We can assign the $\min(u)$ values on this directed acyclic graph by reversing the direction of the edges and traversing the graph, keeping a minimum $\min(u)$ encountered so far for the nodes;
+
+\begin{tikzpicture}
+    [vertex/.style={circle,draw,thick,minimum size=6mm,inner sep=10pt},
+    edge/.style={<-,>=stealth',line width=1pt]}]
+
+    \node[vertex] (0) {$a$};
+    \node[vertex] (1) [right=of 0] {$b$};
+    \node[vertex] (2) [right=of 1] {$c$};
+    \node[vertex] (3) [right=of 2] {$d$};
+
+    \node [above,xshift=-5mm] at (0.north west) {$L(u) = 4$};
+    \node [above] at (1.north) {$L(u) = 1$};
+    \node [above] at (2.north) {$L(u) = 3$};
+    \node [above,xshift=5mm] at (3.north east) {$L(u) = 2$};
+
+    \node [red,below] at (0.south) {$\min(u) = 1$};
+    \node [red,below] at (1.south) {$\min(u) = 1$};
+    \node [red,below] at (2.south) {$\min(u) = 2$};
+    \node [red,below] at (3.south) {$\min(u) = 2$};
+
+    \draw [edge] (0) to (1);
+    \draw [edge,bend left=45] (0) to (3);
+    \draw [edge] (1) to (2);
+    \draw [edge] (2) to (3);
+\end{tikzpicture}
+
+Starting from the \enquote{root} \texttt{d}, the $\min(u)$ is $2$, which is assigned to the immediate neighbours of \texttt{d}, \texttt{c} and \texttt{a}.
+When the traversal \emph{reaches} \texttt{b}, \texttt{b} sets the current $\min(u)$ to $1$ and \texttt{a}'s $\min(u)$ value is updated to $1$ as well.
+
+With the intuition out of the way, we will generalize the problem.
+First, compute all strongly connected components (SCCs) of $G$ by using~\parencite{tarjanDepthFirst1972} per \emph{page 72} of the \nth{3} lecture notes in $\mathcal{O}(E+V)$ time.
+Instead of labelling the SCCs with their root node, we will initially label all nodes of the SCC $F'$ with the $\min(u)$ of the connected component; $\min(a) ~ \text{of} ~ a \in F' = \min{\{L(w) : w \in F'\}}$.
+
+Then, by ignoring the tree edges, \emph{shrink} the graph $G$ such that $E' = \{(v, w)~|~v \in F', w \in F''\}$, leaving only cross links behind.
+This step takes another $\mathcal{O}(E+V)$ time.
+
+Now run the topological sort algorithm presented in \emph{page 84} of the \nth{3} lecture notes.
+This operation is yet again $\mathcal{O}(E+V)$.
+
+We now have a scenario like the one illustrated above.
+Reverse the direction of the edges on the graph that have been output by the topological sort and starting from the new root node, traverse the graph downwards and update the $\min(u)$ of every SCC in $\mathcal{O}(m+n)$ time as follows;
 
 {\centering
     \begin{minipage}{.7\linewidth}
@@ -100,13 +166,13 @@ Finally, reverse the direction of the edges on the graph that have been output b
             \SetAlgoLongEnd{}
             \KwData{$G'$ = topological sorted G with reversed edges}
             \KwResult{$\min(u)$ for all vertices $u \in V$}
-            $\text{mostmin} \longleftarrow \min(\text{root})$\;
-            \While{traversing $G'$ downwards with current node $v$}{
-                \uIf{$\min(v) < mostmin$}{
-                    $\text{mostmin} \longleftarrow \min(v)$\;
+            $\text{minnest} \longleftarrow \min(\text{root})$\;
+            \While(\tcp*[f]{$m+n$}){traversing $G'$ downwards with current node $v$}{
+                \uIf{$\min(v) < minnest$}{
+                    $\text{minnest} \longleftarrow \min(v)$\;
                 }
                 \Else{
-                    label $v$ as $mostmin$
+                    label $v$ as $minnest$
                 }
             }
             \caption{Updating $\min(u)$ of the SCCs}%
@@ -116,6 +182,8 @@ Finally, reverse the direction of the edges on the graph that have been output b
     \par
 }
 
+Finally, update the $\min(u)$ of every node $w \in G$ to match the cross link edges of the SCC they belong to. This operation is yet another $\mathcal{O}(m+n)$ traversal.
+
 \printbibliography
 
 \end{document}