Identifying bubble-like subgraphs in linear-time via a unified SPQR-tree framework Francisco Sena, Aleksandr Politov ∗, Corentin Moumard, Massimo Cairo, Romeo Rizzi, Manuel Cáceres, Sebastian Schmidt †, Juha Harviainen †, Alexandru I. Tomescu † Abstract A fundamental algorithmic problem in computational biology is to find all subgraphs of a given type— superbubbles , snarls , and ultrabubbles —in a directed or bi directed input graph. Such bubble-like subgraphs correspond to regions of genetic variation, whose identification is useful in analyzing collections of genomes (a pangenome graph ). At present, all subgraphs of the latter two types can only be found in quadratic time, which constitutes a major bottleneck for applications involving massive inputs. Although all superbubbles can be identified in linear time, the existing algorithm is highly specialized and the result of a long sequence of tailored developments. In this work, we present the first linear-time algorithms for identifying all snarls and all ultrabubbles, resolving problems that have remained open since 2018. Additionally, the algorithm for snarls relies on a new linear-size representation of all snarls with respect to the number of vertices in the graph. For the first time in this context, we make use of the well-known SPQR-tree decomposition, which encodes all 2-separators of a biconnected graph. By performing several dynamic-programming–style traversals of this tree, we maintain key properties (such as acyclicity) that allow us to decide whether a given 2-separator defines a subgraph to be reported. A crucial ingredient for achieving linear-time complexity is the observation that the acyclicity of linearly many subgraphs can be tested simultaneously via a reduction to the classical problem of computing all arcs in a directed graph whose removal renders it acyclic (so-called feedback arcs ). As such, we prove a fundamental result for bidirected graphs, that may be of independent interest: all feedback arcs can be computed in linear time for tipless bidirected graphs, while in general graphs the problem is at least as hard as matrix multiplication, assuming the k k -Clique Conjecture. Altogether, our results form a unified framework that also yields a completely different linear-time algorithm for finding all superbubbles. Although some of the results are technically involved, the underlying ideas are conceptually simple, and may extend to other bubble-like subgraphs. More broadly, our work contributes to the theoretical foundations of computational biology and advances a growing line of research that uses SPQR-tree decompositions as a general tool for designing efficient algorithms, beyond their traditional role in graph drawing. 1 Introduction 1.1 Background and motivation Recent bioinformatics applications in pangenomics are concerned with building a single massive graph representing many genomes in a population. For example, the Human Pangenome Reference Consortium (HPRC) [ 37 ] released in May 2025 a pangenome graph created from 232 individual genomes, 1 1 1 https://humanpangenome.org/hprc-data-release-2/ which contains over 206 million edges [ 3 ] . The size of such graphs is expected to significantly increase in the future. For example, HPRC is planning to release in Summer 2026 a larger graph created from 350 individual genomes, 2 2 2 https://humanpangenome.org/release-timeline/ and there are other initiatives worldwide aiming to construct such graphs from many more human genomes, such as the European ‘‘1+ Million Genomes’’ initiative. 3 3 3 https://digital-strategy.ec.europa.eu/en/policies/1-million-genomes An advantage of pangenome graphs is that genetic variation translates into local substructures, with clean graph-theoretic characterizations, that can be found and analyzed for biological meaning. One of the most used type of such subgraph of a directed graph is a superbubble [ 44 , 7 ] , see Figure 1 (a). A superbubble is an acyclic subgraph B identified by two endpoint vertices, say s and t , such that s is the only source of B and s does not have out-neighbors outside of B ; and symmetrically, t is the only sink of B and t does not have in-neighbors outside of B . Additionally, there are no other edges from B to the rest of the graph, and a minimality property is also imposed to ensure overall a linear number of superbubbles. See also [ 33 , 49 , 41 , 51 , 19 ] for other applications of superbubbles. The development of pangenome graphs led to the introduction of generalizations of superbubbles, to explicitly handle the bi directed nature of the graphs that arises from the reverse-complementary symmetry of DNA. In a bidirected graph 4 4 4 Bidirected graphs, though not as widely known, are well represented in the literature; see e.g. [ 17 ] (STOC 1983) and [ 50 , Chapter 36] . , every edge also carries a sign + or - at each endpoint. For example, between two vertices u and v there can be four bidirected edges: \{u-,v-\} , \{u-,v+\} , \{u+,v-\} and \{u+,v+\} (as unordered pairs). A vertex v together with a sign + or - is called a vertex-side [ 47 ] . Directed graphs are a special case of bidirected graphs: every directed edge (u,v) is encoded as \{u+,v-\} . Bidirected graphs are heavily used in bioinformatics, and we refer the reader to e.g. [ 2 , 39 , 32 , 47 ] for further motivation on bidirected graphs. Figure 1 : Examples of superbubbles (a), snarls (b), and ultrabubbles (d) in directed graphs and bidirected graphs, with the extremities of the bubbles highlighted in the same color. The superbubbles are (c,b) and (b,e) , the snarls are \{a+,b-\} , \{a+,c-\} , \{b-,c-\} , \{b+,e+\} , \{d+,f-\} , and \{d-,f+\} , and the ultrabubbles are \{b-,c-\} and \{b+,e+\} . Subfigure (c) illustrates splitting vertex sides d+ and f- from (b), after which d and f are in the same connected component that is distinct from the component of d^{\prime} and f^{\prime} . Note that all pairs of a+ , b- , and c- form snarls in (b), whereas with superbubbles and ultrabubbles each vertex-side can be an extremity of only a single bubble. In bidirected graphs, the most well-known bubble-like notions are snarls (see Figure 1 (b)) and ultrabubbles (see Figure 1 (d)), introduced by 46 . At a high level, a snarl is a minimal connected subgraph identified by two vertex-sides that separate its interior from the rest of the graph; moreover, at each of the two endpoints, all vertex-sides of one sign lie inside the snarl and all vertex-sides of the opposite sign lie outside. Ultrabubbles are snarls whose interior contains no tip and is acyclic , i.e. it contains no closed bidirected walk . A tip is a generalization of a source/sink in directed graphs: it is a vertex v for which all incident edges carry the same sign at v . A bidirected walk alternates the sign at every internal vertex; it is closed if it starts and ends at the same vertex, at which it does not need to alternate sign. We also call such a walk a cycloid . See also [ 20 , 27 , 55 , 6 , 53 , 52 ] for important applications of snarls and ultrabubbles. 1.2 Existing bubble-finding algorithms Given a directed graph (V,E) , the first superbubble finding 5 5 5 The interior of a bubble is uniquely identified by its endpoints, and thus bubble-finding algorithms compute the set of pairs of endpoint vertices of all bubbles of a certain type. In fact, since bubble subgraphs can contain smaller bubble subgraphs, one cannot obtain linear-time algorithms if the full subgraphs are reported in output. algorithm ran in time O(|V|(|E|+|V|)) [ 44 ] , and was later improved to O(\log|V|(|E|+|V|)) -time [ 54 ] . Linear time O(|V|+|E|) was first achieved for acyclic graphs by 5 , then for general graphs by 21 , and further simplified by 22 . Despite the massive size of pangenome graphs, existing worst-case bounds for these bidirected structures are far from linear: snarls can be computed in O(|V||E|) time in the worst case, and ultrabubbles in O((|V|+|E|)^{2}) time [ 46 ] . Another intrinsic difficulty is output size, as the total number of snarls can be quadratic in the number of vertices. 46 therefore used the cactus graph [ 45 ] to prune snarls and compute in linear time a snarl decomposition of linear size. However, because of their possible biological significance, we are interested in identifying all bubble-like structures in the graph. 56 recently proposed an algorithm which, given a set of k snarls, can verify in time O(k|V|+(|V|+|E|)) which ones are ultrabubbles. Finally, 26 showed that ultrabubbles can be computed in linear time on the special class of bidirected graphs that either contain a tip or their underlying undirected graph contains a cutvertex. This is based on transforming any bidirected graph in this class into a directed graph which is at most of double size, such that the ultrabubbles of the bidirected graph correspond exactly to (a slight generalization of) superbubbles in the directed graph. However, note that this reduction does not work in general. Despite the similarities between the several existing bubble-like structures (see also e.g. bibubbles [ 36 ] , panbubbles [ 3 ] , and flubbles [ 43 ] ), there is no unified methodology for efficiently computing them. Moreover, since superbubbles can indeed be computed in linear time, it would seem reasonable to assume that such an approach can be adapted also for snarls. However, this achievement is heavily tailored to superbubbles and crucially relies on the directed nature of the input graph. Finally, this result has been obtained only after a series of papers [ 44 , 54 , 5 , 21 , 22 ] , begging the question of how large undertaking obtaining a linear-time snarl or ultrabubble identification algorithm is. 1.3 Contributions In this paper we show that all snarls and all ultrabubbles can be identified in linear time in the size of the graph, solving problems that have been open since 2018. For snarls, we further prove that the set of all snarls admits a representation of size linear in the number of vertices of the input graph, which can itself be constructed in linear time. Thus, we can identify all snarls in time linear in the input size. We obtain both algorithms via a unified framework for finding these structures. This framework also yields a new linear-time algorithm for computing all superbubbles in directed graphs. The key insight underlying our approach is that the two endpoints of a bubble subgraph form a 2-separator (i.e. 2-vertex cut) in the underlying undirected graph, except for special cases which we can handle separately. We then leverage classical decomposition machinery for 2-separators, namely the SPQR tree of a (bi)connected graph [ 9 , 25 ] , which compactly encodes all its 2-separators. While SPQR trees have been used in bioinformatics in other contexts (e.g. [ 15 , 31 ] ), they have not been used to algorithmically capture bubble-like structures. More broadly, although SPQR trees are most commonly associated with graph embedding and drawing applications [ 42 ] , our work contributes to a growing line of research that employs them to design efficient algorithms. For example, recognizing if a graph belongs to a certain class [ 8 ] , or constructing efficient indexing schemes for e.g. shortest-path queries [ 38 ] . Although some of the results are technically involved, the underlying ideas are conceptually simple. This suggests that the same framework may extend to other bubble-like notions, such as bibubbles [ 36 ] and panbubbles [ 3 ] , for which linear-time algorithms are currently unknown. 1.4 Organization of the paper In Section 2 we introduce key technical notions, and in Section 3 we give an extended overview of our main ideas. To better illustrate our framework, we first apply it to standard directed graphs and present the new linear-time superbubble algorithm, in Section 4 . Our goal in the presentation is to illustrate the key ideas, which we can then adapt to the more involved case of bidirected graphs. We show the linear-time snarl algorithm in Section 5 , and the results on ultrabubbles in Section 6 . 2 Preliminaries Many of our results are based on analyzing the underlying undirected graph of the (bi)directed graph we wish to find superbubbles, ultrabubbles, or snarls. We begin by giving preliminaries on undirected graphs and basic terminology on connectivity. Then we introduce terminology for bidirected and directed graphs. 2.1 Undirected graphs and connectivity Let H=(V,E) be an undirected graph with vertex set V(H) and edge set E(H) . Let u,v\in V(H) be vertices. If H has an edge with endpoints u and v then we denote that edge as \{u,v\} (parallel edges are allowed). A u - v undirected walk in H is a standard walk between u and v ; a u - v undirected path is a u - v undirected walk without repeated vertices. The internal vertices of a u - v undirected path are the vertices contained in the path except u and v . (When clear from the context, we simply say “path” instead of undirected “path”.) A subgraph H of G is maximal w.r.t. a given property if no proper supergraph of H contained in G has that property. The subgraph induced by a subset C\subseteq V(G),E(G) of vertices or edges of G is denoted by G[C] . The vertex-induced subgraph is the graph with vertex set C and the subset of edges in E(G) whose endpoints are in C . The edge-induced subgraph has edge set C and a vertex set consisting of all endpoints of edges in C . If G^{\prime}=(V^{\prime},E^{\prime}) is an undirected graph, then G^{\prime}\cup G:=(V\cup V^{\prime},E\cup E^{\prime}) . Graph H is disconnected if it has two vertices without a path between them. Graph H is k -connected if it has more than k vertices and no subset of fewer than k vertices disconnects the graph. By Menger’s theorem [ 40 ] , if a graph H is k -connected then H has k internally vertex-disjoint paths between any two of its vertices. A component of H is a maximally (1-)connected subgraph. Vertex v is a cutvertex of H if H-v has more components than H ; if H has no cutvertex then it is biconnected . The vertex pair \{u,v\} is a separation pair of H if (H-u)-v has more components than H ; if H has no separation pairs then it is triconnected . Notice that we allow biconnected (resp. triconnected) graphs to have fewer than three (resp. four) vertices. We call an edge a bridge if its removal increases the number of components of the graph; a set of at least two parallel edges whose removal increases the number of components of the graph is called a multi-bridge . If every u - v path contains vertex w\neq u,v then w is a u - v cutvertex. A separation of H is a pair of vertex sets (A,B) such that V=A\cup B , A\setminus B and B\setminus A are nonempty, and there is no edge between A\setminus B and B\setminus A . A maximal set of vertices X\subseteq V(H) with |X|\geq k such that no two vertices of X can be separated by removing fewer than k other vertices is called a k -block . 2.2 Bidirected and directed graphs A bidirected graph G=(V,E) has a set of vertices V=V(G) and a set of bidirected edges E=E(G) . A sign is an element in \alpha\in\{+,-\} , and the opposite sign \hat{\alpha} of \alpha is defined as \hat{-}=+ and \hat{+}=- . A pair (v,\alpha) where v\in V(G) and \alpha\in\{+,-\} is a vertex-side , 6 6 6 We adopt this nomenclature from [ 48 ] and note that [ 32 ] opts for “signed vertex”. We remark that our definition of bidirected graph, while appropriate for this work, differs from commonly used definitions (e.g., [ 32 , 23 , 2 , 1 , 50 ] ) although all are essentially equivalent. which we concisely write as v\alpha , e.g. v+ or v- . A bidirected edge e\in E(G) is an unordered pair of vertex-sides \{u\alpha,v\beta\} (for simplicity we may refer to bidirected edges as just edges); we say that e is incident to u (resp. v ) with sign \alpha (resp. \beta ), that G has a vertex-side of sign \alpha in u , and that u and v are the endpoints of e . The set of vertex-sides of G is the set \bigcup_{e\in E(G)}e . A bidirected graph H is a subgraph of G if V(H)\subseteq V(G) and E(H)\subseteq E(G) , and write H\subseteq G . The set of out-neighbors of v is denoted as N^{+}_{G}(v) and consists of the vertices x for which there is an edge \{v+,x\beta\} in G (the set of in-neighbors is defined analogously). We say that a vertex v is a tip in G if no two edges of G are incident to v with different signs. The undirected graph of G is denoted by U(G) and is obtained from G by ignoring the signs in its vertex-sides, and keeping parallel edges that possibly appear (edges are thus labeled with unique identifiers that are retained during the conversion). A bidirected walk W is a sequence \{v_{1}\alpha_{1},v_{2}\alpha_{2}\} , \{v_{2}\hat{\alpha}_{2},v_{3}\alpha_{3}\},\dots,\{v_{k-1}\hat{\alpha}_{k-1},v_{k}\alpha_{k}\}\in E(G) . We also say that W is a v_{1} - v_{k} bidirected walk (also a v_{1}\alpha_{1} - v_{k}\alpha_{k} , a v_{1} - v_{k}\alpha_{k} , or a v_{1}\alpha_{1} - v_{k} bidirected walk). When clear from the context we may say simply “walk” instead of “bidirected walk”. Vertices x and y are the first and last vertices of the walk, respectively, and all remaining vertices are its internal vertices. Observe that to any walk W we can associate its reversed walk (i.e., walks in bidirected graphs have two possible orientations). A bidirected path is a walk without repeated vertices. A cycloid is a path with the exception that the first and last vertex are the same and where at most one of its vertices (called the exceptional vertex ) has the same sign over the two edges incident to it in the sequence. A graph with no cycloid is acyclic . When every edge of G has one vertex-side with a + sign and the other with a - sign then we can say that G is a directed graph where a bidirected edge \{u+,v-\} is seen as a directed edge from u to v , which we concisely denote as uv . A directed path is a sequence of vertices v_{1}\dots v_{k} such that v_{i}v_{i+1}\in E(G) for i=1,\dots,k-1 , in which case we also say that v_{1} reaches v_{k} in G or that this sequence is a v_{1} - v_{k} directed path . A vertex v is a source of G if |N^{-}_{G}(v)|=0 and a sink if |N^{+}_{G}(v)|=0 . A vertex v is an extremity of G if v is a source or sink of G , or a cutvertex of U(G) . 2.3 Block-cut trees Let H=(V,E) be an undirected connected graph with at least two vertices. It follows from the definition of k -block that a subgraph induced by a 2-block is a maximal connected subgraph without cutvertices (see [ 13 ] ). For simplicity, we will refer to the subgraphs induced by 2-blocks simply as blocks. The block-cut tree of H is a tree with node set N and edge set A . A node is a block node , which is either a maximal 2-connected subgraph or a multi-bridge of H , or a cutnode , which is a cutvertex of H . The edges in A represent how the blocks of H interact via the cutvertices of H as follows. Let v be a cutvertex of H and let \mu be the cutnode of N corresponding to v . Then H-v consists of components C_{1},\dots,C_{\ell} ( \ell\geq 2 ) and \mu has \ell neighbours in the tree, each corresponding to the block contained in H[V(C_{i})+v] that meets v . The blocks partition the edge set of H [ 13 ] and there is at most one block containing any two vertices. 2.4 SPQR trees SPQR trees represent the decomposition of a biconnected graph according to its separation pairs in a tree-like way, thus exposing the 3-blocks of the graph (analogously to cutvertices and blocks in block-cut trees). They were first formally defined by Tamassia and Di Battista [ 9 ] , but were informally known before [ 35 , 29 , 4 ] . They can be constructed in linear time [ 29 , 25 ] , and if unrooted they are unique [ 9 ] . SPQR trees are a valuable tool in the design of algorithms for different problems [ 28 , 11 , 10 ] . The definition of SPQR trees given in this paper is essentially the same given by Di Battista and Tamassia in [ 9 , 12 , 11 ] ; note that the exact same recursive definition is used in [ 25 , 24 ] (for a non-recursive definition see [ 28 ] ). We remark that our definition contains some minor technical adjustments to the definition of Di Battista and Tamassia. Figure 2 : A directed graph (left) and the SPQR tree of its (biconnected) underlying undirected graph (right). Virtual edges are dashed, tree edges (in blue) connect pairs of virtual edges in adjacent tree nodes, and node types (S, P, R) are shown in blue. We highlight in red a virtual edge e_{\nu} and show its \expansion(e_{\nu}) in the red box. The \skel(\mu) of the tree node \mu (the top-most node) is shown in the blue box. The directed skeleton \dirskel(\mu) is a directed graph obtained from \skel(\mu) where real edges are directed as in the input directed graph, and for each e=\{s,t\} in \skel(\mu) we add an edge from s to t (and from t to s ) if s reaches t (or t reaches s , resp.). To define SPQR trees we need some basic definitions. Let H be an undirected biconnected graph with at least two edges. A split pair of H is a separation pair or an edge of H . A split component of a split pair \{u,v\} is an edge \{u,v\} or a maximal subgraph C of H containing the vertices u and v such that \{u,v\} is not a split pair of C . Let \{s,t\} be a split pair of H . A maximal split pair \{u,v\} of H with respect to \{s,t\} is such that for any other split pair \{u^{\prime},v^{\prime}\} vertices u,v,s , and t are in the same split component of \{u^{\prime},v^{\prime}\} . Fix an arbitrary edge e=\{s,t\}\in E(H) , called the reference edge . The SPQR tree T of H with respect to e is defined as a rooted tree with nodes of four types: S (series), P (parallel), Q (single edge), and R (rigid). Each node \mu in T has an associated biconnected graph \skel(\mu) , called the skeleton of \mu with V(\skel(\mu))\subseteq V(H) . The tree T is recursively defined as follows: Trivial case: If H consists of exactly two parallel edges between s and t , then T consists of a single Q-node whose skeleton is H itself. Parallel case: If the split pair e=\{s,t\} has exactly k+1\geq 3 split components H_{0},\dots,H_{k} where H_{0} denotes the split component containing e , then the root of T is a P-node \mu whose skeleton consists of k+1 parallel edges e_{0},\dots,e_{k} between s and t with e_{0}=e . Series case: Otherwise the split pair \{s,t\} has exactly two split components, where one is e trivially and the other let us denote by H^{\prime} . If H^{\prime} is a sequence of blocks H_{1},\dots,H_{k} separated by cutvertices c_{1},\dots,c_{k-1} (k\geq 2) in this order from s to t , then the root of T is an S-node \mu whose skeleton is a cycle e_{0},e_{1},...,e_{k} where e_{0} = e , c_{0}=s , c_{k}=t , and e_{i}=(c_{i-1},c_{i}) (i=1,\dots,k) . Rigid case: If none of the previous cases applies, let \{s_{1},t_{1}\},\dots,\{s_{k},t_{k}\} be the maximal split pairs of H with respect to \{s,t\} (k\geq 1) , and, for i=1,\dots,k let H_{i} be the union of all the split components of \{s_{i},t_{i}\} except the one containing e . The root of T is an R-node \mu whose skeleton is obtained from H by replacing each subgraph H_{i} with the edge e_{i}=\{s_{i},t_{i}\} . Except for the trivial case, \mu has children \mu_{1},\dots,\mu_{k} , such that \mu_{i} is the root of the SPQR tree of H_{i}\cup e_{i} with respect to e_{i} for i=1,\dots,k . Notice how the (reference) edge e_{i} in \skel(\mu_{i}) ensures that \skel(\mu_{i}) is biconnected (e.g., in the case of the S-node). Once the recursion terminates, we add a Q-node with vertex set \{s,t\} representing the first reference edge e=\{s,t\} and make it a child of the root of T . Node \mu_{i} is associated with edge e_{i} of the skeleton of its parent \mu , called the virtual edge of \mu_{i} in \skel(\mu) (i=1,\dots,k) . Conversely, \mu is implicitly associated with the reference edge e_{i} in \skel(\mu_{i}) . Notice that reference and virtual edges encode the same information: two subgraphs of H and how they attach to each other. Indeed, a reference edge of some node is just another virtual edge with the additional property of pointing to the parent of that node. We say that \mu is the pertinent node of e_{i}\in E(\skel(\mu_{i})) (or that e_{i}\in E(\skel(\mu_{i})) pertains to \mu ), and that \mu_{i} is the pertinent node of e_{i}\in E(\skel(\mu)) (or that e_{i}\in E(\skel(\mu)) pertains to \mu_{i} ). Additional definitions. For simplicity, we will omit Q-nodes from the SPQR tree. This amounts to replacing every virtual edge pertaining to a Q-node by a real edge and removing every Q-node from the tree. The edges of a skeleton are then either real or virtual. Suppose now that \nu is the parent of \mu in T . Let e_{\nu}\in\skel(\mu) be the edge pertaining to \nu and let e_{\mu}\in\skel(\nu) be the edge pertaining to \mu . Let \{s,t\} be the endpoints of e_{\nu} and e_{\mu} . Deleting the edge \{\nu,\mu\} from T disconnects T into two subtrees, T_{\nu} containing \nu and T_{\mu} containing \mu . The expansion graph of e_{\nu} , denoted as \expansion(e_{\nu}) , is the subgraph induced in H by the real edges contained in the skeletons of the nodes in T_{\nu} . The graph \expansion(e_{\mu}) is defined analogously with respect to T_{\mu} . The expansion of a real edge is the graph consisting of that edge alone. Each edge of T (importantly, without Q-nodes) encodes a separation of H (i.e., (V(\expansion(e_{\nu})),V(\expansion(e_{\mu}))) is a separation of H ). Further, we have V(\expansion(e_{\nu}))\cap V(\expansion(e_{\mu}))=V(\skel(\nu))\cap V(\skel(\mu))=\{s,t\} and \expansion(e_{\nu})\cup\expansion(e_{\mu})=H . For every node \mu of T whose skeleton has edge set \{e_{1},\dots,e_{k}\} , the graph \bigcup_{i=1}^{k}\expansion(e_{i}) is exactly H . In SPQR trees no two S-nodes and no two P-nodes are adjacent [ 11 ] . The next two statements are well known results about SPQR trees. Lemma 2 below is given in a context where Q-nodes are part of the tree. Clearly, removing Q-nodes maintains the bounds. Lemma 1 (SPQR trees and separation/split pairs) . Let H be an undirected 2-connected graph and let T be its SPQR trees with Q-nodes omitted. For each S-node \mu of T , let X_{\mu} denote the set of all pairs of nonadjacent vertices in \skel(\mu) . Then the union of the virtual edges over the skeletons of the nodes of T together with the union of all the X_{\mu} is exactly the set of separation pairs of H . If Q-nodes are included in the tree, then this union is exactly the set of split pairs of H . Lemma 2 (SPQR trees require linear space [ 10 ] ) . Let H=(V,E) be an undirected biconnected graph. The SPQR tree T of H has O(|V(H)|) nodes and the total number of edges in the skeletons is O(|E(H)|) . The next simple result is merely technical and will be used throughout in the paper. Lemma 3 . Let G be a bidirected graph, H be a 2-connected subgraph of G , and T be the SPQR tree of H . Let \mu be a node of T , e=\{u,v\} be a virtual edge of \skel(\mu) , and a\in V(H)\setminus\{u\} be a vertex. If a\in V(\expansion(e)) then \expansion(e) has an a - v path avoiding u . Proof. If a=v we are done, so a\neq v . Suppose for a contradiction that every a - v path in \expansion(e) contains u . Since a is contained in a split component of \{u,v\} , every a - v path in H also contains u . So u is an a - v cutvertex in H , contradicting the fact that H is 2-connected. ∎ A remark on notation. To simplify the writing we will refer to connectivity properties of the underlying undirected graph of a bidirected graph by saying that the bidirected graph itself has the property, as to minimize the use of the cumbersome notation U(G) . For instance, if G is a bidirected graph such that U(G) is 2-connected and where x is a u - v cutvertex, then we say that G is 2-connected and that x is a u - v cutvertex with the meaning that U(G) has those properties. The only possible ambiguity arising from this choice is on the notion of “walk”. For that, we carefully specify what kind of walk we are referring to by using the terms “(bi)directed” and “undirected” as they were defined previously; only when it is clear from the context, we allow ourselves to simply say “walk”. We also build block-cut trees and SPQR trees directly on bidirected graphs (connectivity is seen from their underlying undirected graphs). The edges contained in the blocks of block-cut trees, in the skeletons of the nodes of SPQR trees, in split components, etc, additionally encode their relevant properties in the (bi)directed graph they live in. This applies also to the \expansion operator in SPQR trees. We will routinely solve subproblems on the skeletons whose edges are assigned directions depending on the reachability relation of G restricted to their respective expansions. Formally, let \mu be a node of T and let e_{1}=\{s_{1},t_{1}\},e_{2}=\{s_{2},t_{2}\},\dots,e_{k}=\{s_{k},t_{k}\} be the edges of \skel(\mu) (k\geq 2) . Define the set of directed edges B_{1}=\{s_{i}t_{i}:\text{$s_{i}$ reaches $t_{i}$ in $\expansion(e_{i}),\;i=1,\dots,k$}\} and B_{2}=\{t_{i}s_{i}:\text{$t_{i}$ reaches $s_{i}$ in $\expansion(e_{i}),\;i=1,\dots,k$}\} . We define the directed skeleton of \mu as \dirskel(\mu):=(V(\skel(\mu)),B_{1}\cup B_{2}) . 3 Overview of our results and techniques In this section, we will give a high-level description of the results and the techniques behind them. We start by informally defining the bubble-like structures (or just bubbles) we are interested in, as they will be formally defined in Sections 4 , 5 and 6 , respectively. Next, we give more details on how we handle the bubbles of each type. In this paper we assume that (bi)directed graphs have no parallel edges since they have no effect on superbubbles, ultrabubbles, and snarls (two edges \{x\alpha,y\beta\} and \{z\gamma,w\delta\} are parallel if x=z , \alpha=\gamma , y=w , and \beta=\delta ). 3.1 Bubble-like subgraphs All bubbles we consider are characterized by two vertices u and v that are the “extremities”, or “endpoints“ of the bubble. Intuitively, if one enters a bubble from the outside of the bubble, they have to go through an extremity and similarly exit through an extremity. In other words, the extremities form a 2-separator of the underlying undirected graph in the sense that their removal separates the interior of the bubble from the rest of the graph (except fo special cases which we can handle separately). We actually require a mildly stronger property that is formalized under the notion of splitting , where we pick a vertex v and a direction (for directed graphs) or a vertex-side v+ or v- (for bidirected graphs), create a copy v^{\prime} of v , and finally detach the edges of the opposing direction/vertex-side from v and reattach them to v^{\prime} . This is illustrated in Figure 1 (c). We then require that a bubble characterized by the extremities u and v has u and v in the same connected component that is separated from u^{\prime} and v^{\prime} after splitting u and v . Further, all our bubbles have to be minimal , intuitively meaning that they are not obtainable by concatenating smaller bubbles. Snarls are precisely defined by these separability and minimality properties in bidirected graphs, with examples provided in Figure 1 (b)–(c). Snarls are relatively weak bubbles in the sense that they lack any assumptions about their interior such as all internal vertices being reachable from an extremity in (bi)directed sense. In contrast, superbubbles and ultrabubbles require that the component containing u and v after splitting them has no cycloids and that for any internal vertex w there is a (bi)directed walk (path, in fact) from one extremity to another that goes through w . Superbubbles and ultrabubbles are illustrated in Figure 1 (a) and (d), respectively. Figure 3 : Superbubbles, snarls and ultrabubbles in a directed or bidirected graph naturally map to the SPQR tree of their underlying undirected graph. In (a) we have a directed graph with superbubbles (b,d) (violet) and (e,h) (green). (Note that also (a,i) is a superbubble, but since it is the whole graph, it will be handled separately.) In (b) we have a bidirected graph with the same underlying undirected graph as the graph in (a). We have that \{b+,d+\} (violet), \{d-,i+\} (yellow) are snarls, that are also ultrabubbles. The pair \{b+,i+\} is not a snarl because of minimality. The snarl \{e+,h+\} (green) is not an ultrabubble as it contains a cycloid (purple) in its interior (alternating signs at all vertices except e ). In (c) we show the SPQR tree of the underlying undirected graph of these graphs, where the different bubble subgraphs are shown with the same color as in the graphs in (a) and (b). Some snarls, such as the single-edge snarl \{h-,i-\} do not arise from a 2-separator, but are handled separately when traversing the SPQR tree (in this case, when processing the middle S-node). 3.2 Superbubbles Since (nearly all) superbubbles correspond to some 2 -separator of the graph, our main technique is to exploit the decomposition of the 2 -separators provided by the SPQR tree, encoded by its virtual edges (see Figure 3 ). For each 2 -separator, we need to decide whether the subgraph induced by the vertex set C that the virtual edge points to corresponds to a superbubble, but we also need the other direction of whether the subgraph induced by the complement of C is a superbubble. Most of our efforts in finding superbubbles and ultrabubbles is in computing the required properties in these “two sides” of the separations. (Exceptionally, P-nodes require special treatment since they encode many separations alone, but ultimately do not raise any issues due to their fixed topology.) To solve these problems, we start by observing that the property of the desired walks existing inside the superbubble is equivalently captured by the lack of internal sources and sinks supposing that we know the graph to be acyclic. If the induced subgraph corresponding to some virtual edge contains cycles, sources, or sinks, then so do all of its induced supergraphs. Therefore, we traverse the SPQR tree with depth-first search starting from an arbitrary root r , compute the information for the subgraphs, and finally combine the subresults to deduce the acyclicity and the existence of sources and sinks. For high-level visualization, see Figure 4 . To identify superbubbles from this information (and also to identify other bubbles), we then need to perform careful case analysis on how they can manifest in each type of a node of the SPQR tree. Figure 4 : Phase 1 of the superbubble-finding algorithm (bottom-up DFS traversal of the SPQR tree). In (a), the SPQR tree is shown with an R-node \mu having children \mu_{1},\mu_{2},\mu_{3} and parent \nu . The skeletons are depicted with dotted edges (virtual) and solid edges (real, maintaining the directions in the input directed graph). In this example, the goal is to determine whether s reaches t in \expansion(e_{\mu}) , knowing the reachabilities between the 2-separators \{s,a\} , \{a,b\} , and \{b,t\} in the children \mu_{1} , \mu_{2} , and \mu_{3} (in red), respectively. In (b), retrieving these information from the children, each expansion is collapsed into a directed edge in \dirskel(\mu) (red arrows). A traversal of this directed skeleton confirms that s reaches t (notice that the algorithm does not require an explicit traversal in order to determine this reachability relation, see Lemma 8 ). Figure 5 : Phase 2 of the superbubble finding algorithm (BFS from the root). The algorithm processes node \nu and determines for each neighbor \mu_{i} whether \expansion(e_{\nu}^{i}) is acyclic, for i\in\{1,\dots,k\} . The red arrows represent states already computed (due to Phase 1 and the BFS traversal order in Phase 2). The purple region shows \expansion(e_{\nu}^{1}) . To handle all these tree nodes/states in linear-time in the size of \skel(\nu) , the feedback-arcs of \dirskel(\nu) are computed. This procedure identifies the superbubbles for each 2 -separator in one direction—in the separated component without the vertices of r —but not in the other. For that direction, we instead need to know that if we were to remove the subgraph corresponding to the virtual edge, would the remaining subgraph be a superbubble. The main idea here is that if the subgraph corresponding to a virtual edge between u and v is acyclic and has no sources and sinks, then we can “collapse” it into a single arc whose direction is determined by whether all walks in the subgraph go from u to v or from v to u . If we then collapse all the virtual edges of the node, then identifying the remaining superbubbles reduces to finding the feedback arcs among the collapsed virtual edges, that is, arcs whose removal makes the graph acyclic. Such arcs are computable in linear time in the number of arcs [ 18 ] , and SPQR trees contain only linearly many virtual edges in the size of the input. The process is illustrated in Figure 5 . Consequently, we get a linear-time algorithm for identifying all superbubbles. Theorem 1 . The superbubbles of a directed graph G can be computed in time O(|V(G)|+|E(G)|) . 3.3 Snarls Because snarls only require separability and minimality, identifying them with the SPQR tree should intuitively be more straightforward than identifying ultrabubbles. On the other hand, the lack of structural requirements makes it possible for there to be quadratically many of them in the size of the input; this occurs for example in a clique of tips. To solve this issue, we provide a novel characterization of snarls and then provide a concise representation of all snarls based on that, whose size is only linear in the size of the input. We start by identifying a subset of cutvertices of the graph such that the extremities of a snarl cannot be in distinct connected components after splitting of any of them. These cutvertices have a property which we call sign-consistency : a sign-consistent vertex becomes a tip in each component that is created after being split (not necessarily with the same sign in each component). By splitting each of these vertices we obtain a set of disjoint graphs that we call sign-cut graphs , which preserve the set of all original snarls and where every snarl has its extremities in a single sign-cut graph. We then observe that the extremities of each snarl are either (i) a pair of tips or (ii) a pair of non-tips, within a (unique) sign-cut graph. For the snarls of type (i), we compile a list of tips for each sign-cut graph, enabling us to capture a quadratic number of snarls with linear-sized lists. Crucially, there are only linearly many snarls of type (ii), which we find by analyzing the nodes of the SPQR tree. Ultimately, we obtain the next result. Theorem 2 . Given a bidirected graph G , there exists a representation of the set of all snarls of G consisting of sets T_{1},T_{2},\dots,T_{k} and S_{1},S_{2},\dots,S_{\ell} , where 1. each T_{i} is a set of vertex-sides of G , and any pair of vertex-sides in T_{i} identifies a snarl of G ; 2. each S_{i} is a pair of vertex-sides \{u\alpha,v\beta\} identifying a snarl of G ; 3. \sum_{i=1}^{k}|T_{i}|=O(|V(G)|) and \sum_{i=1}^{\ell}|S_{i}|=O(|V(G)|) . Moreover, this representation can be computed in time O(|V(G)|+|E(G)|) . For a concrete example, cutvertex b is sign-consistent in Figure 1 (b). After splitting it, we would get a sign-cut graph with tips a , b , and c and another sign-cut graph with tips b and e . The remaining snarls \{d+,f-\} and \{d-,f+\} correspond to a pair of non-tip vertices d and f . 3.4 Ultrabubbles Ultrabubbles were introduced as a canonical generalization of superbubbles to bidirected graphs. Their similarities were exploited in 26 in order to get a linear-time algorithm for finding ultrabubbles. This algorithm works by converting the input bidirected graph into a directed graph such that an ultrabubble in the original instance corresponds to a ‘‘weak’’ 7 7 7 We do not need the exact definition of weak superbubble in this paper. The original definition can be found in [ 22 ] . superbubble in the transformed instance, and vice-versa. As a corollary, they showed that ultrabubbles are “directable”, i.e., they can be cast on a directed graph. The approach of 26 has the limitation of requiring the input graph to contain a tip or a cutvertex. Although ultrabubbles are originally defined in a way where their resemblance with superbubbles is not entirely clear, both these objects share the following key reachability property: every vertex in the superbubble/ultrabubble lies in some directed/bidirected path between the extremities of the bubble. In fact, many if not essentially all the structural results we present in detail for superbubbles can be adapted to ultrabubbles in a straightforward manner. As directed graphs are more common in the literature, we first present our SPQR tree approach to find superbubbles in linear time and then go on to show how to adapt this algorithm to find ultrabubbles also in linear time. To achieve this within our SPQR-tree-methodologies we must be able to perform the following two procedures in linear time: testing whether a bidirected graph has cycloids and finding its bidirected feedback edges , that is, edges whose deletion destroys all cycloids (i.e., the resulting bidirected graph is acyclic). We observe this to be impossible in general under the k - Clique Conjecture (see Conjecture 10 of 34 ), which asserts in particular that a triangle—a clique of 3 vertices—cannot be found in an undirected graph in time O(|V|^{\omega-\epsilon}) for the matrix multiplication exponent \omega and any \epsilon>0 . The result follows by a relatively simple reduction, where we essentially associate appropriate vertex-sides to each undirected edge of the graph such that any cycloid is an undirected triangle and vice versa; see Figure 6 for an example. Figure 6 : The reduction from finding triangles in tripartite graphs (left) to finding bidirected feedback edges, or finding cycloids, in bidirected graphs (right), where the vertices x , y , and z are omitted in the latter case. Roughly speaking, vertex-sides are associated to each undirected edge based on the tripartite sets of the endpoints of the edges such that triangles correspond to closed walks. If a triangle exists then there are no bidirected feedback edges because there are two disjoint closed walks (in violet). Theorem 3 . Let G be a bidirected graph. Under the k - Clique Conjecture , we cannot decide if a bidirected graph is acyclic (i.e. it has no cycloid) or it has at least one bidirected feedback edge, in time O(|V(G)|^{\omega-\epsilon}) for any \epsilon>0 . Fortunately, we are able to exploit the special structure of ultrabubbles to solve these problems in linear time. We observe the problems to be linear-time solvable in graphs without tips, which is a property of ultrabubbles. Our solution involves an ear-addition procedure exploiting the bidirected reachability properties of the graph being constructed. If the construction succeeds then the procedure outputs a strongly connected directed graph with the same set of cycles as the original bidirected graph, and so we can use the linear-time algorithm of 18 to find all feedback edges. If the procedure halts before having built the whole graph then we can correctly output that no feedback edge exists. Theorem 4 . Let G be a bidirected graph without tips. Then the set of feedback edges of G can be computed in time O(|V(G)|+|E(G)|) . Further, we can decide whether G has a cycloid in time O(|V(G)|+|E(G)|) . Theorem 5 . The ultrabubbles of a bidirected graph G can be computed in time O(|V(G)|+|E(G)|) . 4 Superbubbles In this section we develop a linear-time algorithm to find superbubbles in directed graphs. Basic notions Onodera et al. introduced in [ 44 ] the notion of superbubble and motivate it as being a natural generalization of bubbles - a structurally simple graph motif appearing in graphs built from biological data. A superbubble (s,t) is a minimal acyclic vertex-induced subgraph by the set of vertices reachable from s without going through t , which must coincide with the set of vertices that reach t without going through s . This property is called the matching property of superbubbles, so in particular every vertex in the superbubble lies in some s - t path (see [ 44 ] for the formal definition). In the same paper Onodera et al. showed that every vertex is the entry (and exit) of at most one superbubble. A useful relaxation of superbubbles is that of superbubbloids, introduced by 21 , 22 ; superbubbloids are superbubbles without the minimality constraint. Moreover, [ 21 , 22 ] defines (and proves equivalence with) these constructs in a way that is more suitable for our SPQR tree approach, as it exposes better the visual intuition that superbubbles are attached to the rest of the graph only by its defining vertices. Definition 1 (Superbubbloid [ 22 ] ) . Let G be a directed graph, X\subseteq V(G) , and s,t\in X . The pair (s,t) is a superbubbloid with superbubbloid graph G[X] if: 1. every u\in X is reachable from s , 2. t is reachable from every u\in X , 3. if u\in X and w\in V(G)\setminus X , then every w - u directed path contains s , 4. if u\in X and w\in V(G)\setminus X , then every u - w directed path contains t , 5. if uv is an edge in G[X] , then every v - u directed path in G contains both t and s , and 6. G does not contain the edge ts . Let (s,t) be a superbubbloid with graph B . Vertex s is the entry and vertex t is the exit of the superbubbloid. The interior of (s,t) is the set V(B)\setminus\{s,t\} ; notice that the interior of a superbubbloid does not contain sources or sinks. Since the pair (s,t) uniquely defines the superbubbloid graph B and the superbubbloid graph B uniquely defines the pair (s,t) , we refer to both the graph and the pair of vertices simply as “superbubbloid”. A superbubble (s,t) is a superbubbloid where no s^{\prime}\in V(B)\setminus\{s\} is such that (s^{\prime},t) is a superbubbloid. An edge st with N^{+}_{G}(s)=\{t\} , N^{-}_{G}(t)=\{s\} , and ts\notin E(G) is a trivial superbubble (in fact, the original notion of “bubbles” essentially coincides with that of trivial superbubbles). Next we give some results on the relation between cutvertices, superbubbloids, and superbubbles. Importantly, we show that cutvertices are not in the interior of any superbubble. Lemma 4 . Let G be a directed graph and let (s,t) be a superbubbloid of G with graph B . Then (s,t) is a superbubble if and only if no vertex in the interior of B is an s - t cutvertex in B . Proof. The statement holds if B is trivial, so suppose B has at least three vertices. (\Rightarrow) (Trivial.) (\Leftarrow) Suppose for a contradiction that B has a vertex v\neq s,t violating the minimality of (s,t) . Notice that B has an s - t directed path avoiding v for otherwise v is an s - t cutvertex. So s reaches t without v and so s is contained in the superbubbloid graph of (v,t) , and consequently v reaches s without t . But s reaches v without t because (s,t) is a superbubbloid, and thus B has a cycle, a contradiction. ∎ Corollary 1 . Superbubbles are biconnected. Proof. Suppose there is a vertex v in a superbubble (s,t) with graph B such that B-v is disconnected with components C^{\prime}_{1},\dots,C^{\prime}_{\ell} (\ell\geq 2) . Let C_{i}:=B[V(C^{\prime}_{i})+v] for each i\in\{1,\dots,\ell\} . Observe that there is exactly one component C_{i} where both s and t appear, since if v\neq s,t then v does not separate s and t because Lemma 4 gives us two internally vertex-disjoint s - t paths in B (and if v=s or v=t this follows trivially). Moreover, any component C_{j} but the one containing s and t contains at most one source or sink, which is v , since B has no sources or sinks besides s and t due to conditions 1 and 2 of superbubbles (see Definition 1 ). Therefore C_{j}\subseteq B has a cycle, a contradiction to the acyclicity of superbubbles. ∎ Lemma 5 (Superbubbles and cutvertices) . Let G be a directed graph and let (s,t) be a superbubble of G with graph B . Then no vertex in the interior of B is a cutvertex of G . Proof. We can assume that B contains at least three vertices. Suppose for a contradiction that the interior of B contains a cutvertex of G . There are two cases to analyze. No block contains both s and t : Since no block contains both s and t there is a vertex v whose removal disconnects s from t in G . Since (s,t) is a superbubble and every s - t path in U(G) contains v , every s - t directed path in G also contains v . Thus v is reachable from s without t and so v\in V(B) . Since B\subseteq G , vertex v is an s - t cutvertex in B , which is a contradiction by Lemma 4 . There is a block containing s and t : Let v be a cutvertex of G in the interior of B . Removing v from G results in a disconnected graph where at least one component does not contain both s and t since one block of G contains both s and t . Thus, let w be a vertex in such a component adjacent to v in G . Notice that regardless of whether vw\in E(G) or wv\in E(G) , we have w\in V(B) because v\in V(B) . So, in G , w is reachable from s without t and reaches t without s , but any two directed paths witnessing these reachabilities contain v , and so there is a cycle in B through v , a contradiction. ∎ By Lemma 5 a cutvertex of G can only be the entry or the exit of a superbubble. Therefore, superbubble graphs are confined to the blocks of G , and moreover there is a unique block that contains both the entrance and exit of of any given superbubble. Then the task of computing superbubbles in a directed graph G reduces to that of computing superbubbles in each block of G . Since block-cut trees can be built in linear time, if we can find superbubbles inside a block in linear time then we can find every superbubble of an arbitrary graph also in linear time. The next result explains why (interesting) superbubbles induce 2-separators of the underlying undirected graph. Theorem 6 (Superbubbles and split pairs) . Let G be a directed graph and let (s,t) be a superbubble of G with graph B . Let H_{1},\dots,H_{\ell} be the blocks of G (\ell\geq 1) . Then \{s,t\} is a split pair of some H_{i} or V(B)=V(H_{i}) . Proof. It follows from Lemma 5 that V(B) is contained in a block of G , say, without loss of generality, of H_{1} . Suppose that |V(B)|\geq 3 , V(B)\neq V(H_{1}) . Then it suffices to show that \{s,t\} disconnects H_{1} . Let u\in V(B)\setminus\{s,t\} and let v\in V(H_{1})\setminus V(B) . By (3) and (4) of Definition 1 , every u - v path in G contains t and every v - u path in G contains s . But then every u - v path in H_{1} contains s or t , and therefore \{s,t\} is a separation pair of H_{1} . ∎ The interesting case of Theorem 6 is when the vertices identifying a superbubble form a separation pair of a block, as the other two cases can be dealt with a linear-time preprocessing step (with a single graph traversal it is possible to decide if the whole block is a superbubble, and with a simple predicate it is possible to decide whether an edge is a trivial superbubble). By Lemma 1 we know that every separation pair of a graph is encoded as the endpoints of a virtual edge of some node of the SPQR tree, or as nonadjacent vertices in an S-node (but these cannot form superbubbles unless its superbubble graph is the whole block, as the next result shows; see Figure 7 ). Conversely, the endpoints of any virtual edge in a node of the SPQR tree forms a separation pair. Therefore, by correct examination of the virtual edges of the SPQR tree we can obtain the complete set of superbubbles of G (see Figure 3 for an example). Proposition 1 . Let G be a directed graph, H a maximal 2-connected subgraph of G , T the SPQR tree of H , and \mu\in V(T) an S-node with u,v\in V(\skel(\mu)) . If \{u,v\}\notin E(\skel(\mu)) then (u,v) and (v,u) are not superbubbles, unless the corresponding graph is H . Proof. Suppose for a contradiction and without loss of generality that (u,v) is a superbubble with graph B . Assume B\neq H . Let e_{1},\dots,e_{\ell} and f_{1},\dots,f_{k} denote the sequence of edges in \skel(\mu) in the two u - v paths of this S-node ( \ell,k\geq 2 because \{u,v\}\notin E(\skel(\mu)) ). Since superbubbles are contained in blocks and u,v\in V(H) we have B\subseteq H and, due to the structure of the S-nodes, it is not hard to see that any u - v directed path contains the vertices which are endpoints of the edges e_{i} or of the edges f_{j} , for i\in\{1,\dots,\ell\} and j\in\{1,\dots,k\} . Thus the set of vertices of B contains at least the endpoints of the edges e_{i} or those of f_{j} (possibly of both). Suppose without loss of generality that B contains those of the edges e_{i} . We claim that V(\bigcup_{i=1}^{\ell}\expansion(e_{i}))\subseteq V(B) . Suppose otherwise and let w\in V(\bigcup_{i=1}^{\ell}\expansion(e_{i}))\setminus V(B) and let e_{i}=\{x,y\} be the edge such that w\in V(\expansion(e_{i})) , and suppose that x denotes the vertex closest to u in \skel(\mu) (possibly y=v ). By Lemma 3 \expansion(e_{i}) has an x - w path p avoiding y , which starts in a vertex in B and ends in a vertex not in B . Let x^{\prime} denote the last vertex in p that is in B (possibly x^{\prime}=x ). So x^{\prime} has a successor y^{\prime} in p which is not contained in B (notice that y^{\prime}\neq v since p avoids y ). Thus \expansion(e_{i}) has a directed edge x^{\prime}y^{\prime} or y^{\prime}x^{\prime} . Since x^{\prime}\in V(B) , B has a u - x^{\prime} path avoiding v and an x^{\prime} - t path avoiding u . Therefore, if x^{\prime}y^{\prime}\in E(\expansion(e_{i})) then \expansion(e_{i}) has a u - y^{\prime} path avoiding v , thus y^{\prime}\in V(B) , a contradiction, and similarly a contradiction is obtained if y^{\prime}x^{\prime}\in E(\expansion(e_{i})) . Hence V(\bigcup_{i=1}^{\ell}\expansion(e_{i}))\subseteq V(B) . If B has a vertex not in V(\bigcup_{i=1}^{\ell}\expansion(e_{i})) then such a vertex can be chosen so that it is an endpoint of an edge f_{j} . Thus the same argument as above can be made to conclude that V(\bigcup_{i=1}^{k}\expansion(f_{i}))\subseteq V(B) . But notice that either V(\bigcup_{i=1}^{\ell}\expansion(e_{i}))\subseteq V(B) or V(\bigcup_{i=1}^{k}\expansion(f_{i}))\subseteq V(B) hold, for if both hold then V(H)\subseteq V(B) and since superbubbles are contained in blocks we get V(B)=V(H) and hence B=H , a contradiction. So V(B)\subseteq V(\bigcup_{i=1}^{\ell}\expansion(e_{i})) without loss of generality and thus V(B)=V(\bigcup_{i=1}^{\ell}\expansion(e_{i})) . Due to the structure of S-nodes and the fact that \ell\geq 2 we can conclude that B has a u - v cutvertex, a contradiction to Lemma 4 . ∎ Figure 7 : Why nonadjacent vertices in an S-node do not form superbubbles ( Proposition 1 ). (a) S-node skeleton of a block H with u and v nonadjacent. There are two u - v paths in the cycle. (b) The superbubble graph B must contain one entire side. (c) Since this side has at least two edges, there is a u - v cutvertex in B (red), a contradiction. If both sides lie in B then B=H , a contradiction. The next result is merely technical and will be used later on to show correctness of the superbubble finding algorithm. Lemma 6 (Unique orientation at poles of acyclic components) . Let G be a directed graph and let C\subseteq V(G) , |C|\geq 2 , be such that G[C] is connected and G[C] is acyclic. Moreover, let s,t\in C be such that for all other vertices v\in C\setminus\{s,t\} there is no edge in G between v and some v^{\prime}\in V(G)\setminus C . If no vertex in C\setminus\{s,t\} is a source or sink of G , then one vertex among \{s,t\} is the unique source of G[C] and the other vertex is the unique sink of G[C] . Proof. Notice that since G[C] is acyclic, it has at least one source (relative to G[C] ), say v . If v\in C\setminus\{s,t\} , then it is also a source of G , since by the hypothesis there is no edge in G between v and some v^{\prime}\in V(G)\setminus C . This contradicts the assumption that no vertex in C\setminus\{s,t\} is a source of G . Therefore, any source of G[C] belongs to \{s,t\} . Symmetrically, we have that any sink of G[C] belongs to \{s,t\} . Observe that neither s nor t can be both a source and a sink of G[C] , because otherwise it would be an isolated vertex with no edges in G[C] , which contradicts the assumption that G[C] is connected. Therefore, since G[C] has at least one source and at least one sink (being acyclic), one vertex among \{s,t\} is the unique source of G[C] and the other vertex is the unique sink in G[C] . ∎ 4.1 Setup Here, we focus on superbubbles that induce a separation pair of a block H . The next result will be applied frequently later on. Lemma 7 . Let G be a directed graph, let \{s,t\} be a separation pair of a maximal 2-connected subgraph of G , and let K be the union of a nonempty subset of the split components of \{s,t\} . If there are no extremities of G in V(K)\setminus\{s,t\} , K is acyclic, N^{+}_{G}(s)\subseteq V(K) , N^{-}_{G}(t)\subseteq V(K) , and ts\notin E(G) , then (s,t) is a superbubbloid of G with graph K . Proof. Let K_{1},\dots,K_{k} denote the set of split components of \{s,t\} whose union is K (k\geq 1) . We show that K fulfills each condition of Definition 1 . 1. Let u\in V(K_{i}) and let p=v_{1},\dots,v_{\ell} be a maximal directed path in K_{i} containing u (\ell\geq 1) . Suppose that v_{1} has in-neighbors in K_{i} . If v_{1} has an in-neighbor in p then this edge is in K_{i} by maximality of split component, and so there is a cycle in K_{i}\subseteq K , a contradiction. If v_{1} has an in-neighbor in K_{i} that is not in p then p can be prolonged, contradicting its maximality. Therefore v_{1} does not have in-neighbors in K_{i} and thus v_{1}=s since s is the unique source of K_{i} . Analogously, we have v_{\ell}=t . As \bigcup_{i=1}^{k}V(K_{i})=V(K) it follows that every vertex in K lies in some s - t directed path, and thus it is reachable from s and reaches t . 2. (Proved in the previous item.) 3. Let u\in V(K) and w\in V(G)\setminus V(K) . If u=s we are done. Otherwise, suppose for a contradiction that G has a w - u directed path avoiding s . Then, since K consists of the union of split components of \{s,t\} , this path contains t , a contradiction to the fact that every in-neighbor of t is contained in K . Therefore every w - u path in G contains s . 4. (Analogous to the previous item.) 5. Let uv\in E(K) and let K_{i} denote the split component that contains the edge uv . Suppose for a contradiction that G has a v - u path avoiding, say, s . Then this path is contained in K_{i} because K_{i} is a split component (if the path leaves K_{i} it must do it through t , but then it cannot reenter since paths do not repeat vertices). This path together with the edge uv forms a cycle in K_{i} , a contradiction. Therefore every v - u path in G contains both t and s . 6. Direct by assumption. ∎ We assume in what follows that the SPQR tree of H does not consist of a single node, since otherwise any superbubble is either H or a single edge by Theorem 6 and Proposition 1 . Let T be the SPQR tree of H . Let \{\nu,\mu\}\in E(T) such that \nu is the parent of \mu , and let e_{\nu} be the virtual edge in \skel(\mu) pertaining to \nu and define e_{\mu} analogously; let \{s,t\} denote the endpoints of these virtual edges. In the edge \{\nu,\mu\} we store two pieces of information: the state corresponding to the subgraph \expansion(e_{\mu}) as \mathsf{State_{\nu,\mu}[\cdot]} and the state corresponding to \expansion(e_{\nu}) as \mathsf{State_{\mu,\nu}[\cdot]} . We say that \mathsf{State_{\nu,\mu}[\cdot]} leaves \nu and that it enters \mu . (This can be seen as a directed edge in the tree pointing from \nu to \mu .) Let X=\expansion(e_{\mu}) . Notice that any state uniquely identifies a virtual edge, in this case e_{\mu} . In \mathsf{State_{\nu,\mu}} we store the following information: • \mathsf{State_{\nu,\mu}[NoInnerExtr]}:=\mathsf{True} iff no vertex in V(X)\setminus\{s,t\} is an extremity of G . • \mathsf{State_{\nu,\mu}[Acyclic]}:=\begin{cases}\mathsf{Null},&\text{if $\mathsf{State_{\nu,\mu}[NoInnerExtr]}$ is false,}\\ \mathsf{True},&\text{otherwise, if $X$ is acyclic,}\\ \mathsf{False},&\text{otherwise.}\end{cases} • \mathsf{State_{\nu,\mu}[Reaches_{st}]}:=\begin{cases}\mathsf{Null},&\text{if $\mathsf{State_{\nu,\mu}[Acyclic]}$ is $\mathsf{False}$ or $\mathsf{Null}$,}\\ \mathsf{True},&\text{otherwise, if $s$ reaches $t$ in $X$,}\\ \mathsf{False},&\text{otherwise.}\end{cases} • \mathsf{State_{\nu,\mu}[Reaches_{ts}]}:=\begin{cases}\mathsf{Null},&\text{if $\mathsf{State_{\nu,\mu}[Acyclic]}$ is $\mathsf{False}$ or $\mathsf{Null}$,}\\ \mathsf{True},&\text{otherwise, if $t$ reaches $s$ in $X$,}\\ \mathsf{False},&\text{otherwise.}\end{cases} We define \mathsf{State_{\mu,\nu}[\cdot]} in the same way, but where X is the graph \expansion(e_{\nu}) (i.e., this state now “points” from \mu to \nu ). With this information we can “almost” decide if a separation pair \{s,t\} identifies a superbubble (s,t) , since if \mathsf{State_{\nu,\mu}[NoInnerExtr]} and \mathsf{State_{\nu,\mu}[Acyclic]} are \mathsf{True} , N^{+}_{G}(s),N^{-}_{G}(t)\subseteq V(\expansion(e_{\mu})) , and ts\notin E(G) , then (s,t) is a superbubbloid with graph \expansion(e_{\mu}) by Lemma 7 . This fact also hints that most of our effort is in the computation of \mathsf{State_{\nu,\mu}[\cdot]} for all edges \{\nu,\mu\} of T , as the other conditions are easy to check. The algorithm consists of three phases. • Phase 1. Process the edges \{\nu,\mu\} of T (with \nu the parent of \mu ) with a DFS traversal starting in the root, and compute all \mathsf{State_{\nu,\mu}[\cdot]} . • Phase 2. Process the nodes \nu of T with a BFS traversal starting in the root. For every child \mu of \nu , compute all \mathsf{State_{\mu,\nu}[\cdot]} . • Phase 3. Examine the separation pairs \{s,t\} of H in T and use the information computed in the previous phases to decide whether (s,t) or (t,s) are superbubbles. 4.2 Algorithm - Phase 1 Phase 1 is a dynamic program over the edges of T . Let \nu be the parent of \mu in T and let \{s,t\} denote the endpoints of e_{\nu}\in\skel(\mu) and of e_{\mu}\in\skel(\nu) . If \mu has no children then the edges of its skeleton but e_{\nu} are all real edges, and hence the problem of updating \mathsf{State_{\nu,\mu}[\cdot]} is trivial: with one DFS on \dirskel(\mu)-st-ts we can decide \mathsf{State_{\nu,\mu}[NoInnerExtr]} , \mathsf{State_{\nu,\mu}[Acyclic]} , \mathsf{State_{\nu,\mu}[Reaches_{st}]} , and \mathsf{State_{\nu,\mu}[Reaches_{ts}]} . Otherwise \mu has at least one virtual edge besides e_{\nu} . Let us denote the children of \mu by \mu_{1},\dots,\mu_{k} (k\geq 1) and denote the endpoints of the corresponding virtual edges e_{i} in \skel(\mu) as \{s_{i},t_{i}\} for all i\in\{1,\dots,k\} . Assume recursively that \mathsf{State_{\mu,\mu_{i}}[\cdot]} is solved and let X=\expansion(e_{\mu}) , X_{i}=\expansion(e_{i}) for all i\in\{1,\dots,k\} , and let K=\dirskel(\mu)-st-ts . We now describe how to compute the states \mathsf{State_{\nu,\mu}[\cdot]} . \mathsf{State_{\nu,\mu}[NoInnerExtr]} : We set \mathsf{State_{\nu,\mu}[NoInnerExtr]} to \mathsf{True} if and only if no vertex in V(K)\setminus\{s,t\} is an extremity and \mathsf{State_{\mu,\mu_{i}}[NoInnerExtr]} is \mathsf{True} for all i\in\{1,\dots,k\} . To see this is correct we prove both implications. ( \Rightarrow ) Suppose no vertex in V(X)\setminus\{s,t\} is an extremity. Then indeed, no vertex in V(K)\setminus\{s,t\} is an extremity because V(K)\subseteq V(X) . Moreover, \mathsf{State_{\mu,\mu_{i}}[NoInnerExtr]} must be \mathsf{True} for all i\in\{1,\dots,k\} , for otherwise an extremity x in X_{i} is different from both s_{i} and t_{i} and thus also different from s and t , as it does not belong to \skel(\mu) since \{s_{i},t_{i}\} is a separation pair. (\Leftarrow) Suppose no vertex in V(K)\setminus\{s,t\} is an extremity and \mathsf{State_{\mu,\mu_{i}}[NoInnerExtr]} is \mathsf{True} for all i\in\{1,\dots,k\} . For a contradiction, assume that some x\in V(X)\setminus\{s,t\} is an extremity. By the initial assumption, we have that x cannot belong to V(K) . Thus, x is also different from s_{i},t_{i} , for all i\in\{1,\dots,k\} . Since x\in V(X)\setminus\{s,t\} , x is a vertex of X_{i} for some i\in\{1,\dots,k\} . Therefore, it is an extremity for it, since it is different from s_{i} and t_{i} . This contradicts the initial assumption that \mathsf{State_{\mu,\mu_{i}}[NoInnerExtr]} is \mathsf{True} . \mathsf{State_{\nu,\mu}[Acyclic]} : If \mathsf{State_{\nu,\mu}[NoInnerExtr]} is \mathsf{False} then we set \mathsf{State_{\nu,\mu}[Acyclic]} to \mathsf{Null} , which is correct by definition. Thus, in the following we assume that \mathsf{State_{\nu,\mu}[NoInnerExtr]} is \mathsf{True} . If for some i\in\{1,\dots,k\} \mathsf{State_{\mu,\mu_{i}}[Acyclic]} is \mathsf{Null} , then by definition \mathsf{State_{\mu,\mu_{i}}[NoInnerExtr]} is \mathsf{False} . Let thus x be an extremity in V(X_{i})\setminus\{s_{i},t_{i}\} . Since \{s_{i},t_{i}\} is a separation pair, we have that x\notin\{s,t\} . Thus, x\in V(X)\setminus\{s,t\} , which contradicts the fact \mathsf{State_{\nu,\mu}[NoInnerExtr]} is \mathsf{True} . Thus \mathsf{State_{\mu,\mu_{i}}[Acyclic]} is \mathsf{True} or \mathsf{False} for each i\in\{1,\dots,k\} . If for some i\in\{1,\dots,k\} \mathsf{State_{\mu,\mu_{i}}[Acyclic]} is \mathsf{False} , then X_{i} has a cycle, which implies that also X contains a cycle because X_{i} is a subgraph of X . Since \mathsf{State_{\nu,\mu}[NoInnerExtr]} is \mathsf{True} , then by definition we can set \mathsf{State_{\nu,\mu}[Acyclic]} to \mathsf{False} . Finally, we are in the case where for every i\in\{1,\dots,k\} , \mathsf{State_{\mu,\mu_{i}}[Acyclic]} is \mathsf{True} , and therefore \mathsf{State_{\mu,\mu_{i}}[Reaches_{st}]} and \mathsf{State_{\mu,\mu_{i}}[Reaches_{ts}]} are \mathsf{True} or \mathsf{False} . In other words, each X_{i} is acyclic, and, importantly, the reachability in X_{i} between the endpoints of each virtual edge e_{i} are known. Then K can be built explicitly and we can set \mathsf{State_{\nu,\mu}[Acyclic]} to \mathsf{True} if K is acyclic and to \mathsf{False} otherwise. To see this is correct, notice that any cycle C in X can be mapped to a cycle in K : whenever C uses edges of some X_{i} , it passes through s_{i} (or t_{i} ), and since X_{i} is acyclic, it must return to t_{i} (or s_{i} ). This path of C in X_{i} between s_{i} and t_{i} (or between t_{i} and s_{i} ) can be mapped to the edge of K that was introduced from s_{i} to t_{i} , if \mathsf{State_{\mu,\mu_{i}}[Reaches_{st}]} is \mathsf{True} (or from t_{i} to s_{i} , if \mathsf{State_{\mu,\mu_{i}}[Reaches_{ts}]} is \mathsf{True} ). Viceversa, every cycle C in K can be symmetrically mapped to a cycle in X such that whenever C uses some edge s_{i}t_{i} (or t_{i}s_{i} ) in K , we expand this edge into a path from s_{i} to t_{i} (or from t_{i} to s_{i} ) in X_{i} . \mathsf{State_{\nu,\mu}[Reaches_{st}]} , \mathsf{State_{\nu,\mu}[Reaches_{ts}]} : At this point we have \mathsf{State_{\nu,\mu}[Acyclic]} computed. If it is \mathsf{False} or \mathsf{Null} we set \mathsf{State_{\nu,\mu}[Reaches_{st}]} and \mathsf{State_{\nu,\mu}[Reaches_{ts}]} to \mathsf{Null} , which is correct by definition. Otherwise X is acyclic, V(X)\setminus\{s,t\} has no cutvertex, no sink and no source of G , and there is no edge between a vertex not in V(X) and a vertex in V(X)\setminus\{s,t\} since \{s,t\} is a separation pair; moreover X is clearly connected. We can thus apply Lemma 6 to conclude that one vertex between s and t is a source of X and the other is a sink. In the former case we can set \mathsf{State_{\nu,\mu}[Reaches_{st}]} to \mathsf{True} and \mathsf{State_{\nu,\mu}[Reaches_{ts}]} to \mathsf{False} , and in the latter case we can set \mathsf{State_{\nu,\mu}[Reaches_{ts}]} to \mathsf{True} and \mathsf{State_{\nu,\mu}[Reaches_{st}]} to \mathsf{False} . Let \mu be a node of T and let \nu be its parent. Since T is a tree, each of its edges is processed exactly once during the DFS, thus every state of the form \mathsf{State_{\nu,\mu}[\cdot]} is updated during this phase. Moreover, since every node \mu has a unique parent in T and \dirskel(\mu) is built only when the edge \{\nu,\mu\} is processed, each directed skeleton \dirskel(\mu) is built only once during the algorithm. Since the computational work per edge \{\nu,\mu\} is linear in the size of \dirskel(\mu) and the total size of all skeletons is linear in the size of the current block H (recall Lemma 2 ), Phase 1 runs in time O(|V(H)|+|E(H)|) . Input: Directed graph G , SPQR tree T having at least two nodes 1 Function ProcessEdge( \nu,\mu ) : 2 // \nu is the parent of \mu for \mu_{i}\in\mathsf{children}_{T}(\mu) do 3 ProcessEdge( \mu,\mu_{i} ) ; 4 if \nu=\text{null} then 5 return ; 6 \{s,t\}\leftarrow e_{\mu} (where e_{\mu}\in\skel(\nu) ); 7 noExtr \leftarrow\text{false} iff V(\skel(\mu))\setminus\{s,t\} has an extremity of G ; 8 9 Let e_{1},\dots,e_{k} denote the virtual edges of \mu with pertaining nodes \mu_{1},\dots,\mu_{k} (k\geq 0) ; 10 ThereIsNoExtremityBelow \leftarrow\bigwedge_{i=1}^{k}\mathsf{State_{\mu,\mu_{i}}[NoInnerExtr]} ; 11 ThereIsNoCycleBelow \leftarrow\bigwedge_{i=1}^{k}\mathsf{State_{\mu,\mu_{i}}[Acyclic]} ; 12 \mathsf{State_{\nu,\mu}[NoInnerExtr]}\leftarrow noExtr \land ThereIsNoExtremityBelow ; 13 14 if \mathsf{State_{\nu,\mu}[NoInnerExtr]} is \mathsf{False} then 15 \mathsf{State_{\nu,\mu}[Acyclic]}\leftarrow\mathsf{Null} ; 16 else 17 if \neg ThereIsNoCycleBelow then 18 \mathsf{State_{\nu,\mu}[Acyclic]}\leftarrow\mathsf{False} ; 19 else 20 // We are in conditions to build \dirskel(\mu)-st-ts K\leftarrow\dirskel(\mu)-st-ts ; 21 \mathsf{State_{\nu,\mu}[Acyclic]}\leftarrow\mathsf{True} iff K is acyclic; 22 // Run DFS or BFS on K 23 if \mathsf{State_{\nu,\mu}[Acyclic]} is \mathsf{True} then 24 if N^{+}_{K}(s)\cap V(K)\neq\emptyset then 25 // See Lemma 6 \mathsf{State_{\nu,\mu}[Reaches_{st}]}\leftarrow\mathsf{True} ; \mathsf{State_{\nu,\mu}[Reaches_{ts}]}\leftarrow\mathsf{False} ; 26 else 27 \mathsf{State_{\nu,\mu}[Reaches_{st}]}\leftarrow\mathsf{False} ; \mathsf{State_{\nu,\mu}[Reaches_{ts}]}\leftarrow\mathsf{True} ; 28 else 29 \mathsf{State_{\nu,\mu}[Reaches_{st}]}\leftarrow\mathsf{Null} ; \mathsf{State_{\nu,\mu}[Reaches_{ts}]}\leftarrow\mathsf{Null} ; 30 31 \rho\leftarrow the root of T ; 32 ProcessEdge( \text{null},\rho ) ; 33 34 Algorithm 1 Superbubble finding – Phase 1 4.3 Algorithm - Phase 2 In Phase 2 we compute the states \mathsf{State_{\mu,\nu}[\cdot]} with \nu the parent of \mu by processing the nodes of T via Breadth-First Search, i.e., we compute the states “pointing” towards the root. Notice that the dependencies between states behave differently from Phase 1. Now the relevant states for \mathsf{State_{\mu,\nu}[\cdot]} are those leaving \nu to its children except \mu , and the state leaving \nu to its parent whenever \nu is different from the root of T ; the former states are known from Phase 1 and the latter state is known due to the breadth-first traversal order. We remark that following the same strategy of computation as in Phase 1 may cause the algorithm to have a worst-case quadratic running time. For example, if T consists only of node \rho with children \mu_{1},\dots,\mu_{k} , then in order to update \mathsf{State_{\mu_{i},\nu}[Acyclic]} we would have to build \dirskel(\nu)-s_{i}t_{i}-t_{i}s_{i} for each i=1,\dots,k , which would have a quadratic running time in the size of the graph whenever, e.g., |V(\skel(\nu))|\geq|V(G)|/2 . To overcome this issue we examine the states \mathsf{State_{\mu_{i},\nu}[Acyclic]} for i=1,\dots,k all “at once”. Let \nu be a node of T . Let \mu_{1},\dots,\mu_{k} denote the children of \nu and denote the endpoints of the corresponding virtual edges in \skel(\nu) as e_{i}=\{s_{i},t_{i}\} for i\in\{1,\dots,k\} (k\geq 1) . To distinguish the reference edges e_{\nu} belonging to each node \mu_{i} , we write e_{\nu}^{i} for the edge e_{\nu} in node \mu_{i} . Assume from the breadth-first traversal order that the states leaving \nu to its parent are known and, for convenience, denote by e_{0}=\{s_{0},t_{0}\} the reference edge of \nu and by \mu_{0} the parent of \nu , so the neighbours of \nu in T are the nodes \mu_{0},\mu_{1}\dots,\mu_{k} (if \nu is the root of T then \mu_{0} and e_{0} can be ignored during the following discussion). Let X_{i}=\expansion(e_{\nu}^{i}) , K=\dirskel(\nu) , and K_{i}=K-s_{i}t_{i}-t_{i}s_{i} for every i\in\{1,\dots,k\} . First we compute \mathsf{State_{\mu_{i},\nu}[NoInnerExtr]} for each i\in\{1,\dots,k\} similarly to Phase 1. \mathsf{State_{\mu_{i},\nu}[NoInnerExtr]} : We set \mathsf{State_{\mu_{i},\nu}[NoInnerExtr]} to \mathsf{True} if and only if no vertex in V(K_{i})\setminus\{s_{i},t_{i}\} is an extremity and \mathsf{State_{\nu,\mu_{j}}[NoInnerExtr]} is \mathsf{True} for every j\in\{0,\dots,k\}\setminus\{i\} . To see this is correct we prove both implications. ( \Rightarrow ) Suppose no vertex in V(X_{i})\setminus\{s_{i},t_{i}\} is an extremity. Then indeed, no vertex in V(K_{i})\setminus\{s_{i},t_{i}\} is an extremity. Moreover, \mathsf{State_{\nu,\mu_{j}}[NoInnerExtr]} must be \mathsf{True} for each j\in\{0,\dots,k\} distinct from i , for otherwise an extremity in \expansion(e_{j}) is different from both s_{j} and t_{j} and thus also different from s_{i} and t_{i} , as it does not belong to \skel(\nu) since \{s_{j},t_{j}\} is a separation pair. (\Leftarrow) Suppose no vertex in V(K_{i})\setminus\{s_{i},t_{i}\} is an extremity and that \mathsf{State_{\nu,\mu_{j}}[NoInnerExtr]} is \mathsf{True} for all j\in\{0,\dots,k\}\setminus\{i\} . For a contradiction, assume that a vertex x\in V(X_{i})\setminus\{s_{i},t_{i}\} is an extremity. By the initial assumption, we have that x cannot belong to V(K_{i}) . Thus, x is also different from s_{j},t_{j} for each j\in\{0,\dots,k\}\setminus\{i\} , and so x is an extremity in \expansion(e_{j}) for some j\in\{0,\dots,k\}\setminus\{i\} . Therefore it is an extremity for it, since it is different from s_{j} and t_{j} , contradicting the assumption that \mathsf{State_{\nu,\mu_{j}}[NoInnerExtr]} is \mathsf{True} . Then we compute the states \mathsf{State_{\mu_{i},\nu}[Acyclic]} for all i\in\{1,\dots,k\} . Notice that at this point the states \mathsf{State_{\nu,\mu_{i}}[Reaches_{st}]} and \mathsf{State_{\nu,\mu_{i}}[Reaches_{ts}]} are known for all i\in\{0,\dots,k\} . We proceed by cases on the values of these states. • If there is an i\in\{0,\dots,k\} such that \mathsf{State_{\nu,\mu_{i}}[Reaches_{st}]} or \mathsf{State_{\nu,\mu_{i}}[Reaches_{ts}]} is \mathsf{Null} , then by definition \mathsf{State_{\nu,\mu_{i}}[Acyclic]} is \mathsf{Null} or \mathsf{False} . Then we proceed by cases. – If \mathsf{State_{\nu,\mu_{i}}[Acyclic]} is \mathsf{Null} then \mathsf{State_{\nu,\mu_{i}}[NoInnerExtr]} is \mathsf{False} by definition, and so there is an extremity x\in V(\expansion(e_{i}))\setminus\{s_{i},t_{i}\} . So for every j\in\{1,\dots,k\} distinct from i , vertex x is an extremity also for X_{j} : x\in V(X_{j}) because \expansion(e_{i}) is a subgraph of X_{j} and x is different from s_{j},t_{j} since x is different from s_{i},t_{i} and \{s_{i},t_{i}\} is a separation pair; thus each state \mathsf{State_{\mu_{j},\nu}[Acyclic]} is \mathsf{Null} . For the remaining state \mathsf{State_{\mu_{i},\nu}[Acyclic]} we proceed by cases. First, if \mathsf{State_{\mu_{i},\nu}[NoInnerExtr]} is \mathsf{False} then \mathsf{State_{\mu_{i},\nu}[Acyclic]} is \mathsf{Null} . We can thus assume that \mathsf{State_{\mu_{i},\nu}[NoInnerExtr]} is \mathsf{True} , which implies that \mathsf{State_{\nu,\mu_{j}}[Acyclic]} is \mathsf{True} or \mathsf{False} for each j\in\{0,\dots,k\} distinct from i . If some \mathsf{State_{\nu,\mu_{j}}[Acyclic]} is \mathsf{False} then \expansion(e_{j}) has a cycle, and hence so does X_{i} as it is a supergraph of \expansion(e_{j}) ; therefore \mathsf{State_{\mu_{i},\nu}[Acyclic]} is \mathsf{False} . Otherwise every \mathsf{State_{\nu,\mu_{j}}[Acyclic]} is \mathsf{True} and thus we are in conditions to build K_{i} since the states \mathsf{State_{\nu,\mu_{j}}[Reaches_{st}]} and \mathsf{State_{\nu,\mu_{j}}[Reaches_{ts}]} are not \mathsf{Null} by definition. Then \mathsf{State_{\mu_{i},\nu}[Acyclic]} is \mathsf{False} if and only if K_{i} has a cycle because any cycle in X_{i} can be mapped to a cycle in K_{i} (similarly to the acyclicity update rule discussed in Phase 1). – Otherwise \mathsf{State_{\nu,\mu_{i}}[Acyclic]} is \mathsf{False} . So \expansion(e_{i}) contains a cycle C . Then for every j\in\{1,\dots,k\} with j\neq i , \mathsf{State_{\mu_{j},\nu}[Acyclic]} is \mathsf{False} since C\subseteq\expansion(e_{i})\subseteq X_{j} . For the remaining state \mathsf{State_{\mu_{i},\nu}[Acyclic]} we proceed identically as in the case above. • Otherwise \mathsf{State_{\nu,\mu_{i}}[Reaches_{st}]} and \mathsf{State_{\nu,\mu_{i}}[Reaches_{ts}]} are either \mathsf{True} or \mathsf{False} for all i\in\{0,\dots,k\} . Therefore we are in conditions to build K . Moreover, the fact that the reachability states are all either \mathsf{True} or \mathsf{False} implies, by definition, that \mathsf{State_{\nu,\mu_{i}}[Acyclic]} is \mathsf{True} for all i\in\{0,\dots,k\} ; in particular, there is no cycle in K of the form s_{i}t_{i}s_{i} . So \mathsf{State_{\mu_{i},\nu}[Acyclic]} is \mathsf{True} if and only if K_{i} is acyclic (the correctness of this argument was established in Phase 1), and hence it is enough to examine the acyclicity of K_{i} in order to determine \mathsf{State_{\mu_{i},\nu}[Acyclic]} , for every i\in\{1,\dots,k\} . However, we do not test the acyclicity of each K_{i} individually. First, notice that if K is acyclic then so is K_{i} because K_{i} is a subgraph of K , in which case \mathsf{State_{\mu_{i},\nu}[Acyclic]} is \mathsf{True} for all i\in\{1,\dots,k\} . Otherwise K has a cycle. Let i\in\{1,\dots,k\} . Suppose that an edge e_{i}\in E(K) intersects every cycle of K . Since K_{i}=K-e_{i} it follows that K_{i} is acyclic, and therefore \mathsf{State_{\mu_{i},\nu}[Acyclic]} is \mathsf{True} . Conversely, if e_{i} does not intersect every cycle of K then K_{i} has a cycle, and therefore \mathsf{State_{\mu_{i},\nu}[Acyclic]} is \mathsf{False} . So in order to keep the algorithm linear-time, it suffices to identify the edges that intersect every cycle of the directed skeleton in time proportional to its size. This is essentially the feedback arc set problem for the restricted case where every feedback set contains just one arc 8 8 8 In its generality, the feedback arc set problem is an NP-hard problem which asks if a directed graph G has a subset of at most k edges intersecting every cycle of G . Here, we are interested in enumerating all feedback-arcs. (“arc” and “edge” mean the same thing). Our subroutine to find feedback-arcs works as follows. We start by testing if the graph is acyclic. If it is we are done. Otherwise we compute the strongly connected components (SCCs) of G . If there are multiple non-trivial SCCs then there are two disjoint cycles and no solution exists. Thus, the last case is when there is a single non-trivial SCC, where we then have to find feedback-arcs. For that, we use the linear-time algorithm of Garey and Tarjan [ 18 ] for finding feedback vertices, and use a standard linear-time reduction from the feedback problem on arcs to the feedback problem on vertices described in, e.g., Even et al. [ 14 ] ). We briefly describe how the reduction works. Subdivide each arc uv of G into two arcs uw and wv , thus obtaining a graph G^{\prime} with |V(G)|+|E(G)| vertices and 2|E(G)| edges. If an arc uv is a feedback arc of G then w is a feedback vertex of G^{\prime} (deleting w from G^{\prime} corresponds to deleting the arcs uw and wv in G ), and the converse also holds. Notice, however, that G^{\prime} has feedback vertices that do not correspond to arcs of G , but those can be safely ignored. The states \mathsf{State_{\mu_{i},\mu}[Reaches_{st}]},\mathsf{State_{\mu_{i},\mu}[Reaches_{ts}]} get updated for i\in\{1,\dots,k\} as in Phase 1. \mathsf{State_{\mu_{i},\nu}[Reaches_{st}]} , \mathsf{State_{\mu_{i},\nu}[Reaches_{ts}]} : At this point \mathsf{State_{\mu_{i},\nu}[Acyclic]} is known. If \mathsf{State_{\mu_{i},\nu}[Acyclic]} is \mathsf{False} or \mathsf{Null} then \mathsf{State_{\mu_{i},\nu}[Reaches_{st}]} and \mathsf{State_{\mu_{i},\nu}[Reaches_{ts}]} are \mathsf{Null} by definition. Otherwise \mathsf{State_{\mu_{i},\nu}[Acyclic]} is \mathsf{True} , and thus so is \mathsf{State_{\mu_{i},\nu}[NoInnerExtr]} by definition. Therefore, X_{i} is acyclic, V(X_{i})\setminus\{s_{i},t_{i}\} has no cutvertex, no sink and no source of G , and there is no edge between a vertex not in V(X_{i}) and a vertex in V(X_{i})\setminus\{s_{i},t_{i}\} since \{s_{i},t_{i}\} is a separation pair; moreover X_{i} is clearly connected. We can thus apply Lemma 6 to conclude that one vertex between s_{i} and t_{i} is a source of X_{i} and the other is a sink. In the former case we can set \mathsf{State_{\mu_{i},\nu}[Reaches_{st}]} to \mathsf{True} and \mathsf{State_{\mu_{i},\nu}[Reaches_{ts}]} to \mathsf{False} , and in the latter case we can set \mathsf{State_{\mu_{i},\nu}[Reaches_{ts}]} to \mathsf{True} and \mathsf{State_{\mu_{i},\nu}[Reaches_{st}]} to \mathsf{False} . Notice that each node \nu of T is processed exactly once during this phase by BFS properties. Moreover, this also implies that every state pointing from a node to its parent gets updated, as desired. As the work done in \nu is linear in the size of \dirskel(\nu) (see Algorithm 2 ), with Lemma 2 we can conclude that Phase 2 runs in time O(|V(H)|+|E(H)|) . Lemma 8 . Algorithm 1 and Algorithm 2 correctly compute the states \mathsf{State_{\nu,\mu}[\cdot]} and \mathsf{State_{\mu,\nu}[\cdot]} for every edge \{\nu,\mu\} of T and run in time O(|V(H)|+|E(H)|) where H is the input graph. Input: Directed graph G , SPQR tree T having at least two nodes 1 \rho\leftarrow root of T , \mathsf{Q}\leftarrow\mathsf{queue()} , \mathsf{Q.push}(\rho) ; 2 3 while \mathsf{Q} is not empty do 4 \nu\leftarrow\mathsf{Q.pop()} ; 5 if \nu has no children in T then continue ; 6 7 Let \mu_{1},\dots,\mu_{k} be the children of \nu with pertaining virtual edges \{s_{i},t_{i}\}=e_{i} \in E(\skel(\nu)) , and \mu_{0} the parent of \nu with pertaining virtual edge e_{0}\in E(\skel(\nu)) ; 8 // \mu_{0} can be ignored if \nu=\rho \mathsf{Q.push}(\mu_{i}) \forall i\in[1,k] ; 9 AllNodeExtremities \leftarrow a set containing all the extremities of G in V(\skel(\nu)) ; 10 AllEdgeExtremities \leftarrow a set containing all the virtual edges e_{i}\in E(\skel(\nu)) such that \mathsf{State_{\nu,\mu_{i}}[NoInnerExtr]} is \mathsf{False} ; 11 for i\in[1,k] do 12 noExtr \leftarrow\mathsf{True} iff AllNodeExtremities \setminus\{s_{i},t_{i}\}=\emptyset ; 13 // Notice that it suffices to store (up to) three extremities of V(\skel(\mu)) in order to update noExtr in constant time \mathsf{State_{\mu_{i},\nu}[NoInnerExtr]}\leftarrow ( AllEdgeExtremities \setminus\{\{s_{i},t_{i}\}\}=\emptyset ) \land noExtr ; 14 // Similarly, it suffices to store (up to) two virtual edges of \skel(\nu) with corresponding extremity states leaving \nu set to \mathsf{False} if \mathsf{State_{\mu_{i},\nu}[NoInnerExtr]} is \mathsf{False} then 15 \mathsf{State_{\mu_{i},\nu}[Acyclic]}\leftarrow\mathsf{Null} ; 16 if at least two states among \{\mathsf{State_{\nu,\mu_{1}}[Acyclic]},\dots,\mathsf{State_{\nu,\mu_{k}}[Acyclic]}\} evaluate to \mathsf{Null} then 17 \mathsf{State_{\mu_{i},\nu}[Acyclic]}\leftarrow\mathsf{Null}\;\forall i\in\{1,\dots,k\} ; 18 if exactly one state among \{\mathsf{State_{\nu,\mu_{1}}[Acyclic]},\dots,\mathsf{State_{\nu,\mu_{k}}[Acyclic]}\} evaluates to \mathsf{Null} then 19 Let j\in\{1,\dots,k\} be such that \mathsf{State_{\nu,\mu_{j}}[Acyclic]}=\mathsf{Null} ; 20 Y\leftarrow\{1,\dots,k\}\setminus\{j\} ; 21 \mathsf{State_{\mu_{i},\nu}[Acyclic]}\leftarrow\mathsf{Null},\;\forall i\in Y ; 22 AcyclicOutside \leftarrow true iff \bigwedge_{i\in Y\cup\{0\}}\mathsf{State_{\nu,\mu_{i}}[Acyclic]} is \mathsf{True} ; 23 if \neg AcyclicOutside then \mathsf{State_{\mu_{j},\nu}[Acyclic]}\leftarrow\mathsf{False} ; 24 else 25 // We are in conditions to build \dirskel(\nu)-s_{j}t_{j}-t_{j}s_{j} K\leftarrow\dirskel(\nu)-s_{j}t_{j}-t_{j}s_{j} ; 26 \mathsf{State_{\mu_{j},\nu}[Acyclic]}\leftarrow\mathsf{True} iff K is acyclic; 27 if no state among \{\mathsf{State_{\nu,\mu_{1}}[Acyclic]},\dots,\mathsf{State_{\nu,\mu_{k}}[Acyclic]}\} evaluate to \mathsf{Null} then 28 29 if at least two states among \{\mathsf{State_{\nu,\mu_{1}}[Acyclic]},\dots,\mathsf{State_{\nu,\mu_{k}}[Acyclic]}\} evaluate to \mathsf{False} then 30 \mathsf{State_{\mu_{i},\nu}[Acyclic]}\leftarrow\mathsf{False}\;\forall i\in\{1,\dots,k\} ; 31 if exactly one state among \{\mathsf{State_{\nu,\mu_{1}}[Acyclic]},\dots,\mathsf{State_{\nu,\mu_{k}}[Acyclic]}\} evaluates to \mathsf{False} then 32 Let j\in\{1,\dots,k\} be such that \mathsf{State_{\nu,\mu_{j}}[Acyclic]}=\mathsf{False} ; 33 Y\leftarrow\{1,\dots,k\}\setminus\{j\} ; 34 \mathsf{State_{\mu_{i},\nu}[Acyclic]}\leftarrow\mathsf{False},\;\forall i\in Y ; 35 // We are in conditions to build \dirskel(\nu)-s_{j}t_{j}-t_{j}s_{j} K\leftarrow\dirskel(\nu)-s_{j}t_{j}-t_{j}s_{j} ; 36 \mathsf{State_{\mu_{j},\nu}[Acyclic]}\leftarrow\mathsf{True} iff K is acyclic; 37 if every state among \{\mathsf{State_{\nu,\mu_{1}}[Acyclic]},\dots,\mathsf{State_{\nu,\mu_{k}}[Acyclic]}\} evaluates to \mathsf{True} then 38 // We are in conditions to build \dirskel(\mu) A\leftarrow\mathsf{FeedbackArcs(\dirskel(\nu))}\cap\{e_{1},\dots,e_{k}\} ; 39 // A contains those virtual edges of \dirskel(\nu) which are feedback arcs in \dirskel(\nu) \mathsf{State_{\mu_{i},\nu}[Acyclic]}\leftarrow\mathsf{True}\;\forall e_{i}\in A ; 40 \mathsf{State_{\mu_{i},\nu}[Acyclic]}\leftarrow\mathsf{False}\;\forall e_{i}\notin A ; 41 Algorithm 2 Superbubble finding – Phase 2 4.4 Algorithm - Phase 3 In Phase 3 the pairs (s,t) , (t,s) such that \{s,t\} is a separation pair of H are reported. (Recall that these are necessarily endpoints of virtual edges due to Lemma 1 and Proposition 1 ). Further, if a pair of vertices are adjacent in the skeleton of an S-node and these identify a superbubble then the corresponding superbubble graph is not within the S-node, as we show next. Proposition 2 (Superbubbles and S-nodes) . Let G be a directed graph, let (s,t) be a superbubble of G with graph B , let T be the SPQR tree of a maximal 2-connected subgraph of G , and let e=\{s,t\} be a virtual edge of a node of T . If the pertaining node of e is an S-node then B\not\subseteq\expansion(e) . Proof. Suppose for a contradiction that B\subseteq\expansion(e) . By definition of S-node, the graph \expansion(e) is a split component of the split pair \{s,t\} and moreover contains a vertex y separating s from t , so y is an s - t cutvertex in B since B\subseteq\expansion(e) . The result now follows from Lemma 4 . ∎ Thus, if (s,t) is a superbubble and \{s,t\} is a separation pair of H , then there is a P-node of T with vertex-set \{s,t\} , or there is an R-node of T with a virtual edge \{s,t\} . We discuss informally the two cases. SPQR trees encode not only every separation pair of the graph but also the respective sets of split components. The way in which these split components are put together to form the skeletons of the nodes is what defines the different types of nodes, S, P, and R, as well as the SPQR tree itself. For the application of finding superbubbles, examining only the natural separations (and split components thereof) encoded in the SPQR tree is not enough to ensure completeness. Consider, for instance, a P-node \mu with k\geq 4 split components. The separations encoded in each of the k tree-edges incident to \mu implicitly group k-1 expansions of the edges of \skel(\mu) and puts the vertices therein in one side of the separation, and the vertices on the expansion of remaining virtual edge is put on the remaining side of the separation. However, it may be that the graph of a superbubble could match, e.g., the union of the expansions of two virtual edges of \skel(\mu) . To overcome this, we first iterate over all the P-nodes of T (say, with vertex set \{s,t\} ) and group the virtual edges containing out-neighbours of s and group the virtual edges containing in-neighbours of t ; these have to match, otherwise (s,t) is not a superbubble. Further, for each virtual edge in these (matching) sets, we check if the respective state leaving this P-node has the acyclicity and absence-of-extremities fields set to true. Finally, if all the out-neighbors (resp. in-neighbors) of s (resp. t ) are contained in candidate superbubble graph given by the matching sets, and ts\notin E(G) , then (s,t) is a superbubbloid by Lemma 7 . Minimality follows from the structure of P-nodes as follows. If the resulting matching sets have more than one edge then minimality follows from Lemma 4 . Otherwise, if the pertaining node of the unique edge in the set is an S-node then Proposition 2 tells us that the expansion of that edge is not a superbubble, and so in this case S-nodes can be ignored; hence the pertaining node in question is an R-node, in which case minimality follows easily due to the connectivity of R-nodes. We formalize this discussion with the next two results. Proposition 3 (Superbubbloids and P-nodes, see Figure 8 ) . Let G be a directed graph, H be a maximal 2-connected subgraph of G , and \mu be a P-node of the SPQR tree of H . Let e_{1},\dots,e_{k} denote the edges of \skel(\mu)) with endpoints \{s,t\} (k\geq 3) . Let E^{+}_{s}=\{e_{i}:V(\expansion(e_{i}))\cap N^{+}(s)\neq\emptyset\} , E^{-}_{t}=\{e_{i}:V(\expansion(e_{i}))\cap N^{-}(t)\neq\emptyset\} , and K=\bigcup_{e\in E^{+}_{s}}\expansion(e) . Then (s,t) identifies a superbubbloid of G with graph K if and only if E^{+}_{s}\neq\emptyset , E^{+}_{s}=E^{-}_{t} , N^{+}_{G}(s)\subseteq V(K) , N^{-}_{G}(t)\subseteq V(K) , ts\notin E(G) , and for each e\in E^{+}_{s} the graph \expansion(e) is acyclic and does not contain extremities of G except \{s,t\} . Proof. (\Rightarrow) Let (s,t) be a superbubbloid of G with graph B and let \mu be a P-node whose skeleton has vertex set \{s,t\} . Since superbubbles are contained in the blocks of G by Lemma 5 and s,t\in V(H) it follows that V(B)\subseteq V(H) . Further, since B contains all the out-neighbors of s and V(B)\subseteq V(H) , it follows that E^{+}_{s}\neq\emptyset (analogously, E^{-}_{t}\neq\emptyset ). We show that K=B . We show that K\subseteq B . Notice that K is an induced subgraph since each expansion is induced and there are no edges across expansions. Since B is also induced by definition of superbubbloid, it is enough to show that any vertex in K is also in B . Notice that if u\in V(K) then u\in\expansion(e) for some e\in E^{+}_{s} . As established in the proof of (1) of Lemma 7 , \expansion(e) has a directed path from s to t through u since it is acyclic and has no extremities except \{s,t\} , and since (s,t) is a superbubbloid, we have u\in B . Now we show that B\subseteq K . Suppose for a contradiction that B\not\subseteq K . Since K and B are induced subgraphs there is a vertex v\in V(B)\setminus V(K) . So in particular, s reaches v without t via some directed path. Due to the structure of P-nodes, this path is contained in \expansion(e) for some e\in E(\skel(\mu)) . Thus, the first vertex following s in this path is also in \expansion(e) and hence \expansion(e) has an out-neighbour of s . Therefore e\in E^{+}_{s} and hence v\in V(K) , a contradiction. The conditions N^{+}_{G}(s)\subseteq V(K) and N^{-}_{G}(t)\subseteq V(K) follow trivially since B=K , and ts\notin E(G) because (s,t) is a superbubbloid. Further, for each e\in E^{+}_{s} the graph \expansion(e) is acyclic and does not contain extremities of G except \{s,t\} , since a cycle or extremity except \{s,t\} in some expansion would be a cycle or extremity in K , each contradicting the fact that K is a superbubbloid graph. The equality E^{+}_{s}=E^{-}_{t} follows at once from the fact that B=K=\bigcup_{e\in E^{+}_{s}}\expansion(e) and N^{+}_{G}(s)\subseteq V(K) and N^{-}_{G}(t)\subseteq V(K) . (\Leftarrow) First, notice that if \{s,t\} is not a separation pair then \skel(\mu) has exactly three edges, two of which are the real edges st and ts (recall that G has no parallel edges and that |E(\skel(\mu))|\geq 3 by definition), a contradiction to the assumption that ts\notin E(G) . So \{s,t\} is a separation pair and K consists of a union of a nonempty subset of split components of \{s,t\} since E^{+}_{s}\neq\emptyset . Moreover, K has no extremities of G except \{s,t\} because \expansion(e) has no extremities of G except \{s,t\} for every e\in E^{+}_{s} . Further, since \expansion(e) is acyclic and has no sources or sinks except \{s,t\} for all e\in E^{+}_{s} , it follows that one vertex in \{s,t\} is the unique source and the other is the unique sink of \expansion(e) (see Lemma 6 ); due to the neighborhood constraints, it follows that s is the source and t is the sink of \expansion(e) . Also, since \expansion(e) is acyclic for each e\in E^{+}_{s} , any cycle in K contains vertices from different split components. So a cycle in K contains both s and t , but since s is a source (and t is a sink) in \expansion(e) for any e\in E^{+}_{s} , it follows that K is acyclic. So we are in conditions of applying Lemma 7 and conclude that (s,t) is a superbubbloid of G with graph K . ∎ Figure 8 : Superbubbloids in a P-node ( Proposition 3 ). (a) P-node skeleton with four parallel split components between s and t . The green edges are those whose expansion contains out-neighbors of s and in-neighbors of t ( E^{+}_{s}=E^{-}_{t} ). (b) The three green paths go from s to t and their union K forms the superbubbloid graph. The gray path goes from t to s and is not part of K . Proposition 4 (Superbubbles and R-nodes) . Let G be a directed graph, H be a maximal 2-connected subgraph of G , and \nu,\mu be nodes of the SPQR tree of H . Let e_{\mu}=\{s,t\}\in E(\skel(\nu)) be the virtual edge pertaining to \mu and e_{\nu}\in E(\skel(\mu)) be the virtual edge pertaining to \nu . If \nu is an R-node, N^{+}_{G}(s),N^{-}_{G}(t)\subseteq V(\expansion(e_{\nu})) , \expansion(e_{\nu}) is acyclic and has no extremities except \{s,t\} , ts\notin E(G) , then (s,t) is a superbubble with graph \expansion(e_{\nu}) . Proof. Let K=\expansion(e_{\nu}) . Notice that \{s,t\} is a separation pair of H and that K is a split component with respect to \{s,t\} . So we are in conditions of applying Lemma 7 , which implies that (s,t) is a superbubbloid with graph K . Next we argue on the minimality. Notice that \skel(\nu) has three internally vertex-disjoint s - t paths since it is 3-connected. Then \skel(\nu) without the edge \{s,t\} has two internally vertex-disjoint s - t undirected paths and hence so does K (split components are connected, so a path through the edges of \skel(\nu) can be mapped to a path in K ). Therefore (s,t) is a superbubble by Lemma 4 . ∎ Input: Directed graph G , SPQR tree T having at least two nodes 1 for every P-node \mu of T do 2 Build the sets E^{+}_{s},E^{-}_{t} of \mu as described in Proposition 3 ; 3 Build the sets E^{-}_{s},E^{+}_{t} analogously; 4 if E^{+}_{s}=E^{-}_{t} then 5 // Equivalently, E^{-}_{s}=E^{+}_{t} Let \{s,t\} be the vertex set of \skel(\mu) ; 6 Let e_{1},\dots,e_{k} denote the edges in \skel(\mu) (k\geq 3) ; 7 Let \mu_{1},\dots,\mu_{\ell} denote the pertaining nodes of edges in E^{+}_{s} (\ell\geq 0) ; 8 Let \mu^{\prime}_{1},\dots,\mu^{\prime}_{\ell^{\prime}} denote the pertaining nodes of edges in E^{-}_{s} (\ell^{\prime}\geq 0) ; 9 \mathsf{assert}(\ell^{\prime}=k-\ell) ; 10 11 if \mathsf{State_{\mu,\mu_{i}}[Acyclic]} and \mathsf{State_{\mu,\mu_{i}}[NoInnerExtr]} are \mathsf{True} for all i\in\{1,\dots,\ell\} then 12 if N^{+}_{G}(s),N^{-}_{G}(t)\subseteq V(\bigcup_{e\in E^{+}_{s}}\expansion(e)) and ts\notin E(G) then 13 if \ell=1 then 14 // See Proposition 2 Report (s,t) if the pertaining node of the edge in E^{+}_{s} is not an S-node; 15 else 16 Report (s,t) ; 17 18 if \mathsf{State_{\mu,\mu^{\prime}_{i}}[Acyclic]} and \mathsf{State_{\mu,\mu^{\prime}_{i}}[NoInnerExtr]} are \mathsf{True} for all i\in\{1,\dots,\ell^{\prime}\} then 19 if N^{-}_{G}(s),N^{+}_{G}(t)\subseteq V(\bigcup_{e\in E^{-}_{s}}\expansion(e)) and st\notin E(G) then 20 if \ell^{\prime}=1 then 21 // See Proposition 2 Report (t,s) if the pertaining node of the edge in E^{-}_{s} is not an S-node; 22 else 23 Report (t,s) ; 24 25 for every R-node \mu of T do 26 for every neighbour \nu of \mu in T that is not a P-node do 27 Let \{s,t\}=e_{\mu}\in\skel(\nu) be the virtual edge pertaining to \mu ; 28 Let X=\expansion(e_{\mu}) ; 29 if \mathsf{State_{\nu,\mu}[Acyclic]} and \mathsf{State_{\nu,\mu}[NoInnerExtr]} are \mathsf{True} then 30 if N^{+}_{G}(s),N^{-}_{G}(t)\subseteq V(X) and ts\notin E(G) then 31 // And hence N^{-}_{G}(s),N^{+}_{G}(t)\subseteq\overline{V(X)} Report (s,t) ; 32 if N^{+}_{G}(t),N^{-}_{G}(s)\subseteq V(X) and st\notin E(G) then 33 // And hence N^{-}_{G}(t),N^{+}_{G}(s)\subseteq\overline{V(X)} Report (t,s) ; 34 Algorithm 3 Superbubble finding – Phase 3 Input: Directed graph G 1 Let \mathcal{B} and C\subseteq V(G) be the list of blocks and cutvertices of U(G) , respectively (k\geq 1) ; 2 3 for H\in\mathcal{B} do 4 for e=\{s,t\}\in E(H) do 5 if N^{+}_{s}(G)=\{t\} and N^{-}_{t}(G)=\{s\} and ts\notin E(G) then 6 Report (s,t) ; 7 if N^{+}_{t}(G)=\{s\} and N^{-}_{s}(G)=\{t\} and st\notin E(G) then 8 Report (t,s) ; 9 if H is a multi-bridge then 10 continue else 11 // H is 2-connected if H has exactly one source s and one sink t w.r.t. H and ts\notin E(G) then 12 if C\cap V(H)\setminus\{s,t\}=\emptyset and N^{+}_{G}(s),N^{-}_{G}(t)\subseteq V(H) and H is acyclic then 13 Report (s,t) ; 14 T\leftarrow\mathsf{BuildSPQR}(H) ; 15 \mathsf{Phase1}(G,T) ; 16 \mathsf{Phase2}(G,T) ; 17 \mathsf{Phase3}(G,T) ; 18 Algorithm 4 Superbubble finding algorithm 4.5 The superbubble finding algorithm We are in conditions to prove the correctness of the superbubble finding algorithm directly. Correctness and runtime Theorem 7 . Let G be a directed graph. The algorithm computing superbubbles ( Algorithm 4 ) is correct, that is, it finds every superbubble of G and only its superbubbles, and it can be implemented in time O(|V(G)|+|E(G)|) . Proof. (Completeness.) We argue that every superbubble (s,t) of G is reported by the algorithm. Let B denote the superbubble graph of (s,t) and H the block containing B . If (s,t) is a trivial superbubble then N^{+}_{G}(s)=\{t\} , N^{-}_{G}(t)=\{s\} , and ts\notin E(G) by definition. These are exactly the conditions tested in Line 4 and 4 , and so (s,t) is reported by the algorithm. Otherwise, if V(B)=V(H) , then (s,t) is reported by the algorithm in Line 4 : clearly, B has at most one source s and at most one sink t of G , no vertex in the interior of B is a cutvertex of G by Lemma 5 , B is acyclic, ts\notin E(G) , and the out-neighbors of s and the in-neighbors of t are all contained in H . These conditions altogether are enough to report the pair (s,t) . Otherwise \{s,t\} is a separation pair of H by Theorem 6 (so H is a maximal 2-connected subgraph of G ). Let T denote the SPQR tree of H . Since no pair of nonadjacent vertices in an S-node identifies a superbubble by Proposition 1 , it follows by Lemma 1 that \{s,t\} are endpoints of a virtual edge of a node \mu of T . This virtual edge is associated with a tree edge \{\nu,\mu\} . Let e_{\mu} be the virtual edge in \nu pertaining to \mu and let e_{\nu} the virtual edge in \mu pertaining to \nu . If \mu is an S-node then Proposition 2 implies that B\not\subseteq\expansion(e_{\mu}) . (Essentially \mathsf{State_{\nu,\mu}[\cdot]} can be ignored). Symmetrically, \mathsf{State_{\mu,\nu}[\cdot]} can be ignored whenever \nu is an S-node. If \mu is a P-node with vertex set \{s,t\} then B can be expressed as the union of the expansions of the virtual edges of \mu as described in Proposition 3 . Symmetrically, the same is done whenever \nu is a P-node. Hence, the remaining virtual edges that encode superbubbles are those contained in the R-nodes. Moreover, if the pertaining node of such a virtual edge is a P-node then (s,t) is processed when analyzing P-nodes. So it suffices to analyze P-nodes individually followed by the tree-edges \{\nu,\mu\} such that \nu is not a P-node and \mu is an R-node. We argue on the two cases separately. • \mu is a P-node: Let e_{1},\dots,e_{k} be the edges in \skel(\mu) whose endpoints are \{s,t\} (k\geq 3) . Since (s,t) is a superbubble, (s,t) is also a superbubbloid and thus Proposition 3 implies that B can be expressed, without loss of generality, as \bigcup_{i=1}^{k^{\prime}}\expansion(e_{i}) for some k^{\prime}1 . Notice the following observation concerning vertices that do not form a separation pair but form an edge of H . Observation 10 . If \skel(\mu) has two real edges \{u\alpha,v\beta\} and \{u\hat{\alpha},v\hat{\beta}\} and one virtual edge pertaining to an S-node whose expansion contains only vertex-sides at u and v with signs \alpha and \beta , respectively, then the snarl \{u\alpha,v\beta\} is reported in Line 6 of Algorithm 6 . 3. Suppose that \mu is an R-node of T with a virtual edge \{u,v\} . If the pertaining node \nu of this virtual edge is an S- or a P-node then \{u\alpha,v\beta\} was reported before. So \nu is an R-node. We claim that the vertex-sides in \expansion(e_{\nu}) all have the same sign in u , and those in \expansion(e_{\mu}) all have the opposite sign in u , and the same for v . Suppose for a contradiction (and without loss of generality) that \expansion(e_{\mu}) has vertex-sides of opposite signs at u . Then Proposition 12 gives a contradiction to the fact that \{u\alpha,v\beta\} is separable. Now notice that the conditions just established on the vertex-sides of u and v are precisely those described in Algorithm 7 and thus the snarl is reported in Line 7 when the assignments to the sign variables \alpha and \beta match those of the snarl. Otherwise \{u,v\} is an edge of H and is not a separation pair of H , so we are in conditions of applying Proposition 13 from where two cases follow. We have e=\{u\alpha,v\beta\}\in E(H) and all vertex-sides at u and v except for those in e have signs \hat{\alpha},\hat{\beta} , respectively, or e=\{u\hat{\alpha},v\hat{\beta}\}\in E(H) and all vertex-sides at u and v except for those in e have signs \alpha,\beta , respectively. In the former case the snarl \{u\alpha,v\beta\} is reported in Line 8 . In the latter case the snarl \{u\alpha,v\beta\} is reported in Line 8 (where the signs are written with the respective opposites) if also no S-node of T contains both u and v . So we are left to argue the case when T has an S-node \sigma whose skeleton contains both u and v . Our goal now is to contradict the fact \{u\alpha,v\beta\} is a snarl or to show that it is reported in another phase of the algorithm. Notice that u and v are adjacent in \skel(\sigma) because \{u,v\} is an edge of H , so let e=\{u,v\}\in E(\skel(\sigma)) . Let e_{u},e_{v}\neq e denote the edges incident to u and v in \skel(\sigma) , respectively. We do case analysis on the type of e . 1. If e is a real edge then the snarl is reported when S-nodes are analyzed: u and v are classified as good vertices due to the assumption on the vertex-sides and moreover they are consecutive in the circular list of good vertices since they are adjacent in \skel(\sigma) . 2. Otherwise e is a virtual edge. Since \{u,v\} is not a separation pair the pertaining node of e necessarily is a P-node, say \pi , such that \skel(\pi) consists of exactly two real edges and one virtual edge (which pertains to \sigma ). Indeed, if \skel(\pi) has three real edges then it is not hard to see that \{u\alpha,v\beta\} is not separable, and if \skel(\pi) has at least two virtual edges then \{u,v\} is a separation pair, both leading to a contradiction. By the assumption on the vertex-sides at u and v , we have that \{u\alpha,v\beta\} and \{u\hat{\alpha},v\hat{\beta}\} are the real edges of \skel(\sigma) , and that the vertex-sides contained in \expansion(e_{u}) all have sign \alpha and those contained in \expansion(e_{v}) have sign \beta . But then we are exactly in the conditions described in 10 , and thus the snarl is reported when P-nodes are analyzed. All cases were examined and so every snarl of G is reported by the algorithm. (Soundness.) We argue that the algorithm only reports snarls. By Lemma 11 , if \{u\alpha,v\beta\} is a snarl in a sign-cut graph of G then it is also a snarl in G . Thus, let F denote the sign-cut graph where the pair \{u\alpha,v\beta\} is reported. We show that \{u\alpha,v\beta\} is separable and minimal in F . If u\alpha and v\beta are vertex-sides of the set built in Line 9 of Algorithm 9 then u and v are both tips in F . By (1) of Theorem 8 it follows that \{u\alpha,v\beta\} is a snarl and thus the set \mathcal{T}_{i} only encodes snarls. If \{u\alpha,v\beta\} is reported by virtue of Line 5 of Algorithm 5 then u\alpha and v\beta are consecutive elements of W and u\neq v . Moreover, the conditions expressed in Algorithm 5 identify all and only good vertices. Thus Proposition 9 implies that \{u\alpha,v\beta\} is a snarl. If \{u\alpha,v\beta\} and \{u\hat{\alpha},v\hat{\beta}\} are reported in Line 7 of Algorithm 7 then Proposition 11 implies that \{u\alpha,v\beta\} is a snarl: the conditions of the statement match those in the algorithm. Applying Proposition 11 symmetrically to the other R-node implies that \{u\hat{\alpha},v\hat{\beta}\} is a snarl. If \{u\alpha,v\beta\} is reported in Algorithm 6 then Proposition 10 implies that \{u\alpha,v\beta\} is separable. Without loss of generality we argue on the minimality for Line 6 . If |E^{\alpha}_{u}|>1 then the component containing u and v after splitting u\alpha and v\beta in F has two internally vertex-disjoint u - v paths (this is easily seen from the structure of P-nodes), so we can apply Proposition 8 and conclude that \{u\alpha,v\beta\} is a snarl. Otherwise we have |E^{\alpha}_{u}|=1 . If the unique edge in E^{\alpha}_{u} is real then \{u\alpha,v\beta\} is clearly a snarl, and otherwise it is virtual and it pertains to an R-node since no two P-nodes are adjacent in T and if it is an S-node the algorithm does not report anything. Notice now that we are in conditions of applying Proposition 11 , i.e., the conditions on the sets described in Proposition 10 can be reinterpreted and plugged into Proposition 11 , from where we can conclude that \{u\alpha,v\beta\} is a snarl. If \{u\alpha,v\beta\} is reported in Line 8 then the pair is clearly a snarl whose component has vertex set \{u,v\} . If \{u\hat{\alpha},v\hat{\beta}\} is reported in Line 8 then u and v are non-tips and no skeleton of an S-node of T contains the vertices u and v . Clearly \{u\hat{\alpha},v\hat{\beta}\} is separable, so we are left to argue minimality. Since \{u,v\} is an edge of U(H) , T has a node whose skeleton contains the real edge \{u,v\} . This node is thus a P- or an R-node, and so H has three internally vertex-disjoint u - v paths (the existence of these paths is easily seen from the description of the P- and R-nodes, nonetheless we point to Lemma 2 of [ 11 ] ). One of these paths consists of the edge \{u\alpha,v\beta\} , and thus H has two internally vertex-disjoint u\hat{\alpha} - v\hat{\beta} paths because no edge in F distinct from e has a vertex-side u\alpha or v\beta . So splitting u\hat{\alpha} and v\hat{\beta} in F results in a graph with a component containing u and v which has two internally vertex-disjoint u - v paths and hence we can apply Proposition 8 to conclude that \{u\hat{\alpha},v\hat{\beta}\} is a snarl. Every line where the algorithm reports a pair of vertex-sides is analyzed and therefore the algorithm only reports snarls. ∎ See 2 Proof. First we argue that Algorithm 9 runs in linear-time. Block-cut trees can be built in linear time [ 30 ] and the total size of the blocks is linear in |V(G)|+|E(G)| . We also find the sign-cut graphs in linear time, since we only need to identify the sign-consistent cutvertices of the block-cut tree. We can suppose that we are analyzing a block H that is 2-connected, since the other cases are trivial to check. Let |H|=|V(H)|+|E(H)| . We show that the rest of the algorithm runs in time O(|H|) , thus proving the desired bound. After building the SPQR tree T of H , which can be built in O(|H|) time [ 25 ] , the algorithm examines each of the possible node types. By examination of Algorithms 5 , 6 and 7 we conclude that the work done is at most linear in the size of the skeleton of the node, except for the neighborhood queries, which we must support in constant-time. But these neighborhood queries can easily be supported in constant-time, exactly how it was described in Theorem 7 . Now we argue that the representation of the snarls has the desired size. The bound on the tip-tip snarls follows from the fact that the sum of tips over all sign-cut graphs of G is at most O(|V(G)|) . For each 2-connected block H examined by the algorithm, the total number of vertices over all skeletons of the SPQR tree of H is O(|V(H)|) (see [ 11 , Lemma 5] ) and that SPQR tree has O(|V(H)|) edges (recall Lemma 2 ), and it is not hard to see that H contributes with O(|V(H)|) many (explicitly) listed snarls to \mathcal{S} (the edge-snarls case takes constant time with linear-time preprocessing on the S-nodes and the neighborhoods of the vertices therein). Finally, within each sign-cut graph F_{i} we have \sum_{H\text{ block of }F_{i}}|V(H)|=O(|V(F_{i})|) , and each vertex of G appears in at most two sign-cut graphs. Hence \sum_{j=1}^{\ell}|S_{j}|=O(|V(G)|) . ∎ Input: Sign-cut graph F of a bidirected graph, maximal 2-connected subgraph H of F , T the SPQR tree of H for every edge e=\{u\alpha,v\beta\} of H such that u and v are non-tips in F do 1 if no edge in F distinct from e has a vertex-side u\alpha or v\beta then 2 Report \{u\alpha,v\beta\} ; 3 if no S-node \mu of T is such that \{u,v\}\subseteq V(\skel(\mu)) then 4 Report \{u\hat{\alpha},v\hat{\beta}\} ; 5 Algorithm 8 \mathsf{FindEdgeSnarls}(F,H,T) Input: Bidirected graph G Output: A linear-size encoding of snarls of G as two collections: \mathcal{T}=\{T_{1},\dots,T_{k}\} of vertex-side sets and \mathcal{S}=\{S_{1},\dots,S_{\ell}\} of unordered pairs of vertex-sides, where every unordered pair of distinct vertex-sides in T_{i} is a snarl and each S_{j} is a snarl. F_{1},\dots,F_{k}\leftarrow\mathsf{BuildSignCutGraphs}(G) ; 1 \mathcal{T}\leftarrow\{\} ; 2 \mathcal{S}\leftarrow\{\} ; 3 for i\in\{1,\dots,k\} do 4 if F_{i} is an isolated vertex then 5 continue ; 6 T_{i}\leftarrow the set of vertex-sides v\alpha where v is a tip in F_{i} with sign \alpha ; 7 \mathcal{T}\leftarrow\mathcal{T}\cup\{T_{i}\} ; 8 for every block H of F_{i} do 9 if H is a multi-bridge then 10 // The snarls in multi-bridges are reported in Algorithm 8 continue ; 11 else 12 T_{H}\leftarrow\mathsf{BuildSPQRTree}(H) ; 13 \mathcal{S}\leftarrow\mathcal{S}\cup\mathsf{FindSnarlsInSnodes}(F_{i},H,T_{H}) ; 14 \mathcal{S}\leftarrow\mathcal{S}\cup\mathsf{FindSnarlsInPnodes}(F_{i},H,T_{H}) ; 15 \mathcal{S}\leftarrow\mathcal{S}\cup\mathsf{FindSnarlsBetweenRRnodes}(F_{i},H,T_{H}) ; 16 \mathcal{S}\leftarrow\mathcal{S}\cup\mathsf{FindEdgeSnarls}(F_{i},H,T_{H}) ; 17 return (\mathcal{T},\mathcal{S}) Algorithm 9 Snarls representation algorithm 6 Ultrabubbles 6.1 Setup Ultrabubbles are snarls with two additional superbubble-like conditions. Definition 5 (Ultrabubble and Ultrabubble component [ 46 ] ) . Let G be a bidirected graph. Let \{u\alpha,v\beta\} be a pair of vertex-sides with distinct u,v\in V(G) and \alpha,\beta\in\{+,-\} . Then \{u\alpha,v\beta\} is an ultrabubble if: (a) separable: the graph created by splitting u\alpha and v\beta contains a separate component X\subseteq G containing u and v but not u^{\prime} and v^{\prime} . We call X the ultrabubble component of \{u\alpha,v\beta\} . (b) tipless: no vertex in V(X)\setminus\{u,v\} is a tip. (c) acyclic: X is acyclic. (d) minimal: no vertex-side w\gamma with vertex w\in X\setminus\{u,v\} is such that \{u\alpha,w\gamma\} and \{w\hat{\gamma},v\beta\} are separable. The interior of a separable pair of vertex-sides \{u\alpha,v\beta\} with component K is the vertex set V(K)\setminus\{u,v\} . A trivial ultrabubble is an ultrabubble whose interior is empty. It should be clear that the analogues of Lemma 5 and Theorem 6 hold for ultrabubbles, as their proofs are a simple adaptation from directed to bidirected graphs. So ultrabubbles are confined to blocks, and any ultrabubble is either trivial, the whole graph, or induces a separation pair. Moreover, also an analogue of Lemma 4 holds for ultrabubbles (see Lemma 4 of [ 26 ] ). The algorithm we propose is essentially the same as the one to find superbubbles presented in Section 4 , having only a few major differences. 6.2 The ultrabubble finding algorithm The algorithm starts by computing the blocks of the input bidirected graph G . For each block H of G it builds its SPQR tree T and therein it runs two graph traversals akin to phases one and two of the superbubbles algorithm. The algorithm maintains the following information. Let node \nu be the parent of node \mu in T , e_{\mu} and e_{\nu} the usual edges, and X:=\expansion(e_{\mu}) . • \mathsf{State_{\nu,\mu}[NoInnerExtr]}:=\mathsf{True} iff no vertex in V(X)\setminus\{s,t\} is an extremity of G . • \mathsf{State_{\nu,\mu}[Acyclic]}:=\begin{cases}\mathsf{Null},&\text{if $\mathsf{State_{\nu,\mu}[NoInnerExtr]}$ is false,}\\ \mathsf{True},&\text{otherwise, if $X$ is acyclic,}\\ \mathsf{False},&\text{otherwise.}\end{cases} As for the reachability states, since we are working with bidirected graphs now we store four kinds of reachability. So for all \alpha,\beta\in\{+,-\} we define the following states. • \mathsf{State_{\nu,\mu}[Reaches_{uv\alpha\beta}]}:=\begin{cases}\mathsf{Null},&\text{if $\mathsf{State_{\nu,\mu}[Acyclic]}$ is $\mathsf{False}$ or $\mathsf{Null}$,}\\ \mathsf{True},&\text{otherwise, if $X$ has an $s\alpha$-$t\beta$ path,}\\ \mathsf{False},&\text{otherwise.}\end{cases} The \dirskel construct defined for directed graphs naturally extends to bidirected graphs as follows. For all \alpha,\beta\in\{+,-\} let B_{\alpha\beta}=\{\{s_{i}\alpha,t_{i}\beta\}:\text{$\expansion(e_{i})$ has an $s_{i}\alpha$-$t_{i}\beta$ path, for $i=1,\dots,k$}\} . The bidirected skeleton of \mu is the graph \dirskel(\mu):=(V(\skel(\mu)),B_{++}\cup B_{+-}\cup B_{-+}\cup B_{--}) . We are now ready to proceed with the description of the phases. Some correctness details are omitted since they are just a straightforward adaptation of the proofs described in Section 4.1 . Phase 1. Recall that \nu is the parent of \mu in T . Let \{u,v\} denote the endpoints of e_{\nu} and e_{\mu} . Phase 1 is also a DFS starting at the root of T and updates the states pointing downwards from the root. The update of \mathsf{State_{\nu,\mu}[NoInnerExtr]} is identical to that for superbubbles. The update of \mathsf{State_{\nu,\mu}[Acyclic]} is also identical to that for superbubbles up to the point where graph K:=\dirskel(\mu)-\{u+,v+\}-\{u+,v-\}-\{u-,v+\}-\{u-,v-\} can be built. So at this point we have that \mathsf{State_{\nu,\mu}[NoInnerExtr]} is \mathsf{True} and the states pointing from \mu to its children all have the acyclicity state set to \mathsf{True} . Clearly, as for directed graphs, \mathsf{State_{\nu,\mu}[Acyclic]} is \mathsf{True} if K is acyclic and is \mathsf{False} otherwise. Our aim is to use DFS in order to decide acyclicity, but before that we make some observations regarding bidirected graphs and the structure of K . First notice that for any two vertices x,y\in V(K) there is at most one edge with endpoints \{x,y\} for otherwise K has a cycle. This is justified in the next result (essentially, the obvious fact that a directed graph contains a cycle whenever two of its vertices reach each other generalizes to bidirected graphs). Proposition 14 . Let G be a bidirected graph, u,v\in V(G) be vertices, and \alpha,\beta\in\{+,-\} . If G has a u\alpha - v\beta and a u\hat{\alpha} - v bidirected path then G has a cycloid. Proof. Let x\neq u be the closest vertex to u where these two paths intersect (possibly x=v ). Let p_{1} denote the first path and p_{2} the second. The subpath of p_{1} from u\alpha up to x concatenated with the reversed subpath of p_{2} from u\hat{\alpha} up to x forms a cycloid: if the vertex-side at x in the subpath of p_{1} has a different sign than that at x in the subpath of p_{2} then we have a cycloid with alternation at every vertex, and otherwise we have a cycloid where only x does not respect alternation. ∎ Furthermore, notice that if K has at most one tip then it has a cycloid (this is clear if G is directed since every directed acyclic graph contains a source and a sink, i.e., it contains two tips). See [ 26 ] for a proof of the next result. Proposition 15 . Let G be a bidirected graph having at least two vertices. If G has at most one tip then G has a cycloid. Suppose now that K has at least three tips, so pick x to be a tip which moreover is distinct from the vertices u and v . Then the vertex-sides contained in the expansions of the edges incident to x in \skel(\mu) all have sign \alpha for some \alpha\in\{+,-\} . Suppose otherwise and let e=\{x,y\}\in\skel(\mu) be an edge incident to x (possibly y=u or y=v ). Then \expansion(e) has vertex-sides of opposite signs at x . Since \expansion(e) has no extremities except possibly x and y , \expansion(e) has at most one tip, which is y , and thus it has a cycloid by Proposition 15 , a contradiction (recall that the fact that we build K implies in particular that \expansion(e) is acyclic). Therefore \mathsf{State_{\nu,\mu}[NoInnerExtr]} is \mathsf{False} because x is a tip in \expansion(e_{\mu}) , a contradiction. Therefore K has exactly two tips, which are u and v . Under these conditions deciding if K is acyclic is a simple (linear-time) task and we refer to [ 26 ] for the technical details. Essentially, we can run a DFS starting at u such that when arriving at an unvisited vertex z with a vertex-side z\gamma , the DFS prioritizes expanding to vertices in N^{\hat{\gamma}}_{G}(z) and only then considers those in N^{\gamma}_{G}(z) . Moreover, whenever an edge \{x\alpha,y\alpha\} is scanned, for some \alpha\in\{+,-\} , if y is unvisited then we can “flip” y in order to make this edge have vertex-sides of opposite signs, i.e., this bidirected edge becomes essentially a directed edge, and if y is already visited then it is possible to find a cycloid 9 9 9 In fact, a cycloid with the “exceptional” vertex. in the current graph induced by the edges which have been scanned so far; if the DFS halts without ever finding such an edge then it produces a bidirected graph where every edge has vertex-sides of opposite signs, i.e., a directed graph, in which case a standard DFS suffices to finally decide if K is acyclic. The correctness of “flipping” the vertex-sides of the vertices during the first DFS is ensured by the next result ( Proposition 16 ), i.e., flipping vertices during the first DFS preserves cycloids. Proposition 16 . Let G be a bidirected graph, let u\in V(G) be a vertex, and let G^{\prime} be the graph obtained from G by changing the positive vertex-sides at u into negative vertex-sides and the negative into positive (i.e., flipping u ). Let W be a sequence of edges of G . Then W is a bidirected walk in G if and only if W is a bidirected walk in G^{\prime} . As for the reachability states, if u is a tip with sign \gamma and v is a tip with sign \delta in K , then clearly \mathsf{Reaches_{uv\gamma\delta}} is \mathsf{True} and the remaining three reachability states are \mathsf{False} . The fact that at most one state is true is clear from Proposition 14 (since otherwise there is a cycle and by definition these states are \mathsf{Null} and we are done). To see why indeed there is one state set to true, consider a maximal bidirected path in K and observe that this path starts at u\gamma and ends at v\delta (similarly as to why a maximal path in an acyclic graph with unique source and unique sink starts at the source and ends at the sink). As usual, this path in K can be mapped to a path in X . Phase 2. This phase is also a BFS starting at the root of the tree and is essentially identical to phase two of superbubbles. The only difference is in the computation of the acyclicity states, which we describe next. Let K:=\dirskel(\nu) , let \mu_{1},\dots,\mu_{k} denote the children of \nu , and let \mu_{0} denote the parent of \nu (if \nu is the root of T then \mu_{0} can be ignored). Recall that at this point the acyclicity and absence-of-extremities states leaving \nu to \mu_{i} for i\in\{0,\dots,k\} are all set to \mathsf{True} , otherwise the states \mathsf{State_{\mu_{i},\nu}[Acyclic]} for i\in\{1,\dots,k\} are updated in the obvious way (see how to update the states in this case in the description of phase two for superbubbles). So we are indeed in conditions of building K . Similarly as for superbubbles, if K is acyclic then \mathsf{State_{\mu_{i},\nu}[Acyclic]} is \mathsf{True} for each i\in\{1,\dots,k\} (to decide if K is acyclic we can proceed identically as described above in phase one). Otherwise K has a cycloid and in order to maintain our algorithm linear-time we can compute its feedback edges. 10 10 10 For clarity, a feedback edge in a bidirected graph is an edge intersecting every cycloid of the graph. Depending on which edges are indeed feedback edges we can update the acyclicity states accordingly, like we did for superbubbles. One key observation about K is that it contains no tips. Suppose otherwise. If K has a tip x but x is not a tip in \expansion(e) for some edge e\in E(\skel(\nu)) then \expansion(e) has vertex-sides of opposite signs at x and therefore \expansion(e) has at most one tip, which is the other endpoint of e . But then Proposition 15 gives a cycloid in \expansion(e) , a contradiction since every acyclicity state pointing away from \nu is to \mathsf{True} . So indeed x is a tip for some absence-of-extremity state pointing towards \nu , and thus that state is \mathsf{False} , a contradiction. In conclusion, it is enough to devise a linear-time algorithm for finding feedback edges in tipless bidirected graphs. Such an algorithm is presented in Section 6.3 and it is followed by a hardness result for the same problem in general bidirected graphs. Phase 3. This phase is completely analogous to phase three of the superbubble finding algorithm. The only change required to the algorithm is to remove the condition of the “back-edge”, i.e., in a candidate superbubble st we must ensure that ts is not an edge, while for ultrabubbles the existence of that edge is allowed: clearly, for a separable pair of vertex-sides \{u\alpha,v\beta\} in a graph G , if \{u\hat{\alpha},v\hat{\beta}\}\in E(G) then splitting u\alpha and v\beta results in a graph where the component containing u and v does not contain the edge \{u^{\prime}\hat{\alpha},v^{\prime}\hat{\beta}\} . The remaining parts of the algorithm are completely identical and thus we obtain the next theorem. We remark that part as to why it is straightforward to get the ultrabubble algorithm from the superbubble algorithm has to do with the fact that ultrabubbles are, essentially, “weak” superbubbles (see [ 26 ] for further results and intuition on this direction). Theorem 11 . The ultrabubbles of a bidirected graph G can be computed in time O(|V(G)|+|E(G)|) . 6.3 Feedback edges in bidirected graphs Feedback edges in tipless bidirected graphs We present a linear-time algorithm computing every feedback edge of a bidirected graph G containing no tips. Recall that a feedback edge in a bidirected graph is an edge contained in every cycloid of the graph. The algorithm constructs G by ear additions. If it succeeds then the problem reduces to that of a directed graph, where known linear-time algorithms to find feedback edges can be used. Otherwise the procedure finds an obstruction and can correctly output that G has no feedback edges. We begin with a simple observation. Lemma 13 . Let G be a bidirected graph without tips. If G has a cycloid with exceptional vertex then G has no feedback edges. Proof. Let B be a cycloid in G with exceptional vertex x having sign \alpha\in\{+,-\} . Since G has no tips, there is an edge \{x\hat{\alpha},u\gamma\}\in E(G) and let p be a bidirected path consisting of that edge alone. Also because G has no tips, we can greedily extend this bidirected path from u . During the process either we visit a vertex already in p , in which case we have found a cycloid edge-disjoint from B and thus G has no feedback edges, or we hit a vertex of B for which we give the following argument. Notice that p partitions B into two subpaths. Moreover, notice that removing an edge of B from either of these subpaths leaves G with a cycloid via \{x\hat{\alpha},u\gamma\} and the untouched path (notice that this cycloid possibly has an exceptional vertex), but since any feedback edge is contained in B we can conclude that G has no feedback edges. ∎ We need two more definitions before describing the algorithm. Let H\subset G be a nonempty graph. Say that an ear is a path of G whose first and last vertex (called attachment vertices) are distinct and belong to H and every other vertex on the path does not belong to H . Say that H is digraphic if every edge of G has opposite signs in its vertex-sides. Begin by applying Proposition 15 to get a cycloid C . We can assume to be provided a cycloid without exception, for otherwise G has no feedback edge by Lemma 13 . We maintain the invariant that the graph is digraphic and is strongly connected (in the directed sense). Put H_{0}=C . Graph H_{0} is digraphic (i.e., every edge has vertex-sides of opposite signs). To ensure it is strongly connected, it is not hard to see that it suffices for that effect to invert some of its vertices (which is correct due to Proposition 16 ). So H_{0} respects the invariant. We show that if H_{i} respects the invariant then successfully adding an ear results in a graph H_{i+1} also respecting the invariant, and if not, then we either found a cycloid with exception or an edge-disjoint cycle from C . When no more ears can be added then we have recovered a graph equivalent to G in the sense of Proposition 16 . We remark that we only resign vertices of the newly added ears except for its attachment vertices as those are already in the current graph H_{i} . Suppose that V(H_{i})\subset V(G) and let x\in V(G)\setminus V(H_{i}) . Since G is tipless, vertex x is not a tip. Then build a path p^{+} starting with a vertex-side x+ until it hits a vertex of H_{i} or a vertex previously on the path. In the latter case we halt, because we have found a cycloid disjoint from C . So this path hits H_{i} first in a vertex a . Similarly, build a path p^{-} starting with a vertex-side x- until it hits either a vertex in V(H_{i}) , a vertex of p^{+} , or a vertex of p^{-} . If one of the last two cases occurs then we have found cycloid disjoint from C . So p^{-} hits H_{i} first in a vertex b . If b=a then we have found a cycloid disjoint from C , so b\neq a . Notice that the concatenation of p^{+} and p^{-} gives an ear with attachment vertices a and b . Let \alpha,\beta\in\{+,-\} denote the signs of the vertex-sides of the ear in the attachment vertices. Suppose that \alpha=\beta . The graph H_{i} has an \alpha - \hat{\beta} path 11 11 11 H_{i} also has a \hat{\alpha} - \beta path, and thus H_{i+1} also has a cycloid with exceptional vertex b . since it is strongly connected. This path together with the new ear creates a cycloid with exceptional vertex a in H_{i+1} , and so we can halt due to Lemma 13 . Otherwise \alpha\neq\beta . It is trivial to flip each vertex of the ear 12 12 12 Without loss of generality suppose that \alpha=+ . We can start at a+ and move to the consecutive vertex in the a+ - b- path while greedily flipping vertices in order to make every edge directed. Essentially, the first edge has a plus and a minus, the second too, and so on and so forth, until we reach the last vertex, which must b and moreover is contained in the vertex-side b- . so that the every edge has vertex-sides of opposite signs, which makes H_{i+1} digraphic. We are left to argue that H_{i+1} is strongly connected. Assume without loss of generality that \alpha=+ . Notice that H_{i} has +- and -+ paths for any two vertices since it is strongly connected. Let u be a vertex contained in the ear distinct from a and b and let v\in V(H_{i}) (clearly, any two vertices in the ear are strongly connected in H_{i+1} ). We show that H_{i+1} has u+ - v- and v+ - u- paths, thus showing that H_{i+1} is strongly connected. Since a\in V(H_{i}) , H_{i} has a v+ - a- path, which prepended with the a+ - u- subpath of the ear gives a v+ - u- path in H_{i+1} . (Notice that the a+ - u- exists by construction of ear). Similarly, since b\in V(H_{i}) , H_{i} has a b+ - v- path, which prepended with the u+ - b- subpath of the ear gives a u+ - v- path in H_{i+1} . Suppose now that V(H_{i})=V(G) and E(H_{i})\subset E(G) . Let e\in E(G)\setminus E(H) . If the vertex-sides of e have the same sign then we have found a cycloid with exception (similarly to the case where the ear had vertex-sides of the same sign in the attachment vertices, i.e., when \alpha=\beta ). Otherwise H_{i+1} is digraphic since H_{i} is digraphic, e has vertex-sides of opposite signs, and H_{i+1}=H_{i}+e . Further, H_{i+1} is strongly connected because H_{i} is strongly connected and V(H_{i+1})=V(H_{i}) . Finally we have H_{i+1}=G . Due to the invariant, G is digraphic and is strongly connected. In conclusion, if the ear addition procedure succeeds then we know that G is essentially a strongly connected directed graph, where linear-time algorithms to find feedback edges are known. If it fails then we know that the graph has no feedback edges. We are left to examine the running time of the ear-addition construction. Theorem 12 . There is an algorithm that finds all the feedback edges of a tipless bidirected graph in time O(|V(G)|+|E(G)|) . Proof. We argue that the ear addition procedure takes O(|V(G)|+|E(G)|) time. Finding H_{0} and the ears takes linear time: we can greedily extend the walk (e.g., by always taking an arbitrary edge incident to the current vertex being extended) until we hit a relevant vertex for the construction. Flipping the vertices of the ears takes linear time in the size of the ear, and since every vertex is flipped at most once and the ears partition E(G) , the overall time taken to flip the vertices during the construction is \Theta(|V(G)|+|E(G)|) . The checks on the vertex-sides at the attachment vertices when adding ears take constant time. ∎ Hardness of computing feedback edges Recall the Triangle problem where one is given an undirected graph G^{\prime}=(V^{\prime},E^{\prime}) and asked whether it contains a cycle of length 3 , that is, a triangle. The k - Clique Conjecture (see Conjecture 10 of 34 ) asserts in particular that a triangle cannot be found in time O(n^{\omega-\epsilon}) for matrix multiplication exponent \omega and any \epsilon>0 . We argue that under the k - Clique Conjecture , one cannot decide whether a bidirected graph has bidirected feedback edge , i.e., whether it can be made acyclic by removing a single edge in time O(n^{\omega-\epsilon}) for any \epsilon>0 . Theorem 13 . Under the k - Clique Conjecture , the existence of a bidirected feedback edge cannot be decided in time O(n^{\omega-\epsilon}) for any \epsilon>0 . Proof. Take an arbitrary instance G_{T}=(V_{T},E_{T}) of Triangle . By a standard color-coding-like reduction, we can reduce Triangle to the Tripartite Triangle problem [ 16 ] where we look for a triangle in an undirected tripartite graph G_{3}=(A,B,C,E_{3}) with tripartite sets A , B , and C such that both endpoints of all edges in E_{3} come from distinct sets. The reduction multiplies the number of vertices by 3 and the number of edges by 6 , so solving Tripartite Triangle is as hard as hard solving Triangle . We will next show a reduction from Tripartite Triangle to finding a bidirected feedback edge in a bidirected graph G=(V,E) . Let G_{3}=(A,B,C,E_{3}) be an instance of Tripartite Triangle . Construct a bidirected graph on the vertex set A\cup B\cup C\cup\{x,y,z\} with auxiliary vertices x , y , and z . For every edge \{u,v\}\in E_{3} , (1) if u\in A and v\in B , add the edge \{u-,v+\} ; (2) if u\in A and v\in C , add the edge \{u+,v-\} ; and (3) if u\in B and v\in C , add the edge \{u-,v-\} . Finally, add bidirected edges \{x+,y-\} , \{y+,z-\} , and \{z+,x-\} . We claim that G has a bidirected feedback edge if and only if G_{3} does not have a triangle. Suppose G_{3} has a triangle \{a,b,c\} with a\in A , b\in B , and c\in C . Then, there are two disjoint cycles with the edges \{x+,y-\} , \{y+,z-\} , \{z+,x-\} and \{a-,b+\} , \{b-,c-\} , \{c-,a+\} in G , and no bidirected feedback edge can exist. Suppose now instead that no triangle exists in G_{3} . We need to show that there are no other cycles in G than the one with the edges \{x+,y-\} , \{y+,z-\} , \{z+,x-\} . Consider any alternating closed walk W in G with edges \{v_{1}\alpha_{1},v_{2}\hat{\alpha_{2}}\},\{v_{2}\alpha_{2},v_{3}\hat{\alpha_{3}}\},\dots,\{v_{\ell}\alpha_{\ell},v_{1}\alpha_{1}^{\prime}\} with v_{1},v_{2},\dots,v_{\ell}\in A\cup B\cup C and \alpha_{1},\alpha_{2},\dots,\alpha_{\ell},\alpha_{1}^{\prime}\in\{+,-\} . Note that v_{2},v_{3},\dots,v_{\ell}\not\in C , since for all v\in C all vertex-sides are of the form v- . Because of the construction, it also cannot be that v_{i},v_{i+2\,\text{mod}\,\ell}\in X and v_{i+1\,\text{mod}\,\ell}\in Y for any i\in\{1,\dots,\ell\} with X,Y\in\{A,B,C\} . Therefore, we must have that \ell=3 , v_{1}\in C , and either v_{2}\in A , v_{3}\in B or v_{2}\in B , v_{3}\in A . In this case, we have a tripartite triangle \{v_{1},v_{2},v_{3}\} , resulting in a contradiction. Hence, G cannot contain any other cycles and thus, for example, \{x+,y-\} is a bidirected feedback edge. ∎ By omitting the edges \{x+,y-\} , \{y+,z-\} , and \{z+,x-\} from G , we immediately get the following corollary. Corollary 2 . Under the k - Clique Conjecture , the acyclicity of a bidirected graph cannot be decided in time O(n^{\omega-\epsilon}) for any \epsilon>0 .