# Direct Superbubble Detection
## Theory
### Superbubble Detection
Thus, every superbubploid \(\langle s,t\rangle\) (with vertex set \(U_{st}\)) in \(\hat{G}[V(T)]\) is characterized by Conditions (F1) and (F2). It is, furthermore, a weak superbubploid in \(G\) if and only if the following conditions hold:  
1. For every \(u\in U_{st}\setminus\{s\}\), there is no edge \((x,u)\in E(G)\) such that \(x\
otin U_{st}\);
2. For every \(v\in U_{st}\setminus\{t\}\), there is no edge \((v,x)\in E(G)\) such that \(x\
otin U_{st}\); and
3. \(G[U_{st}]\) without the edge \((t,s)\in E(G)\) acyclic. Only edges not contained in \(\hat{G}[V(T)]\) need to be considered for Conditions (i) and (ii), because no such edges exist within \(\hat{G}[V(T)]\) due to the assumption that \(\langle s,t\rangle\) is a weak superbubbloid in \(\hat{G}[V(T)]\). For (iii), only the back edges are of interest. By definition, a back edge creates a cycle in \(\hat{G}[V(T)]\). A back edge \((v^{\prime},u^{\prime})\) with \(u^{\prime}\in U_{st}\) would violate (iii) when \(v^{\prime}\in U_{st}\) or (i) if \(v^{\prime}\
otin U_{st}\). Analogously, if \(v^{\prime}\in U_{st}\) and \(u^{\prime}\
otin U_{st}\), then (ii) is violated. Thus, a weak superbubbloid cannot contain the head or tail of a back edge. Only for Condition (i), we also need to consider the case that \(x\
otin V(T)\). (F1) can be satisfied only if \(\mathbf{OutParent}(u)>-1\) for every \(u\in U_{st}\setminus\{s\}\). Analogously, (F2) can only be true if \(\mathbf{OutChild}(u)<\infty\) for all \(u\in U_{st}\setminus\{t\}\). Hence, it suffices to rule out false positive weak superbubbloids in \(G\) by ensuring that every vertex \(u\) that violates one of the three conditions also violates (F1) or (F2). This is achieved by setting \(\mathbf{OutParent}(u)=-1\) for a vertex \(u\) if there is an edge \((x,u)\) such that \(x\
otin V(T)\) or \((x,u)\) is a back edge; analogously, we set \(\mathbf{OutChild}(v)=\infty\) for all \(v\) with an incident edge \((v,x)\) such that \(x\
otin V(T)\) or \((v,x)\) is a back edge. Equation (3) implements exactly these conditions. Thus, only weak superbubbloids fulfill (F1) and (F2). Conversely, it suffices to note that by Lemma 4(ii), every weak superbubbloid forms a contiguous interval w.r.t. the postorder \(\pi\) of \(T\) and, thus, also w.r.t. the reverse postorder \(\bar{\pi}\) of \(T\). We denote by \(\mathtt{Superbubble}\) the algorithm \(\mathtt{DAGsuperbubble}\) with the modified functions \(\mathbf{OutParent}(\,.\,)\) and \(\mathbf{OutChild}(\,.\,)\) as described above. By construction, \(\mathtt{Superbubble}\) identifies minimal intervals of \(\pi\) that satisfy (F1) and (F2); see Figure 1 for an illustration and [7] for full details. Since the modification of \(\mathbf{OutParent}(\,.\,)\) and \(\mathbf{OutChild}(\,.\,)\) only amounts to setting additional entries to \(-1\) or \(\infty\), respectively, the performance remains unaffected. According to Theorem 1, the minimal intervals satisfying (F1) and (F2) are exactly the minimal weak superbubbloids and, thus, by definition, the weak superbubbles. Therefore, we have:  
**Corollary 3**. : _Let \(G\) be a digraph, and let \(T\) be a DFS-tree on \(G\) with a root \(r\) that is not an interior vertex or exit of a weak superbubble. Then, \(\mathtt{Superbubble}\) correctly identifies exactly the weak superbubbles \(\langle s,t\rangle\) in \(G\) whose vertex set satisfies \(U_{st}\cap V[r]\
eq\emptyset\)._  
It is straightforward to extend this result to a DFS-forest that covers \(V(G)\) entirely: This forest is constructed by first constructing \(T_{1}\) with root \(r_{1}\) covering \(V[r_{1}]\). Then, \(T_{2}\) is constructed from a root \(r_{2}\) searching on \(V(G)\setminus V[r_{1}]\), and so on; see Lemma 2. This amounts to constructing an auxiliary graph \(G^{\prime}\) from \(G\) by adding an artificial root \(r_{0}\) and out-edges \((r_{0},r_{1})\), \((r_{0},r_{2})\),..., \((r_{0},r_{k})\), and defining the sibling order of the roots as \(r_{1}\triangleleft r_{2}\triangleleft\dots\triangleleft r_{k}\).