# Direct Superbubble Detection
## Theory
### Cycles, \(\stackrel{{ C}}{{\sim}}\)-Covers, and \(\stackrel{{ C}}{{\sim}}\)-Cuts
As shownin the first part of the proof, \(C(u,v)\); therefore, it is not extended by any \(B\in\mathfrak{B}\). We conclude that unless \(\mathfrak{B}\) is a total \(\overset{C}{\rightsquigarrow}\)-cover or \(\mathfrak{B}=\emptyset\), there is an interval \(B\in\mathfrak{B}\) without an extension. Figure 3 shows an example of a cycle with a total \(\overset{C}{\rightsquigarrow}\)-cover and a cycle with a \(\overset{C}{\rightsquigarrow}\)-cut, respectively. Since the largest \(\overset{C}{\rightsquigarrow}\)-interval in \(C\) is \(C(v,v)=C\setminus\{v\}\) for some \(v\), every total \(\overset{C}{\rightsquigarrow}\)-cover comprises at least two \(\overset{C}{\rightsquigarrow}\)-covered intervals. The following lemma provides us with a convenient way to obtain a total \(\overset{C}{\rightsquigarrow}\)-cover. Figure 3: \(\overset{C}{\rightsquigarrow}\)-covers. (**a**) The green cycle \(C\) in the top panel has five \(\overset{C}{\rightsquigarrow}\)-paths indicated in red. In the middle panel, \(C\) is laid out linearly to emphasize the \(\overset{C}{\rightsquigarrow}\)-covered intervals. Below, the clean \(\overset{C}{\rightsquigarrow}\)-cover obtained by removing all \(\overset{C}{\rightsquigarrow}\)-intervals that are contained in longer ones. Note that every \(\overset{C}{\rightsquigarrow}\)-interval is extended by another one; hence, the \(\overset{C}{\rightsquigarrow}\)-cover is total. (**b**) Again, the top panel highlights \(C\) in green and the \(\overset{C}{\rightsquigarrow}\)-paths in red. The linear layout below highlights that Vertex 1 is not \(\overset{C}{\rightsquigarrow}\)-covered. Thus, it is a \(\overset{C}{\rightsquigarrow}\)-cut vertex. **Lemma 9**. : _Let \(C\) be a cycle in \(G\), \(v\
ot\in C\), and \(c_{1},c_{2},c_{3},c_{4}\in C\) with \(d_{C}(c_{1},c_{3})\leq d_{C}(c_{1},c_{2})<d_{C}(c_{1},c_{4})\). Then, \(c_{1}\stackrel{{ C}}{{\leadsto}}v\), \(c_{2}\stackrel{{ C}}{{\leadsto}}v\), \(v\stackrel{{ C}}{{\leadsto}}c_{3}\), and \(v\stackrel{{ C}}{{\leadsto}}c_{4}\) imply that \(\mathfrak{B}:=\{C(c_{1},c_{4}),C(c_{2},c_{3})\}\) is a total clean \(\stackrel{{ C}}{{\leadsto}}\)-cover of \(C\)._  
Proof. : By construction, \(C(c_{1},c_{4})\) and \(C(c_{2},c_{3})\) are \(\stackrel{{ C}}{{\leadsto}}\)-covered intervals. By definition, we have \(c_{2}\in C(c_{1},c_{4})\), and \(C(c_{2},c_{3})\) extends \(C(c_{1},c_{4})\). Since \(c_{3}\in C(c_{1},c_{4})\), the two intervals cover all of \(C\). Furthermore, the cover \(\mathfrak{B}\) consists of only two intervals that are not subsets of each other; thus, it is clean. We will refer to this type of total clean \(\stackrel{{ C}}{{\leadsto}}\)-cover as a _single-vertex cover_ of \(C\). An example is shown in Figure 4.  
Cycles, \(\stackrel{{ C}}{{\leadsto}}\)-Cover, \(\stackrel{{ C}}{{\leadsto}}\)-Cuts, and Superbubbles  
A key result of [5] states that every superbubble is either contained in or disjoint of any strongly-connected components. The following results on the interaction of cycles and superbubbles are a generalization of this observation. The acyclicity condition (S.v) can be restated in the following way:  
**Lemma 10**. : _Let \(\langle s,t\rangle\) be a weak superbubloid in the digraph \(G\) and \(u\in\langle s,t\rangle\). Then, every cycle containing \(u\) also contains \(s\) and \(t\)._  
Proof. : If \(u\
eq s\), then all in-neighbors of \(u\) are contained in \(\langle s,t\rangle\). Similarly, if \(u\
eq t\), then all out-neighbors of \(u\) are contained in \(\langle s,t\rangle\). Since every cycle through \(u\) contains both in- and out-neighbors of \(u\), it, in particular, contains an edge \(e\) in \(\langle s,t\rangle\). (S.v) now implies any cycle through \(e\) contains both \(s\) and \(t\). **Lemma 11**. : _Let \(C\) be a cycle in the digraph \(G\), and let \(\mathfrak{B}\) be a total clean \(\stackrel{{ C}}{{\leadsto}}\)-cover of \(C\). If \(C(u,v)\in\mathfrak{B}\), then \(v\) is neither an interior, nor an exit of a weak superbubble, i.e., \(v\) is a legitimate root._  
Proof.