# Direct Superbubble Detection
## Theory
### Cycles, \(\stackrel{{ C}}{{\sim}}\)-Covers, and \(\stackrel{{ C}}{{\sim}}\)-Cuts  
**Definition 4**. : _Let \(G\) be a digraph. A set \(C=\{c_{1},\ldots,c_{k}\}\subseteq V(G)\) is a cycle in \(G\) if \(k=|C|\) and \(E(C):=\{(c_{1},c_{2}),\ldots,(c_{k-1},c_{k}),(c_{k},c_{1})\}\subset E(G)\). A pair of vertices \(c_{i},c_{j}\in C\) determines a cycle interval:_  
\[C(c_{i},c_{j}):= \begin{cases}c_{i+1},\ldots,c_{j-1}&\text{if $i<j$}\\ c_{i+1},\ldots,c_{k}\cup c_{1},\ldots,c_{j-1}&\text{otherwise}\end{cases} \]  
By definition, the vertices \(c_{i}\) are pairwise distinct and indexed consecutively along \(C\). Importantly, cycle intervals contain only the interior of the unique path in \(C\) connecting the defining endpoints \(c_{i}\) and \(c_{j}\). Thus, \(C(c_{1},c_{2})=\emptyset\) if \((c_{1},c_{2})\in E(C)\) and \(C(v,v)=C\setminus\{v\}\) for all \(v\in C\). The _C-distance_ of two vertices \(c_{i}\) and \(c_{j}\) along a cycle \(C\) is the length of the directed path, i.e., the number of edges, from \(c_{i}\) to \(c_{j}\). More explicitly,  
\[d_{C}(c_{i},c_{j}):= \begin{cases}j-i&\text{if $i<j$}\\ j-i+k&\text{if $i\geq j$}\end{cases} =|C(c_{i},c_{j})|+1 \tag{5}\]  
since the number of inner vertices is one less than the number of edges. In particular, \(d_{C}(v,v)=|C|\) for all \(v\in C\). The _C-distance_\(d_{C}\) is not symmetric. Instead, we have \(d_{C}(u,v)+d_{C}(v,u)=|C|\) for all two vertices \(u\
eq v\in C\). Another useful consequence of the definition of \(d_{C}\) is:  
\[d_{C}(v,w)<d_{C}(v,u)\quad\implies\quad d_{C}(w,u)=d_{C}(v,u)-d_{C}(v,w) \tag{6}\]  
The following implication will be useful later on:  
**Corollary 7**. : _Let \(G\) be a digraph; let \(C\) a cycle in \(G\); and let \(c_{1},c_{2},c_{3}\in C\). Then, \(d_{C}(c_{1},c_{2})\leq d_{C}(c_{1},c_{3})\) if and only if \(c_{1}\in C(c_{3},c_{2})\cup\{c_{3}\}\)._  
Proof. : If \(c_{1}\), \(c_{2}\), and \(c_{3}\) are pairwise distinct, the l.h.s. is true if the path from \(c_{1}\) to \(c_{2}\) is a subpath of the path from \(c_{1}\) to \(c_{3}\), i.e., \(c_{1}\
otin C(c_{2},c_{3})\) and, thus, \(c_{1}\in C(c_{3},c_{2})\cup\{c_{3}\}\). The converse is obvious. The statement is trivial for \(c_{1}=c_{3}\). If \(c_{2}=c_{3}\), the l.h.s. is always true, while on the r.h.s., we have \(C(c_{2},c_{2})\cup\{c_{2}\}=C\
i c_{1}\). For \(c_{1}=c_{2}\), both the l.h.s. and the r.h.s. are satisfied only if \(c_{2}=c_{3}\). In the following, it will be useful to know whether two vertices on a cycle are also reachable via a directed path that is disjoint from \(C\). We formalize this idea as a binary relation on \(C\). **Definition 5**. : _Let \(G\) be a digraph and \(C\) a cycle in \(G\) and \(s,t\in V\). Then, \(t\) is \(C\)-reachable from \(s\), in symbols \(s\stackrel{{ C}}{{\leadsto}}t\), if there is a path \(p=\{s=v_{0},\ldots v_{h}=t\}\) such that \(h\geq 1\) and \(v_{i}\
otin C\) for \(0<i<h\)._  
We have used the letters \(s\) and \(t\) here since \(C\)-reachability will be used to identify potential candidates for entrance and exit of superbubbles. \(C\)-reachability is defined not only for vertices in the \"reference cycle\" \(C\). It satisfies a restricted transitivity property: If \(v\in V(G)\setminus C\), \(s\stackrel{{ C}}{{\leadsto}}v\), and \(v\stackrel{{ C}}{{\leadsto}}t\), then \(s\stackrel{{ C}}{{\leadsto}}t\). Anotherinteresting observation is that \(s\stackrel{{ C}}{{\rightsquigarrow}}\), \(s\) implies that there is a directed cycle \(C^{\prime}\) such that \(C\cap C^{\prime}=\{s\}\). As an immediate consequence of Definition 5, we obtain:  
**Lemma 6**. : _Let \(G\) be a digraph, \(C\) a cycle in \(G\), \(c_{1},c_{2}\in C\) such that \(c_{1}\stackrel{{ C}}{{\rightsquigarrow}}c_{2}\), and \(d_{C}(c_{1},c_{2})>1\). Then, \(c_{1}\) and \(c_{2}\) are connected by (at least) two edge-disjoint directed paths. In particular, \(\{(v_{i},v_{i+1})\mid 0\leq i<h\}\cap E(C)=\emptyset\)._  
**Definition 6**. : _Let \(C\) be a cycle in the digraph \(G\) and \(u,v\in C\).