# Direct Superbubble Detection
## Theory
### Identification of Quasi-Legitimate Roots  
The obvious approach to identify quasi-legitimate roots is to construct a clean \(\stackrel{{ C}}{{\sim}}\)-cover. The obvious starting point is \(\mathfrak{L}(C)\) since it requires the construction of no more than the \(|C|\stackrel{{ C}}{{\sim}}\)-path. This can be achieved in polynomial time, e.g., using an independent DFS-tree rooted at \(c\in C\) that ignores the edges of \(C\). This naive approach, however, exceeds linear time even for a single cycle. For \(c\in C\), we construct a modified DFS-tree \(T_{c}\) by excluding all other vertices of \(C\) from \(G\). By construction, \(u\in C\) is \(\stackrel{{ C}}{{\sim}}\)-reachable from \(c\) if and only if \(T_{c}\) contains an in-neighbor \(u^{\prime}\) of \(u\), i.e., there is an edge \((u^{\prime},u)\in E(G)\) with \(u^{\prime}\in V(T_{c})\). For each \(v\in V(T_{c})\), we are interested in the vertices \(c_{\min}\in C\) and \(c_{\max}\in C\) that are \(\stackrel{{ C}}{{\sim}}\)-reachable from \(v\) and minimize and maximize \(d_{C}(c,c_{\min})\) and \(d_{C}(c,c_{\max})\). These can be recursively computed on \(T_{c}\) by traversing \(T_{c}\) in postorder. For each \(v\in V(T_{c})\), \(c_{\min}\) and \(c_{\max}\) are obtained by comparing the \(c_{\min}\) and \(c_{\max}\) values for the out-neighbors of \(v\) along \(T\), and the vertices reachable directly from \(v\). More precisely, at each leaf \(v\) of \(T_{c}\), \(c_{\max}[c,v]\) is initialized by the vertex \(c^{\prime}\in C\) such that \((v,c^{\prime})\in E(G)\) and \(c^{\prime}\) maximizes \(d_{C}(c,c^{\prime})\). At each inner vertex \(v\) of \(T_{c}\), \(c_{\max}[c,v]\) is computed as the vertex \(c^{\prime}\) maximizes \(d_{C}(c,c^{\prime})\) from the following set of candidates: \(\{c_{\max}[c,u]|(v,u)\in E(T_{c})\}\cup\{u\in C|(v,u)\in E(G)\}\). The vertex \(\stackrel{{ C}}{{\sim}}\)-reachable from \(c\) with the maximal value of \(d_{C}(c\,.\,)\) is thus \(c_{\max}[c,c]\). The same computations are used for \(c_{\min}[c,v]\), except that \(d_{C}(c,.\,)\) is minimized instead of maximized. The computations of \(T_{c}\) and values of \(c_{\min}[c,v]\) and \(c_{\max}[c,v]\) clearly can be performed in linear time. Repeating this for each \(c\in C\), however, will, in general, exceed linear time since the length \(|C|\) is not bounded in general. We can mostly reuse the information stored in \(T_{c}\), however. A crucial observation is the following:  
**Lemma 18**. : _Let \(C\) be a cycle of the digraph \(G\); consider two distinct cycle vertices \(c_{1},c_{2}\in C\); and let \(v\
otin C\) with \(c_{1}\stackrel{{ C}}{{\sim}}v\) and \(c_{2}\stackrel{{ C}}{{\sim}}v\). If \(d_{C}(c_{2},c_{\min}[c_{1},v])\leq d_{C}(c_{2},c_{\max}[c_{1},v])\), then \(c_{\min}[c_{2},v]=c_{\  
\(d_{C}(c_{1},a)\leq d_{C}(c_{1},b)\) for all \(a,b\in C(c_{3},c_{4})\cup\{c_{4}\}\). Because of Property (2), this implication can be used in particular for every \(c\in C\) for which \(v\xrightsquigarrow{C}c\) might hold. Therefore, the same two vertices minimize and maximize \(d_{C}(c_{1},\,.\,)\) and \(d_{C}(c_{2},\,.\,)\), and thus, we arrive at \(c_{\min}[c_{2},v]=c_{\min}[c_{1},v]\) and \(c_{\max}[c_{2},v]=c_{\max}[c_{1},v]\). Now, suppose \(d_{C}(c_{2},c_{4})<d_{C}(c_{2},c_{3})\). Then, \(c_{3}\
eq c_{4}\) (otherwise, the distances would be equal), and Corollary 7 implies \(c_{2}\in C(c_{3},c_{4})\cup\{c_{3}\}\). Since \(c_{1}\in C(c_{4},c_{3})\cup\{c_{4}\}\), we obtain \(d_{C}(c_{1},c_{3})\leq d_{C}(c_{1},c_{2})<d_{C}(c_{1},c_{4})\). By Lemma 9, \(\mathfrak{B}:=\{C(c_{1},c_{4}),C(c_{2},c_{3})\}\) is a one-vertex cover of \(C\). The use of Lemma 18 is that it allows either to use the \(c_{\min}[c_{1},v]\) and \(c_{\max}[c_{1},v]\) values also for \(c_{2}\), or we obtain a one-vertex \(\xrightsquigarrow{C}\)-cover, which immediately provides us with a legitimate root according to Lemma 11. Thus, we need to continue the computation of \(c_{\min}[c_{i},v]\) and \(c_{\max}[c_{i},v]\) only until we encounter a one-vertex cover.