# Direct Superbubble Detection
## Theory
### Weak Superbubbles
The reachability axiom (S.ii) ensures that every \(u\in U_{st}\) is reached by the DFS whenever \(s\in V(G)\), i.e., \(U_{st}\in V[r]\). Lemma 3 is a variant of the key theorem of [5]. **Corollary 2**. : _Let \(G=(V,E)\) be a digraph and \(U_{st}\) the vertex set of a weak superbubbloid \(\langle s,t\rangle\) in \(G\). Let \(r_{1},r_{2},\ldots,r_{k}\in V\) be such that none of the \(r_{i}\) are an interior or an exit vertex of \(\langle s,t\rangle\). Set \(W_{j}:=\bigcup_{i=1}^{j}V[r_{i}]\) and \(V^{\prime}[r_{j}]=V[r_{j}]\setminus W_{j-1}\). Then, either \(U_{st}\cap V^{\prime}[r_{j}]=\emptyset\) or \(U_{st}\subseteq V^{\prime}[r_{j}]\)._  
Proof. : By Lemma 3, \(U_{st}\) is either contained in the intersection of two or more reachable sets \(V[r_{i}]\) or is disjoint from it. As an immediate consequence, it is also either contained in the difference of two reachable sets or disjoint from it. **Lemma 4**. : _Let \(G\) be a digraph; let \(U_{st}\) be the vertex set of a weak superbubbloid \(\langle s,t\rangle\) in \(G\); let \(T\) be a DFS-tree on \(G\) with root \(r\
otin U_{st}\setminus\{s\}\); and let \(\pi\) be the postorder w.r.t. \(T\). Then:_  
1. _The induced subgraph_ \(G[U_{st}]\) _contains no back edges w.r.t._ \(T\)_, except possibly_ \((t,s)\)_._
2. _If_ \(U_{st}\subseteq V(T)\)_, then_ \(\{\pi(u)|u\in U_{st}\}=[\pi(t),\pi(s)]\) _is an interval w.r.t. to_ \(\pi\)_._  
Proof. : (i) The statement is trivial if \(\langle s,t\rangle\) is not contained in \(T\). If \(\langle s,t\rangle\) resides in an acyclic part \(A\) of \(G\), there are no back edges because \(A\) cannot contain back edges by acyclicity. If \(\langle s,t\rangle\) is contained in a strongly-connected component \(C\), the proof of Lemma 9 of [7] also implies Assertion (i) because the DFS-tree \(T\), in particular, contains a DFS-tree of \(C\) as a subtree and back edges in \(G\) can only be located within a strongly-connected component. (ii) Since the DFS generating \(T\) enters \(\langle s,t\rangle\) through \(s\) and leaves it through \(t\), the preorder \(\rho\) satisfies \(\rho(s)<\rho(t)\). Since \(t\) is reachable from every \(u\in U_{st}\), we conclude that any DFS reaches \(t\) before completing any \(u\in U_{st}\); hence, \(t\) precedes any other \(u\in U_{st}\) in postorder, i.e., \(\pi(u)>\pi(t)\). Since \(u\in U_{st}\) is not reachable without passing through \(s\), every other vertex in \(u\in U_{st}\) precedes \(s\) in postorder, i.e., \(\pi(s)>\pi(u)\). Now, suppose there is some \(w\
otin U_{st}\) with \(\pi(s)>\pi(w)>\pi(t)\). Then, \(w\) must be reachable from \(s\) along a directed path that does not pass through \(t\), a contradiction to the definition of weak superbubbloids. Hence, the vertices of a superbubbloid form an interval in postorder of the DFS-tree \(T\). Statement (ii) rephrases the key result of [6], although we do not need to assume that \(G\) is an acyclic digraph. Conceptually, Lemma 4 suggests that it might not be necessary to first identify the strongly-connected components of \(G\)[5] or the construct acyclic auxiliary digraphs [6] in order to find all weak superbubbles. Lemma 2 then ensures that a single DFS-forest is sufficient.