# Direct Superbubble Detection
## Theory
### Weak Superbubbles  
Superbubbles [2] are a complex generalization of \"bubbles\". Comprising two or more isolated paths connecting a source \(s\) to a target \(t\), bubbles are the simplest obstacle in sequence assembly problems [9]. We use here the terminology of [7]:  
**Definition 1**. : _Let \(G\) be a digraph, and let \((s,t)\) be an ordered pair of distinct vertices. Denote by \(U_{st}\) the set of vertices reachable from \(s\) without passing through \(t\), and write \(U_{ts}^{+}\) for the set of vertices from which \(t\) is reachable without passing through \(s\). Then, the subgraph \(G[U_{st}]\) induced by \(U_{st}\) is a superbubbloid in \(G\) if the following three conditions are satisfied:_  
1. \(t\in U_{st}\)_, i.e.,_ \(t\) _is reachable from_ \(s\) _(reachability condition)._
2. \(U_{st}=U_{ts}^{+}\) _(matching condition)._
3. \(G[U_{st}]\) _is acyclic (acyclicity condition)._  
_We call \(s\), \(t\), and \(U_{st}\setminus\{s,t\}\) the entrance, exit, and interior of the superbubbloid. We denote the induced subgraph \(G[U_{st}]\) by \(\langle s,t\rangle\) if it is a superbubbloid with entrance \(s\) and exit \(t\)._  
The reachability and matching conditions can equivalently be expressed in the following form, which usually is more convenient to use:  
**Lemma 2** ([7]). : _Let \(G\) be a digraph, \(U\subset V(G)\), and \(s,t\in U\). Then, \(U\) equals the set \(U_{st}\) of Definition 1 and satisfies (S1) and (S2) if and only if the following conditions (S.i)-(S.iv) are satisfied. Moreover, \(U\) forms a superbubbloid with entrance \(s\) and exit \(t\) if and only if (S.i)-(S.vi) are satisfied:_  
1. _Every_ \(u\in U\) _is reachable from_ \(s\)_._
2. \(t\) _is reachable from every_ \(u\in U\)_._
3. _If_ \(u\in U\) _and_ \(w\
otin U\)_, then every_ \(w\to u\) _path contains_ \(s\)_._
4. _If_ \(u\in U\) _and_ \(w\
otin U\)_, then every_ \(u\to w\) _path contains_ \(t\)_._
5. _If_ \((u,v)\) _is an edge in_ \(G[U]\)_, then every_ \(v\to u\) _path in_ \(G\) _contains both_ \(t\) _and_ \(s\)_._
6. \(G\) _does not contain the edge_ \((t,s)\)_._  
If only (S.i)-(S.v) holds, the \(\langle s,t\rangle\) is a _weak superbubbloid_. A (weak) superbubble is a (weak) superbubbloid that is minimal in the following sense:  
**Definition 2**. : _A (weak) superbubbloid \(\langle s,t\rangle\) is a (weak) superbubble if there is no \(s^{\prime}\in U_{st}\setminus\{s\}\) such that \(\langle s^{\prime},t\rangle\) is a (weak) superbubbloid._  
Weak superbubbles differ from superbubbles only by (S.vi), which can be checked in constant time for each candidate (weak) superbubble. The effort to recognize superbubbles and weak superbubbles is therefore essentially the same. The following observation, which summarizes and slightly generalizes our previous analysis [7], forms the basis of the present contribution. As in previous work on the topic [5; 6; 7], DFS-trees are a key ingredient. **Lemma 3**. : _Let \(G\) be a digraph and \(U_{st}\) the vertex set of a weak superbubbloid \(\langle s,t\rangle\) in \(G\), and suppose \(r\) is not an interior vertex or the exit of \(\langle s,t\rangle\). Then, either \(V[r]\cap U_{st}=\emptyset\) or \(U_{st}\subseteq V[r]\)._  
Proof. : (i) Every digraph can be decomposed into strongly-connected components and acyclic components. If \(x\in V[r]\), then every vertex reachable from \(x\) is also contained in \(V[r]\). Thus, in particular,every strongly-connected component of \(G\) is either contained in \(V[r]\) or disjoint from \(V[r]\). [PERSON]'s theorem ([5] and [7] (Thm.1)) ensures that every superbubbloid is either contained in a strongly- connected component \(C\) or an acyclic component \(A\) of \(G\). Now, suppose \(V[r]\cap U_{st}\
eq\emptyset\), and let \(x\in U_{st}\) be the first vertex of the DFS in \(\langle s,t\rangle\). By definition (of weak superbubbloids) \(x=s\), since no other vertex in \(U_{st}\) is reachable from outside \(U_{st}\), and the DFS assumption does not start at an interior vertex or the exit of \(\langle s,t\rangle\).