# Direct Superbubble Detection
## 4 Conclusions  
In this contribution, we extended the body of results describing properties of superbubbles, a particular class of induced subgraphs of a digraph. The analysis presented here was motivated by the observation that in principle, all superbubbles in \(G\) can be identified in linear time in a single depth-first search, _provided_ the roots of the individual DFS-trees are known beforehand. Our main result is the observation that a suitable set of starting points, which we call quasi-legitimate roots, (1) always exists in every given digraph and (2) can be identified in linear time, using two additional DFSs. In the first pass, a suitable set of cycles is constructed such that every node in \(G\) is reachable from a source vertex of one of these cycles. In the second pass, a peculiar structure of \"detours\" in a cycle \(C\) is used to identify quasi-legitimate roots in a given cycle. To this end, we defined a notion of \(\overset{C}{\sim}\)-reachability that may also be interesting in its own right to characterize (short) cycles.  
A comparison of running times of Directbubble and previous approaches shows that practically useful performance gains are obtained essentially from two sources: (1) we dispense with the construction of auxiliary graphs and (2) we can avoid most of the processing for all vertices reachable from a source in \(G\). In practice, we observed a speedup of about a factor of three on most, but not all, benchmark cases. In all cases, Directbubble performed at least as good as all competing algorithms for superbubble detection.  
[PERSON] and [PERSON] designed the study, developed the theoretical results, and wrote the manuscript. [PERSON] implemented the algorithm and evaluated its performance.  
**Funding:** This work was funded by the German Federal Ministry of Education and Research within the project Competence Center for Scalable Data Services and Solutions (ScaDS) Dresden/Leipzig (BMBF 01 IS14014B). The authors acknowledge support from the German Research Foundation (DFG) and Universitat Leipzig within the program of Open Access Publishing.  
**Conflicts of Interest:** The authors declare no conflict of interest.  
\begin{table}
\begin{tabular}{l r r r|r r r r r} \hline \hline \multirow{2}{*}{**Data**} & \multirow{2}{*}{\(N\)} & \multirow{2}{*}{\(M\)} & \multirow{2}{*}{\(S\)} & \multicolumn{6}{c}{**Running Times (s)**} \\  & & & & Db & LSD & S & + LSD & LSD + B & S + B \\ \hline Yeast & 49,795 & 130,993 & 325 & 1 & 3 & 4 & 5 & 9 \\ EU Mail & 265,214 & 420,045 & 13,285 & 5 & 14 & 16 & 30 & 32 \\ Slashdot & 82,168 & 948,464 & 0 & 16 & 16 & 30 & 22 & 37 \\ Amazon & 403,394 & 3,387,388 & 3 & 13 & 59 & 93 & 84 & 159 \\ Google & 875,713 & 5,105,039 & 6477 & 26 & 95 & 147 & 152 & 255 \\ Wikipedia & 2,394,385 & 5,021,410 & 4737 & 52 & 160 & 164 & 382 & 418 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Comparison of running times. The five combinations of algorithms compared here are: Db (Directbubble) refers to the new approach described in this contribution. LSD (using the auxiliary graphs \(\hat{G}(C)\) and the stack-based superbubble detector) refers to the algorithm proposed in [7]. S + LSD combines the Sung graphs as auxiliary graphs [5] with LSD stack-based detector plus a post-filter for the false positives. LSD + B uses the LSD graph construction with the range-query-based detector of [6], and S + B uses Sung graphs together with the range-query-based detector, as well as the necessary post-filters; see [7] for full details. All computations were performed on a 2.5-GHz quad-core Intel Core i7 processor (Turbo Boost up to 3.7 GHz) with 6-MB shared L3 cache and 16 GB of 1600-MHz DDR3L onboard memory. Test datasets were taken from [11] and from the Stanford Large Network Dataset Collection [12]. For each test graph, we list the number of vertices \(N\), the numbers of edges \(M\), and the number \(S\) of superbubbles.