The Power of Graph Doubling: Computing Ultrabubbles in a Bidirected Graph by Reducing to Weak Superbubbles
Sebastian Schmidt, Juha Harviainen, Corentin Moumard \cref foot:contribution, Aleksandr Politov \cref foot:contribution, Francisco Sena \cref foot:contribution, Alexandru I. Tomescu · 2026
Read The Power of Graph Doubling: Computing Ultrabubbles in a Bidirected Graph by Reducing to Weak Superbubbles by Sebastian Schmidt, Juha Harviainen, Corentin Moumard \cref foot:contribution, Aleksandr Politov \cref foot:contribution, Francisco Sena \cref foot:contribution, Alexandru I. Tomescu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13074.txt.
Introduction
Schmidt and five co-authors show how graph doubling computes ultrabubbles in bidirected graphs by reducing them to weak superbubbles. In such graphs arcs can enter both ends or leave both ends, so walks can change direction. These bubbles, common in biological graphs, act as nested clusters cut off by only two nodes. Since doubling keeps connectivity, it links the two bubble kinds directly, giving the first linear-time reduction-based algorithm for them on any such graph.
Catalog record
| CREATOR | Sebastian Schmidt, Juha Harviainen, Corentin Moumard \cref foot:contribution, Aleksandr Politov \cref foot:contribution, Francisco Sena \cref foot:contribution, Alexandru I. Tomescu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52605 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.13074
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Power of Graph Doubling: Computing Ultrabubbles in a Bidirected Graph by Reducing to Weak Superbubbles Sebastian Schmidt, Juha Harviainen, Corentin Moumard \cref foot:contribution, Aleksandr Politov \cref foot:contribution, Francisco Sena \cref foot:contribution, Alexandru I. Tomescu Abstract Bidirected graphs are a common generalisation of directed graphs where arcs can also be incoming to both their incident nodes, or outgoing from both their incident nodes. Such arcs allow a walk to change direction. Some algorithms can easily be adapted from directed graphs to bidirected graphs, such as shortest path algorithms. These adaptions are already used in practice, and implicitly use graph doubling as a technique to apply an algorithm for directed graphs to bidirected graphs. In other cases, the applicability of graph doubling is not that obvious. For example, superbubbles and their generalisation to bidirected graphs ultrabubbles appear similar, but the similarity is hidden enough such that it was not yet discovered by the community. Ultrabubbles are a common structure in bidirected biological graphs which carries biological meaning, but also functions as a nested clustering method, since an ultrabubble is separated by only two nodes from the rest of the graph. There is an existing method that enumerates a structure similar to ultrabubbles by enumerating (weak) superbubbles in the doubled graph. However, the literature currently lacks a theoretical investigation if that structure is actually ultrabubbles, or if there is any connection between superbubbles and ultrabubbles except that a superbubble is an ultrabubble in a directed graph. A partial result connecting superbubbles and ultrabubbles exists by Harviainen et al. (2026). They orient a bidirected graph with a special method to fix conflicts and then enumerate weak superbubbles, resulting in an enumeration of ultrabubbles in the original graph. This technique works only on bidirected graphs that contain a source, sink, or cut node, since the conflicts in orientation are fixed in a way that does not maintain connectivity. Graph doubling on the other hand maintains connectivity, and allows to draw a direct connection between ultrabubbles and weak superbubbles. This results in the first linear-time reduction-based algorithm for computing ultrabubbles on any bidirected graph. Together with the fact that graph doubling is already used implicitly in simple cases, our result motivates that graph doubling is a powerful yet simple technique to apply algorithms for directed graphs to bidirected graphs. \crefformat footnote#2 1 1 footnotemark: 1 #3 Department of Computer Science, University of Helsinki, [email protected]://orcid.org/0000-0003-4878-2809 Department of Computer Science, University of Helsinki, [email protected]://orcid.org/0000-0002-4581-840X Department of Computer Science, University of Helsinki, [email protected] Department of Computer Science, University of Helsinki, [email protected] Department of Computer Science, University of Helsinki, [email protected]://orcid.org/0000-0002-3508-4473 Department of Computer Science, University of Helsinki, [email protected]://orcid.org/0000-0002-5747-8350 We want to thank an anonymous reviewer of [ 13 ] for posing the question if graph doubling can be used to compute ultrabubbles via computing superbubbles. ccs Applied computing Bioinformatics ccs Theory of computation Graph algorithms analysis keywords Doubled graph, Bidirected graphs, Graph algorithms, Ultrabubbles, Superbubbles, Pangenomics † † runningtitle: The Power of Graph Doubling: Reducing Ultrabubbles to Weak Superbubbles † † runningauthor: Schmidt et al. † † copyright: Sebastian Schmidt, Juha Harviainen, Corentin Moumard, Aleksandr Politov, Francisco Sena and Alexandru Ioan Tomescu † † funding: Co-funded by the European Union (ERC, SCALEBIO, 101169716). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. Co-funded also by the Research Council of Finland, Grants 346968 and 358744. † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction 1.1 Bidirected graphs Figure 1: Three representations of the same bidirected graph. (a) Arrow representation. An arc can be incoming or outgoing at both ends. If a walk enters a node incoming, it must leave outgoing, and if a walk enters outgoing, it must leave incoming. Arcs with two outgoing ends allow a walk to switch from forward to reverse, and two incoming ends allow a walk to switch from reverse to forward. The sequence 1,2,2,3,4,4,3,3,4,5 is a walk W . (b) Signed representation. A walk alternates signs at each node. W is represented by the sequence 1+,2+,2+,3-,4-,4+,3+,3-,4-,5+ . (c) Doubled graph. Multiarcs caused by the self loops have been collapsed into a single arc. This is a directed graph produced by the doubling operation applied to (b). Directed self loops become directed self loops in the doubled graph, while ++ and -- self loops become arcs between - and + of the same node. W is represented by the sequence 1+,2+,2+,3-,4-,4+,3+,3-,4-,5+ . Bidirected graphs are a generalisation of directed graphs where arcs can also be incoming to both their incident nodes, or outgoing from both their incident nodes. In mathematical contexts, they are usually depicted as undirected graphs with plus or minus signs at the incidences. A walk must obey the sign-alternation rule, meaning that when it enters a node with a - ( + ), then it must leave it through a + ( - ). The edges in a bidirected graph are represented by unordered pairs of signed nodes v\alpha which are pairs of a node v and a sign \alpha\in\{+,-\} . See \Cref fig:doubling (b) for an example of this definition and see \Cref fig:doubling (a) for a visualisation that draws the connection to directed graphs. Bidirected graphs are heavily used in practice in bioinformatics [ 2 , 18 , 16 ] , besides being also interesting generalisation of directed graphs from a theoretical perspective [ 24 ] . While bidirected graphs are a simple generalisation of directed graphs, graph algorithms for directed graphs require at least extra consideration when applied to bidirected graphs, and at worst completely different approaches. Typically, graph algorithms have to be modified to track the signs of nodes. For example, Dijkstra’s classic shortest path algorithm [ 8 ] can be applied to bidirected graphs by tracking the two signs of as two separate nodes, and specifying the start and target nodes with signs. In the same way, reachability-based algorithms can be modified. As these modifications are rather straightforward, they are quietly being used in practice when applicable [ 5 , 6 , 9 , 14 , 27 , 23 ] . However, not all cases are that simple, and in this work we consider one such case. 1.2 Bubbles Figure 2: (a) The classic notion of a bubble: a path that diverges and then merges. (b) Due to the cycle 2,3,5,2 , the pair (1,6) is not a superbubble. If the red arc R is removed, then the cycle is broken and (1,6) is a superbubble. If additionally the green arc G is removed, then 4 is a tip, and hence (1,6) is not a superbubble. (c) Same graph as in (b), but the red edge R has different signs. Due to the cycloid 2+,3+,5+,2- , the pair \{1+,6-\} is not an ultrabubble. If the red edge R