# Direct Superbubble Detection
## Theory
### Cycles, \(\stackrel{{ C}}{{\sim}}\)-Covers, and \(\stackrel{{ C}}{{\sim}}\)-Cuts
Then, either \(\mathfrak{B}=\{\emptyset\}\) or, for every \(C(u,v)\in\mathfrak{B}\), \(d_{C}(u,v)>1\)._  
Proof. : Recall that \(C(u,v)=\emptyset\) if and only if \(d_{C}(u,v)=1\). Thus, \(\mathfrak{Q}(C)=\{\emptyset\}\) if and only if there is no \(C(u,v)\in\mathfrak{B}\) with \(d_{C}(u,v)>1\). Since the empty set is a subset of every other set, \(d_{C}(u,v)>1\) for every \(C(u,v)\in\mathfrak{B}\) unless \(\mathfrak{B}=\mathfrak{Q}(C)=\{\emptyset\}\). **Lemma 7**. : _Let \(C\) be a cycle in the digraph \(G\). Then, \(\mathfrak{Q}(C)\) contains a clean \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cover \(\mathfrak{B}\)._  
Proof. : Let \(\mathfrak{B}\subseteq\mathfrak{Q}(C)\) be a set of \(\stackrel{{ C}}{{\rightsquigarrow}}\)-covered intervals that together \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cover \(Q(C)\). Suppose \(\mathfrak{B}\) is not clean. Then, there are two intervals \(C(p,q)\in\mathfrak{B}\) and \(C(u,v)\in\mathfrak{B}\) such that \(C(p,q)\subsetneq C(u,v)\). Then, \(\mathfrak{B}^{\prime}=\mathfrak{B}\setminus\{C(p,q)\}\) still \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cover \(Q(C)\). The removal of such redundant intervals can be repeated until no further removable interval can be found. By Definition 9, the remaining \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cover is clean. **Definition 10**. : _Let \(C\) be a cycle in a digraph \(G\). Then:_  
\[\mathfrak{Q}(C)=\left\{C(u,v)\in\mathfrak{Q}(C)\ |\ \ \text{for all}\ v^{\prime}\in C \ \text{and}\ C(u,v^{\prime})\in\mathfrak{Q}(C),d_{C}(u,v^{\prime})\leq d_{C}(u,v)\right\}\]  
By definition, \(\mathfrak{Q}(C)\) consists of all \(\stackrel{{ C}}{{\rightsquigarrow}}\)-covered intervals for which there is no larger \(\stackrel{{ C}}{{\rightsquigarrow}}\)-covered interval with the same starting point. Since every \(C(p,q)\in\mathfrak{Q}(C)\setminus\mathfrak{Q}(C)\) is contained in a interval with the same starting point, \(\mathfrak{Q}(C)\) is a \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cover of \(C\). Thus, Lemma 7 implies:  
**Corollary 9**. : _Let \(C\) be a cycle in a digraph \(G\). Then, there is clean cover \(\mathfrak{B}\subseteq\mathfrak{Q}(C)\)._  
**Lemma 8**. : _Let \(C\) be a cycle in the digraph \(G\). A clean \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cover \(\mathfrak{B}\) of \(C\) is total if and only if \(\mathfrak{B}\
eq\emptyset\) and every \(B\in\mathfrak{B}\) is extended by at least one \(B^{\prime}\in\mathfrak{B}\)._  
Proof. : If \(\mathfrak{B}=\emptyset\), then \(Q(C)=\emptyset\), and thus, \(\mathfrak{B}\) is not total. In the following, we assume \(\mathfrak{B}\
eq\emptyset\) is a clean \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cover. Suppose, for contradiction, that \(C(u,v)\in\mathfrak{B}\) is not extended by any \(B\in\mathfrak{B}\). Then, any interval \(B^{\prime}\in\mathfrak{B}\stackrel{{ C}}{{\rightsquigarrow}}\)-covering \(v\) would have to contain \(C(u,v)\), contradicting the assumption that \(\mathfrak{B}\) is clean. Thus, \(v\) is a \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cut vertex, and hence, \(\mathfrak{B}\) is not total. If \(\mathfrak{B}\), therefore it is non-empty, and every \(B\in\mathfrak{B}\) is extended by some \(B^{\prime}\in\mathfrak{B}\). Conversely, suppose \(c\) is a \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cut vertex of \(C\). If \(C(u,c)\in\mathfrak{B}\) for some \(u\), then the first part of the proof implies that \(C(u,c)\) is not extended by any \(B^{\prime}\in\mathfrak{B}\). If \(\mathfrak{B}\) contains no interval \(C(u,c)\), then consider the vertex \(v\) such that \(C(u,v)\in\mathfrak{B}\) for which \(d_{C}(v,c)\) is minimal. Since \(c\) is a \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cut vertex, there is no extension of \(C(u,v)\), since any such extension \(B^{\prime}\) would either contradict the minimality of \(d_{C}(v,c)\) or \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cover \(c\), thereby contradicting the assumption that \(c\) is a \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cut vertex. Thus, \(v\) is again a \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cut vertex.