# Direct Superbubble Detection
## Theory
### Identification of Quasi-Legitimate Roots
Up to this point, the values of \(c_{\min}[c_{i},v]\) and \(c_{\max}[c_{i},v]\) are independent of \(c_{i}\) by Lemma 18. The difficulty is to compute the \(c_{\min}[c_{i},v]\) and \(c_{\max}[c_{i},v]\) for all \(v\in V(T_{c})\) correctly. We have already seen above how to handle tree edges. Forward-edges in \(T_{c}\) do not effectively contribute, because the same information (minimization or maximization over values of \(d_{C}(c,\,.\,)\)) is also propagated stepwise along the tree-edges. Cross edges, on the other hand, could add information. Postorder traversal ensures, however, that the pertinent information at their starting points is already computed in time to include them to compute the correct value, i.e., we simply have to include the cross-edges in the minimization/maximization step. Back edges are problematic when belonging to the same strongly-connected component \(S\) as \(C\subsetneq S\). In this case, they can be reached from a cycle vertex \(c\in C\) and themselves reach a cycle vertex \(u\in C\). Such back edge, therefore, influence which cycle vertices are reachable. To handle this information, \(S\) is split into parts that are strongly connected components under the use of \(\xrightsquigarrow{C}\)-reachability. More precisely, we define a \(\xrightsquigarrow{C}\)-SCC as a strongly-connected component on the induced subgraph \(G[V(G)\setminus C]\). Consider the auxiliary graph \(G_{c}\) with vertex set \((V(G)\setminus C)\cup\{c\}\) and all edges of \(G[V(G)\setminus C]\), as well as all edges \((c,u)\) with \(u\in V(G)\setminus C\). Then, \(c\) is not contained in a cycle of \(G_{c}\), and thus, the SCC of \(G_{c}\) are exactly the \(\xrightsquigarrow{C}\)-SCC and the single vertex \(c\). By construction, \(T_{c}\) is also a DFS-tree for \(G_{c}\). Thus, [PERSON]'s DFS-based SCC-detection algorithm (see Lemma 15) on \(T_{c}\) identifies the \(\xrightsquigarrow{C}\)-SCC as the SCC of \(G_{c}\). To mimic the traversal on \(G_{c}\) instead on \(G[(V(G)\setminus C)\cup\{c\}]\), the graph on which \(T_{c}\) was originally defined, it suffices to ignore the back edge leading to the root, i.e., edges of the form \((u,c)\) for \(u\in V(G)\setminus C\). It is thus not necessary to construct the graph \(G_{c}\) explicitly. The definitions of \(c_{\min}\) and \(c_{\max}\) imply:  
**Corollary 13**. : _Let \(C\) be a cycle in the digraph \(G\); let \(T_{c}\) be a modified DFS-tree rooted at \(c\in C\); and let \(S\) be a \(\xrightsquigarrow{C}\)-SCC with \(S\subseteq V(T_{c})\). Then, \(c_{\min}[c_{1},v]\) and \(c_{\max}[c_{1},v]\) are independent of \(v\) for every \(v\in S\)._  
This begs the question of whether the \(v\)-independent values of \(c_{\min}[c_{1},v]\) and \(c_{\max}[c_{1},v]\) can be obtained while traversing \(G\). A partial answer is provided by:  
**Corollary 14**. : _Let \(C\) be a cycle in the digraph \(G\); let \(T_{c}\) be a modified DFS-tree rooted at \(c\in C\); and let \(v\) be the root of a \(\xrightsquigarrow{C}\)-SCC. Suppose the values of \(c_{\min}[c_{1},w]\) and \(c_{\max}[c_{1},w]\) are known for \(w\
otin V(T_{c}[v])\). Then, \(c_{\min}[c_{1},v]\) and \(c_{\max}[c_{1},v]\) are obtained correctly by postorder traversal of \(T_{c}\) considering all tree and cross edges._Proof. : The only missing information could be a back edge \((u,w)\) with \(u\in V(T[v])\) and \(v\prec w\). Such a back edge cannot exist because \(v\) is by assumption the root of a \(\stackrel{{ C}}{{\leadsto}}\)-SCC, and thus, there is no cycle including \(u\), \(v\), and \(w\in G[V(G)\setminus C]\). This observation yields a simple solution to obtain the correct entries for \(c_{\min}[c_{1},v^{\prime}]\) and \(c_{\max}[c_{1},v^{\prime}]\) for every \(v^{\prime}\in S\): determine the \(\stackrel{{ C}}{{\leadsto}}\)-SCC and its root \(v\), and set \(c_{\min}[c_{1},v^{\prime}]\gets c_{\min}[c_{1},v]\) and \(c_{\max}[c_{1},v^{\prime}]\gets c_{\max}[c_{1},v]\). [PERSON] [8] showed that SCC can be found efficiently by DFS. Below, we will modify the approach slightly to operate on a given DFS-tree.