# Direct Superbubble Detection
## Theory
### Identification of Quasi-Legitimate Roots
We therefore briefly outline [PERSON]'s SSC algorithm; for full details, we refer to [8]: First, the vertices are enumerated in preorder. Then, a postorder traversal is used to compute, for each \(v\), the _lowlink_\(\ell(w)\), which is recursively defined as:  
\[\ell(v) :=\min\big{(}\{\ell(w)|(v,w)\text{ is a tree- or unfinished cross-edge}\}\cup \tag{8}\] \[\{\rho(w)|(v,w)\text{ is a back edge}\}\cup\{\rho(v)\}\big{)}\]  
A cross edge is only included if it is \"unfinished\", i.e., if its endpoint \(w\) has not been reported as part of a previously-completed SCC. A vertex \(v\) is the root of an SSC if \(\ell(v)=\rho(v)\). [PERSON]'s SSC algorithm now uses a stack to iterate over every vertex of the SCC \(S\) to mark them as finished. This cannot be done in the same way in a predefined DFS-tree. The stack can be replaced, however, by an equally-efficient iterative method: Starting from \(v\) with \(\ell(v)=\rho(v)\), simple traverse \(T[v]\) starting at \(v\); report all \"unfinished\" vertices as members of the SSC; and omit every subtree rooted in a \"finished\" vertex. To see that this is correct, note that \(\ell(w)\
eq\rho(w)\) for all \(w\in S\setminus\{v\}\), and hence, \(w\) is \"unfinished\" when the postorder traversal encounters \(v\). Lemma 15 implies that there is a path \((v,w_{1},\ldots,w_{h}=w)\) from \(v\) to \(w\) in \(T\), with \(w_{i}\in S\) and thus also \"unfinished\". Thus, if \(u\) is \"finished\", so are all its descendants, and the subtree \(T[u]\) does not need to be considered. The only difference from [PERSON]'s SSC algorithm tree traversal is to retrieve \(S\), which considers every edge of \(T\) once and thus runs in a total time of \(O(|V|)\). We summarize the discussion above as:  
**Lemma 19**. : _The modified version of [PERSON]'s SCC algorithm correctly identifies all strongly-connected components in \(T\) in \(O(|E|+|V|)\) time._  
Since the correct values of \(c_{\min}[c_{1},u]\) and \(c_{\max}[c_{1},u]\) are computed by postorder traversal of \(T_{c}\), they are already available when the root \(v\) of a \(\stackrel{{ C}}{{\leadsto}}\)-SCC is encountered. Thus, identification of the \(\stackrel{{ C}}{{\leadsto}}\)-SCC and the computation of \(c_{\min}[c_{1},u]\) and \(c_{\max}[c_{1},u]\) can be combined in the same tree traversal. The same tree traversal also guarantees that for every cross edge \((u,w)\), we have either (i) \(u\) and \(w\) in the same \(\stackrel{{ C}}{{\leadsto}}\)-SCC or (ii) the values of \(c_{\min}[c_{1},w]\) and \(c_{\max}[c_{1},w]\) are computed correctly. Now, consider the vertex \(c_{j}\) along \(C\), and suppose we have not encountered a one-vertex \(\stackrel{{ C}}{{\leadsto}}\)-cover so far. Let \(T_{j}\) be the DFS-tree rooted in \(c_{j}\) that ignores all vertices already included in a previous DFS-tree. As for \(c_{i}\), we can compute \(c_{\min}[c_{j},v]\) and \(c_{\max}[c_{j},v]\) with \(v\in T_{j}\) along this tree. Then, \(c_{\min}[c_{j},v]\) either equals \(c_{\min}[c_{j},v]\) computed on \(T_{j}\) or \(c_{\min}[c_{i},u]\) for some \(u\) such that \((v,u)\in E(G)\), depending on which has the smaller value of \(d_{C}(c_{j},\,.\,)\), and \(c_{\max}[c_{j},v]\) either equals \(c_{\max}[c_{j},v]\) computed on \(T_{j}\) or \(c_{\max}[c_{i},u])\), depending on which has the larger value of \(d_{C}(c_{j},\,.\,)\). Note that \(c_{\min}[c_{i},v]\) and \(c_{\max}[c_{i},v]\) do not actually depend on \(i\). In a practical implementation, it is simply stored in dependence of \(v\). The index \(c_{i}\) only is used to keep track of the individual, disjoint DFS-trees \(T_{i}\) rooted in \(c_{i}\) in our arguments. After processing all vertices of \(C\), we have either found a one-vertex \(\stackrel{{ C}}{{\sim}}\)-cover of \(C\), or we know, for every \(c_{j}\in C\), the largest \(\stackrel{{ C}}{{\sim}}\)-covered interval \(C(c_{j},c_{\max}(c_{j}))\).