# Direct Superbubble Detection
## Theory
### Superbubble Detection  
We next show how to retrieve all weak superbubbles of a digraph \(G\) that are located within the induced subgraph \(G[V[r]]\) of \(G\). To this end, we use a slightly modified version of the algorithm DAGsuperbubble described in [7]. It was originally designed to operate on acyclic auxiliary graphs with a single source. Thus, it could be assumed that a DFS-tree rooted on this source reached all vertices. Here, we intend to apply it to the unmodified input graph, which is neither acyclic, nor guaranteed to have a single source. It, therefore, needs to be modified to deal appropriately with back edges within the DFS-tree and the existence of vertices outside the DFS-tree. To this end, vertices in \(V[r]\) that cannot be contained in a superbubble have to be identified. By Lemma 4, there are two possible obstructions for a vertex \(u\): (i) \(u\) has an edge that is a back edge in the DFS-tree; (ii) \(u\) is incident to an edge \((x,u)\) or \((u,x)\) where \(x\
ot\in V[r]\). The basic idea of DAGsuperbubble is to identify minimal intervals in reverse postorder \(\tilde{\pi}:=|V[r]|-\pi(v)-1\) of the DFS-tree \(T\) that satisfy conditions equivalent to membership in a superbubploid. These conditions are expressed in terms of a pair of helper functions with the help of reverse postorder \(\tilde{\pi}(v)\) on \(T\). As in [7], \(\textbf{OutParent}(v)\) denotes the first vertex (w.r.t. reverse postorder \(\tilde{\pi}\)) in \(T\) from which \(v\) can be reached. Similarly, \(\textbf{OutChild}(v)\) is the last child vertex reachable from \(v\). \[\textbf{OutParent}(v) := \begin{cases}-1&\text{if no }(u,v)\in E(G)\text{ exists}\\ -1&\text{if }(u,v)\in E(G)\wedge u\
ot\in V[r]\\ -1&\text{if a back edge }(u,v)\in E(G)\\ \min(\{\pi(u)|(u,v)\in E(G)\})&\text{otherwise}\end{cases}  \tag{3}\] \[\textbf{OutChild}(v) := \begin{cases}\infty&\text{if no }(v,u)\in E(G)\text{ exists}\\ \infty&\text{if }(v,u)\in E(G)\wedge u\
ot\in V[r]\\ \infty&\text{if there is a back edge }(v,u)\in E(G)\\ \max(\{\pi(u)|(v,u)\in E(G)\})&\text{otherwise}\end{cases} \]  
These functions are extended to intervals on \(\pi\) as follows:  
\[\textbf{OutParent}([i,j]) :=\min\{\textbf{OutParent}(v)\mid v\in V[r]\wedge i\leq\pi(v)\leq j\} \tag{4}\] \[\textbf{OutChild}([i,j]) :=\max\{\textbf{OutChild}(v)\mid v\in V[r]\wedge i\leq\pi(v)\leq j\}\]  
In [7], we derived a characterization of weak superbubbloids in terms of \(\textbf{OutParent}([i,j])\) and \(\textbf{OutChild}([i,j])\) for the case of acyclic digraphs. Here, we generalize this condition to general graph using the modified definition of \(\textbf{OutParent}(v)\) and \(\textbf{OutChild}(v)\). The difference is that the situation that back edges and edges connecting to the outside of the DFS-tree are considered. In either case, the corresponding vertices are marked by \(-1\) or \(\infty\), respectively, to indicate that they cannot be part of superbubbloids. Theorem 1: _Let \(G\) be a digraph; let \(T\) be a DFS-tree on \(G\) with a root \(r\) that is not an interior vertex or exit of a weak superbubploid; and denote by \(\tilde{\pi}\) the reverse postorder on \(T\). Then, \(\langle s,t\rangle\) is a weak superbubploid in \(G\) whose vertex set \(U_{st}\) satisfies \(U_{st}\cap V[r]\
eq\emptyset\) if and only if the following conditions are satisfied:_  
1. \(\textbf{OutParent}([\pi(s)+1,\pi(t)])=\pi(s)\) _(predecessor property)_
2. \(\textbf{OutChild}([\pi(s),\pi(t)-1])=\pi(t)\) _(successor property)_  
Proof: It was shown in [7] (theorem 2) that the statement is true for acyclic digraphs. We first note that by Lemma 3, every weak superbubploid intersecting \(V[r]\) is contained in \(V[r]\), i.e., in \(V(T)\). For the purpose of the proof, consider the auxiliary graph \(\hat{G}[V(T)]\) with edge set \(E(\hat{G}[V(T)])=E(G[V(T)])\setminus\{e\mid e\) is a back edge w.r.t. T\(\}\). By construction, \(\hat{G}[V(T)]\) is acyclic, and every vertex is in \(T\).