# Direct Superbubble Detection
## Theory
### Superbubble Detection
The DFS-forest \(F(r_{1},\dots,r_{k})\) with given roots \(r_{1}\), \(r_{2}\),..., \(r_{k}\) on \(G\) is then equivalent to the DFS-tree \(T^{\prime}\) rooted at \(r_{0}\) on \(G^{\prime}\) if we define the reverse postorder of \(T^{\prime}\) such that \(\pi(r_{0})=0\). We note, furthermore, that sibling order, i.e., the order in which the roots are used to seed DFS, is arbitrary. **Corollary 4**. : _Let \(G\) be a digraph, and let \(F\) be a DFS-forest on \(G\) comprising DFS-trees \(T_{i}\) with roots \(r_{i}\), \(1\leq i\leq k\), none of which is an interior vertex or exit of a weak superbubble. Let \(\bar{\pi}\) be the reverse postorder on \(F\), obtained by concatenating the reverse postorders on the constituent DFS-trees. Then, \(\mathtt{Superbubble}\) correctly identifies exactly the weak superbubbles \(\langle s,t\rangle\) in \(G\). Furthermore, given the roots \(r_{i}\), \(\mathtt{Superbubble}\) has a running time of \(O(|E|+|V|)\)._  
Proof. : Correctness follows immediately from Corollary 3, the construction of \(T^{\prime}\) on the auxiliary digraph \(G^{\prime}\), and Lemma 2. During the DFS, each out-edge is considered exactly once, and each vertex is traversed twice. The number \(k\) of required roots is limited by \(|V|\). For each vertex \(v\), checking whether \(\mathbf{OutParent}(v)=-1\) or \(\mathbf{OutChild}(v)=\infty\) requires checking all neighbors only; hence, the total effort is no more than \(O(|E|+|V|)\). The linear time complexity of DAGsuperbubble, finally, is proven in [7]. It is important to note the correctness of Superbubble, Corollary 3, crucially depends on the correct choice of the root \(r\) of the DFS-tree. The remaining problem thus is to find a suitable sequence of roots \(r_{1}\), \(r_{2}\),..., \(r_{k}\). **Definition 3**. : _A vertex \(r\in V\) is a legitimate root if for every weak superbubble \(\langle s,t\rangle\) in \(G\) with vertex set \(U_{st}\), we have either \(U_{st}\subseteq V[r]\) and \(t\prec s\) (in the ancestor order of a search tree with root \(r\)), or \(U_{st}\cap V[r]=\emptyset\)._  
We can summarize the discussion in the following form:  
**Corollary 5**. : _The algorithm Superbubble detects all weak superbubbles in \(G\) if and only if there is a set \(\{r_{1},r_{2},\ldots,r_{k}\}\) of legitimate roots such that the DFS-forest \(F(r_{1},r_{2},\ldots,r_{k})\) covers \(V(G)\)._  
**Corollary 6**. : _A vertex \(r\in V\) is a legitimate root if and only if \(r\) is neither an interior nor an exit of a weak superbubble._  
Proof. : By Corollary 4, a root is legitimate if it is not the exit or an interior vertex of a weak superbubble. Conversely, if \(r\) is an interior vertex or the exit of \(\langle s,t\rangle\), then a DFS-tree rooted in \(r\) reaches the entrance \(s\) either not at all or there is not search tree with root \(r\) such that \(t\prec s\), since by definition of a weak superbubble, the exit \(t\) is found before \(s\) along every path from \(r\) to \(s\). **Lemma 5**. : _Let \(G\) be a digraph and \(v\in V(G)\) a source, i.e., a vertex with in-degree zero. Then, \(v\) is a legitimate root._  
Figure 1: Illustration of the algorithm Superbubble on a digraph \(G\) with cycles. The top panel shows the input digraph. The DFS-tree \(T\) is rooted at one and covers \(V[r]=V(G)\setminus\{15\}\). The table below gives the values of \(\mathbf{OutParent}\) and \(\mathbf{OutChild}\) as a function of the reverse postorder \(\pi\) of \(T\). In the final line, matching pairs of parentheses indicate entrances and exits of the weak superbubbles in \(V[r]\). This corresponds to the intervals that fulfill (F1) and (F2). Proof. : Since \(v\) is not reachable from any other vertex, it is only reachable by DFS if the traversal starts in \(v\). By the same argument, \(v\) is neither an interior vertex, nor the exit of a weak superbubble and, thus, is a legitimate root. Unfortunately, there is no guarantee that a digraph \(G\) has source vertices, and even if they exist, not every vertex of \(G\) is necessarily reachable from them.