# Direct Superbubble Detection
## Theory
### Cycles, \(\stackrel{{ C}}{{\sim}}\)-Covers, and \(\stackrel{{ C}}{{\sim}}\)-Cuts
We refer to this algorithm, which is equivalent to applying Superbubble to \(G^{\#}\), as Superbubble#. **Definition 11**. : _Let \(G\) be a digraph. Then, \(r\in V\) is a quasi-legitimate root if either:_  
1. \(r\) _is source in_ \(G\)_,_
2. \(r\) _is the end point of an interval_ \(C(u,r)\in\mathfrak{B}\) _of a total clean_ \(\overset{C}{\rightsquigarrow}\)_-cover of some cycle_ \(C\) _in_ \(G\)_, or_
3. \(r\) _is_ \(\overset{C}{\rightsquigarrow}\)_-cut vertex of some cycle_ \(C\) _in_ \(G\)  
Figure 5: A digraph \(G\) without any legitimate root. In \(G\) are 16 isomorphic cycles containing eight of the 12 vertices, all of which contain \(\{1,3,5,7\}\). The superbubbles \(\langle 1,3\rangle\), \(\langle 3,5\rangle\), \(\langle 5,7\rangle\), and \(\langle 7,1\rangle\) cover \(G\) entirely, i.e., every entrance of a superbubble is also the exit of another one, and all other vertices are interior vertices of a superbubble. Our discussion so far can be summarized as:  
Corollary 11: _Algorithm Superbubble# correctly identifies the superbubbles in \(G[V[r]]\) if and only if \(r\) is a quasi-legitimate root._  
As an immediate consequence of Lemmas 11 and 12, every cycle contains a quasi-legitimate root. Recalling that every vertex in the digraph \(G\) can be reached either from a source vertex or from a cycle, we finally obtain:  
Theorem 2.2: _Every digraph \(G\) contains a set of quasi-legitimate roots \(\{r_{1},r_{2},\ldots,r_{k}\}\). Given these roots, the algorithm Superbubble# correctly identifies all superbubbles of \(G\) in linear time._  
It remains to show, therefore, that a suitable set of roots can be identified in linear time. Clearly, this is possible for the sources. For superbubbles that cannot be reached from a source vertex, a suitable set of cycles needs to be identified. Lemma 14: _Let \(F=(T[v_{1}],T[v_{2}],\ldots,T[v_{k}])\) be an arbitrary DFS-forest of \(G\) with constituent ordered trees \(T[v_{i}]\) rooted at \(v_{i}\), and let \(C\) be a cycle in \(G\). Then, \(C\cap V(T[v_{i}])\
eq\emptyset\) implies \(C\subseteq V(T(v_{i}))\), and there is a \(u\in C\) such that \(C\subseteq V(T[u])\)._  
Proof: Let \(v_{i}\) be the first root of \(F\) that can reach any vertex of \(C\). Then, by definition of a cycle, \(C\in V[v_{i}]\). Thus, \(C\subseteq V(T[v_{i}])\). Further, let \(u\) be the first vertex that is reached from \(v_{i}\) in the DFS. Then, every other vertex of \(C\) is reached from \(u\) in the DFS. Thus, \(C\subseteq V(T[u])\). The same is true for strongly-connected components:  
Lemma 15: _[_8_]_ _(corollary 11) Let \(S\) be a strongly-connected component in \(G\), and let \(T\) be a DFS-tree with \(S\subseteq V(T)\). Then, there is a vertex \(v\in S\) such that \(S\subseteq V(T[v])\). We call \(v\) the root of the strongly-connected component \(S\) in \(T\)._  
Our aim is now to find a set of \"start cycles\" such that every cycle \(C\) is reachable from at least one of these start cycles. Lemma 16: _Let \(T\) be a DFS-tree on the digraph \(G\) rooted in \(v\), and let \(W\) be the set of \(\prec\)-maximal vertices \(w\) that have an incoming back edge \((u,w)\). Then, (i) \(w\in W\) is contained in a cycle, and (ii) every cycle \(C\subseteq V(T)\) is satisfied \(C\subseteq V(T[w])\) for some \(w\in W\)._  
Proof: Property (i) is an immediate consequence of the definition of DFS. Now, suppose \(u\
otin V(T[w])\) for some \(w\in W\). Then, by construction, none of the vertices along the path from the root \(v\) to \(u\) have an incoming back edge, and thus, neither \(u\), nor one of its ancestors are contained in a cycle. Thus, if \(x\in C\) for some cycle \(C\subseteq V(T)\), then a vertex \(w\in W\) exists such that \(x\in V(T[w])\), and thus, \(C\subseteq V(T[w])\). Note that \(W=\emptyset\) if \(T[v]\) does not contain a cycle.