# Direct Superbubble Detection
## Theory
### Cycles, \(\stackrel{{ C}}{{\sim}}\)-Covers, and \(\stackrel{{ C}}{{\sim}}\)-Cuts
Then, \(C(u,v)\) is \(\stackrel{{ C}}{{\rightsquigarrow}}\)-covered if \(u\stackrel{{ C}}{{\rightsquigarrow}}v\)._  
As an immediate consequence of the definition, \(v\stackrel{{ C}}{{\rightsquigarrow}}v\) implies that \(C\setminus\{v\}\) is covered, while nothing is covered if \((u,v)\in E(C)\). Consider two \(C\)-intervals \(C(u,v)\) and \(C(x,y)\) on the same cycle \(C\) of the digraph \(G\). We say that \(C(u,v)\)_is included in \(C(x,y)\)_ if \(C(u,v)\subsetneq C(x,y)\), \(C(u,v)\) and \(C(x,y)\) are _disjoint_ if \(C(u,v)\cap C(x,y)=\emptyset\), and \(C(x,y)\)_extends_\(C(u,v)\) if \(d_{C}(x,v)<d_{C}(u,v)\) and \(d_{C}(x,v)<d_{C}(x,y)\). In particular, if \(C(x,y)\) extends \(C(u,v)\), then \(x\in C(u,v)\), since the interval boundaries themselves are not considered part of the \(C\)-intervals. For each pair of distinct \(C\)-intervals, thus exactly one of the following four statements is true: (a) the \(C\)-interval are disjoint; (b) one \(C\)-interval is contained in (i.e., a proper subset of) the other one; (c) one \(C\)-interval, say \(C(x,y)\), extends the other one, but not _vice versa_, i.e., \(x\in C(u,v)\) and \(y\
otin C(u,v)\); (d) both \(C\)-intervals extend each other, i.e., \(x,y\in C(u,v)\). Figure 2 illustrates the four cases. Note that in Case (c), the interval boundaries are arranged in the order \(u-x-v-y-u\)along the cycle, while in Case (d), the arrangement is \(u-y-x-v-u\) along \(C\). In the following, we will use the notation:  
\[ \begin{split}\mathfrak{Q}(C)&:=\{C(u,v)\mid u \stackrel{{ C}}{{\rightsquigarrow}}v,\,u,v\in C\}\\ Q(C)&:=\bigcup_{B\in\mathfrak{Q}(C)}B=\{w\mid \exists B\in\mathfrak{Q}(C):w\in B\}\end{split}  \tag{7}\]  
for the set of all \(\stackrel{{ C}}{{\rightsquigarrow}}\)-covered intervals and the set of all \(\stackrel{{ C}}{{\rightsquigarrow}}\)-covered vertices of \(C\), respectively. Note that \(\emptyset\in\mathfrak{Q}(C)\) since \(u\stackrel{{ C}}{{\rightsquigarrow}}v\) holds for \((u,v)\in E(C)\). By the same argument, there is at least one interval \(C(u,v)\in\mathfrak{Q}(C)\) for each \(u\in C\), albeit some or even all of these may be empty. **Definition 7**. : _A subset \(\mathfrak{B}\subseteq\mathfrak{Q}(C)\) is a \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cover of \(C\) if \(\bigcup_{B\in\mathfrak{B}}B=Q(C)\), and \(\mathfrak{B}\) is a total \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cover of \(C\) if \(\bigcup_{B\in\mathfrak{B}}B=C\). We say that \(C\) is totally \(\stackrel{{ C}}{{\rightsquigarrow}}\)-covered if \(C\) has a total \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cover._  
Note that \(C\) is totally \(\stackrel{{ C}}{{\rightsquigarrow}}\)-covered if and only if \(Q(C)=C\). Figure 2: Relationships of distinct \(C\)-intervals. The four possibilities for the relative location of two distinct \(C\)-intervals are shown on a linear layout of a cycle \(C\) with five vertices \((0,1,2,3,4)\). Left top: the \(C\)-intervals \(C(0,2)\) and \(C(2,4)\) are _disjoint_. Right top: \(C(0,4)\)_includes_\(C(1,3)\). Left bottom: \(C(1,3)\)_extends_\(C(0,2)\), but not _vice versa_. Right bottom: \(C(0,4)\) and \(C(3,1)\)_extend each other_. Together, the two \(C\)-intervals cover \(C\). **Definition 8**. : _A vertex in \(v\in K(C):=C\setminus Q(C)\) is a \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cut vertex._  
Obviously, \(C\) is either totally \(\stackrel{{ C}}{{\rightsquigarrow}}\)-covered or it has a non-empty set \(K(C)\) of \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cut vertices. **Definition 9**. : _Let \(C\) be a cycle in the digraph \(G\). \(A\stackrel{{ C}}{{\rightsquigarrow}}\)-cover \(\mathfrak{B}\) of \(C\) is clean if \(B\in\mathfrak{B}\) and \(B^{\prime}\subsetneq B\) implies \(B^{\prime}\
otin\mathfrak{B}\)._  
In other words, in a clean \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cover, no \(\stackrel{{ C}}{{\rightsquigarrow}}\)-covered interval is contained within another one. **Corollary 8**. : _Let \(C\) be a cycle in the digraph \(G\), and let \(\mathfrak{B}\) be a clean \(\stackrel{{ C}}{{\rightsquigarrow}}\)-cover.