# Direct Superbubble Detection
## Theory
### Cycles, \(\stackrel{{ C}}{{\sim}}\)-Covers, and \(\stackrel{{ C}}{{\sim}}\)-Cuts
: Assume, for contradiction, that \(v\) is an interior or the exit of the superbubble \(\langle s,t\rangle\). Since \(C\) is totally \(\stackrel{{ C}}{{\leadsto}}\)-covered by assumption, Corollary 8 implies \(d_{C}(u,v)>1\). Thus, by Lemma 6, there are (at least) two edge-disjoint paths from \(u\) to \(v\). Since neither path can leave \(\langle s,t\rangle\) before passing through \(s\), neither  
Figure 4: One-vertex cover. As in Figure 3, the cycle \(C\) and the \(\stackrel{{ C}}{{\leadsto}}\)-paths are highlighted in green and red, respectively. The paths \((0,5,4)\) and \((3,5,1)\) imply that \(C(0,4)\) and \(C(3,1)\) are \(\stackrel{{ C}}{{\leadsto}}\)-covered. It is a one-vertex cover conforming to Lemma 9.  
of them contains the entrance \(s\), and hence, both are contained in the weak superbubble. Thus, \(\langle s,t\rangle\) contains \(C(u,v)\). Since \(\mathfrak{B}\) is a total clean \(\stackrel{{ C}}{{\leadsto}}\)-cover of \(C\), there is an interval \(C(p,q)\in\mathfrak{B}\) that extends \(C(u,v)\), i.e., \(p\in C(u,v)\), and hence, \(p\) is an inner vertex of \(\langle s,t\rangle\). Therefore, \(\langle s,t\rangle\) contains \(C(p,q)\), and it again has an extending \(\stackrel{{ C}}{{\leadsto}}\)-interval. Repeating the argument, we conclude that every vertex of \(Q(C)\) is an inner vertex of \(\langle s,t\rangle\). Since the cover \(\mathfrak{B}\) is total, \(Q(C)=C\), i.e., the cycle \(C\) consists entirely of interior vertices of \(\langle s,t\rangle\), i.e., \(C\) is a proper subset of \(\langle s,t\rangle\). This contradicts the acyclicity condition (S.v). Corollary 10: _Let \(C\) be a cycle in the digraph \(G\). Suppose \(C\) is totally \(\stackrel{{ C}}{{\leadsto}}\)-covered, and let \(C(u,v)\in\mathfrak{L}(C)\) such that \(d_{C}(u^{\prime},v^{\prime})\leq d_{C}(u,v)\) for all \(C(u^{\prime},v^{\prime})\in\mathfrak{L}(C)\). Then, \(v\) is a legitimate root._  
Proof: The longest \(\stackrel{{ C}}{{\leadsto}}\)-interval \(C(u,v)\in\mathfrak{L}(C)\) by construction cannot be contained within another \(\stackrel{{ C}}{{\leadsto}}\)-interval. Therefore, \(C(u,v)\) is contained in the clean cover \(\mathfrak{B}\subseteq\mathfrak{L}(C)\) of Corollary 9. By Lemma 11, its endpoint \(v\) is a legitimate root. Let us now turn to cycles with \(\stackrel{{ C}}{{\leadsto}}\)-cut vertices:  
Lemma 12: _Let \(C\) be a cycle of the digraph \(G\), and let \(c\) be a \(\stackrel{{ C}}{{\leadsto}}\)-cut point of \(C\), i.e., \(c\in K(C)\). Then, \(c\) is not an interior vertex of any weak superbubble._  
Proof: Assume, for contradiction, that \(c\) is an interior vertex of a weak superbubble \(\langle s,t\rangle\). Then, there is a path \(p\) from \(s\) to \(t\) not passing through \(c\). Otherwise, \(\langle s,c\rangle\) is a superbubbloid, contradicting the assumption that \(\langle s,t\rangle\) is a weak superbubble; see corollary 5 in [7]. Along \(p\), let \(u\) be the last vertex on \(C\) before \(c\), and let \(v\) be the first vertex on \(C\) after \(c\). Thus, \(u\stackrel{{ C}}{{\leadsto}}v\). Therefore, \(c\) is \(\stackrel{{ C}}{{\leadsto}}\)-covered in \(C\), a contradiction. The example in Figure 5 shows that it is possible that every entrance of superbubble is at the same time the exit of another superbubble. Such graphs do not have any legitimate root. Nevertheless, it is easily possible to obtain all the superbubbles. To this end, fix a \(\stackrel{{ C}}{{\leadsto}}\)-cut vertex \(c\) for some cycle \(C\) in \(G\), and consider the auxiliary digraph \(G^{\#}\) obtained from \(G\) by splitting \(c\) into two vertices \(c^{\prime}\) and \(c^{\prime\prime}\) so that \(c^{\prime}\) retains only the in-edges and \(c^{\prime\prime}\) retains only the out-edge. Lemma 13: _Let \(C\) be a cycle in the digraph \(G\), \(c\in C\) a \(\stackrel{{ C}}{{\leadsto}}\)-cut vertex, and \(G^{\#}\) the digraph obtained from \(G\) by splitting \(c\).