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 † · 2026
Read Identifying bubble-like subgraphs in linear-time via a unified SPQR-tree framework by Francisco Sena, Aleksandr Politov ∗, Corentin Moumard, Massimo Cairo, Romeo Rizzi, Manuel Cáceres, Sebastian Schmidt †, Juha Harviainen †, 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-2604-08071.txt.
Description
Sena and eight colleagues present linear-time algorithms, first of their kind, for finding all snarls and ultrabubbles in directed or bidirected graphs, closing problems open since 2018. Finding all subgraphs of a given type, such as superbubbles, in such graphs is basic in biology. These subgraphs mark regions of genetic change, helping analyze genome sets. The snarl method uses a new compact representation of all snarls by vertex count. The team uses SPQR-tree decomposition, holding all 2-cuts of a linked graph.
Catalog record
| CREATOR | Francisco Sena, Aleksandr Politov ∗, Corentin Moumard, Massimo Cairo, Romeo Rizzi, Manuel Cáceres, Sebastian Schmidt †, Juha Harviainen †, Alexandru I. Tomescu † |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 190835 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.08071