arxiv: 2604.08071 · v1 · submitted 2026-04-09 · 💻 cs.DS

Recognition: 2 theorem links

· Lean Theorem

Identifying bubble-like subgraphs in linear-time via a unified SPQR-tree framework

Aleksandr Politov, Alexandru I. Tomescu, Corentin Moumard, Francisco Sena, Juha Harviainen, Manuel C\'aceres, Massimo Cairo, Romeo Rizzi, Sebastian Schmidt

Authors on Pith no claims yet

Pith reviewed 2026-05-10 17:57 UTC · model grok-4.3

classification 💻 cs.DS

keywords snarlsultrabubblessuperbubblesSPQR-treelinear-time algorithmsbidirected graphsfeedback arcsgenome graphs

0 comments

The pith

SPQR-tree decompositions combined with linear-time feedback arc computation identify all snarls and ultrabubbles.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops the first linear-time algorithms for locating all snarls and all ultrabubbles in directed or bidirected graphs. These subgraphs mark regions of genetic variation and support analysis of genome collections. The method decomposes the input via SPQR-trees to handle 2-separators, maintains acyclicity properties through repeated traversals, and solves the simultaneous acyclicity tests by computing all feedback arcs at once. A supporting result shows feedback arcs can be found in linear time on tipless bidirected graphs. The same framework supplies a distinct linear-time algorithm for superbubbles and suggests a pattern for other bubble-like subgraphs.

Core claim

After decomposing a biconnected component with its SPQR-tree, several dynamic-programming traversals maintain key properties such as acyclicity; a given 2-separator defines a reportable snarl or ultrabubble precisely when the corresponding subgraph is acyclic, and all such acyclicity tests are performed simultaneously by computing the feedback arcs of the component. This yields both a linear-size representation of all snarls and linear-time enumeration of all snarls and all ultrabubbles, while also producing an independent linear-time superbubble algorithm.

What carries the argument

The SPQR-tree decomposition, which encodes all 2-separators of a biconnected graph, together with dynamic-programming traversals that maintain acyclicity properties through a single linear-time computation of all feedback arcs in tipless bidirected graphs.

If this is right

All snarls admit a linear-size representation and can be enumerated in linear time.
All ultrabubbles can be enumerated in linear time.
Superbubbles admit a completely different linear-time enumeration algorithm.
Acyclicity of linearly many candidate subgraphs can be decided simultaneously via one feedback-arc computation.
The same SPQR-tree traversals decide membership for multiple bubble-like subgraph types.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The unified SPQR-tree approach may extend directly to other named bubble-like subgraphs that have not yet been enumerated in linear time.
The new linear-time feedback-arc result for tipless bidirected graphs could serve as a primitive for additional problems on genome variation graphs.
SPQR-tree methods may become a standard tool for separator-based problems in computational biology beyond their traditional graph-drawing uses.
Implementations could be tested on large collections of real genome graphs to measure practical speedups over prior quadratic or higher methods.

Load-bearing premise

The input graphs admit an SPQR-tree decomposition and the linear-time feedback-arc result for tipless bidirected graphs holds without hidden quadratic factors in the traversals.

What would settle it

A concrete tipless bidirected graph on which the feedback-arc procedure takes more than linear time in the number of vertices, or a small bidirected graph containing a snarl or ultrabubble that the reported set fails to include.

Figures

Figures reproduced from arXiv: 2604.08071 by Aleksandr Politov, Alexandru I. Tomescu, Corentin Moumard, Francisco Sena, Juha Harviainen, Manuel C\'aceres, Massimo Cairo, Romeo Rizzi, Sebastian Schmidt.

**Figure 2.** Figure 2: A directed graph (left) and the SPQR tree of its (biconnected) underlying undirected graph (right). Virtual [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Figure 3: Superbubbles, snarls and ultrabubbles in a directed or bidirected graph naturally map to the SPQR tree of [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

**Figure 4.** Figure 4: Phase 1 of the superbubble-finding algorithm (bottom-up DFS traversal of the SPQR tree). In (a), the [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗

**Figure 5.** Figure 5: Phase 2 of the superbubble finding algorithm (BFS from the root). The algorithm processes node [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗

**Figure 6.** Figure 6: The reduction from finding triangles in tripartite graphs (left) to finding bidirected feedback edges, or [PITH_FULL_IMAGE:figures/full_fig_p014_6.png] view at source ↗

**Figure 7.** Figure 7: Why nonadjacent vertices in an S-node do not form superbubbles (Proposition 1). (a) S-node skeleton of a [PITH_FULL_IMAGE:figures/full_fig_p018_7.png] view at source ↗

**Figure 8.** Figure 8: Superbubbloids in a P-node (Proposition 3). (a) P-node skeleton with four parallel split components [PITH_FULL_IMAGE:figures/full_fig_p026_8.png] view at source ↗

**Figure 9.** Figure 9: Illustration of sign-cut graphs (Definition 4). (a) A bidirected graph [PITH_FULL_IMAGE:figures/full_fig_p030_9.png] view at source ↗

**Figure 10.** Figure 10: A dangling block H′ with respect to u and H (Proposition 5). (a) Block H′ (green) has both + and − vertex-sides at u, while H (purple) has only +. (b) After splitting u+, the path through H′ (blue) connects u to u ′ , so {uα, vβ} is not separable. 1. If u and v are distinct tips in F with signs α, β ∈ {+, −}, respectively, then {uα, vβ} is a snarl of G. 2. If {uα, vβ} is a snarl of G and u and v are non-t… view at source ↗

**Figure 11.** Figure 11: Finding nontip-nontip snarls in the three types of SPQR tree nodes. Real edges are solid gray and virtual [PITH_FULL_IMAGE:figures/full_fig_p037_11.png] view at source ↗

read the original 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 bidirected input graph. These correspond to regions of genetic variation and are useful in analyzing collections of genomes. We present the first linear-time algorithms for identifying all snarls and all ultrabubbles, resolving problems open since 2018. The algorithm for snarls relies on a new linear-size representation of all snarls with respect to the number of vertices in the graph. We employ the well-known SPQR-tree decomposition, which encodes all 2-separators of a biconnected graph. After 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 linear-time complexity is that acyclicity of linearly many subgraphs can be tested simultaneously via the 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 this is at least as hard as matrix multiplication, assuming the k-Clique Conjecture. 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives the first linear-time algorithms for snarls and ultrabubbles by reducing the problem to feedback arcs on tipless bidirected graphs inside an SPQR-tree framework.

read the letter

The core advance is a linear-time solution for snarls and ultrabubbles, problems left open since 2018. The authors also supply a new linear-size snarls representation and show the same machinery yields a different linear-time superbubble algorithm. The approach rests on SPQR-tree decomposition of biconnected components, a handful of dynamic-programming traversals to track acyclicity and other properties at 2-separators, and a reduction that batches the acyclicity tests into one feedback-arc computation on a derived tipless bidirected graph. They prove the feedback-arc step runs in linear time for this restricted class, while the general case remains matrix-multiplication hard under standard conjectures. The SPQR construction and traversals themselves are standard and already linear, so the new primitive carries the complexity claim. The ideas are conceptually straightforward once the reduction is in place, and the framework looks reusable for other bubble-like subgraphs. The main soft spot is the tipless feedback-arc algorithm itself. The abstract states that the reduction from the SPQR-derived candidates preserves the tipless property and introduces no hidden quadratic work, but that step is the only place where super-linear cost could sneak in. If the auxiliary graph construction or the traversal order adds extra factors, the overall bound fails. The rest of the argument appears to follow from known linear-time primitives. This paper is aimed at people building pangenome tools who need scalable detection of variation regions, and at graph theorists interested in bidirected graphs and separator-based decompositions. A reader working on practical genome-graph algorithms will find the unified framework and the new representation useful even if they only adopt the high-level structure. The work is technically grounded enough and the claims specific enough that it deserves a serious referee. I would send it out for review.

Referee Report

1 major / 2 minor

Summary. The paper claims the first linear-time algorithms for identifying all snarls and all ultrabubbles in directed or bidirected graphs. It relies on SPQR-tree decompositions of biconnected graphs to encode 2-separators, followed by dynamic-programming traversals that maintain acyclicity and other properties to decide which separators define reportable subgraphs. A core technical ingredient is a new reduction showing that acyclicity tests over linearly many candidate subgraphs can be batched into a single feedback-arc computation; the authors prove that all feedback arcs can be found in linear time on tipless bidirected graphs (while the general case is matrix-multiplication hard under the k-Clique Conjecture). The same framework yields a different linear-time algorithm for superbubbles.

Significance. If the central linearity claims hold, the work resolves open problems from 2018 and supplies the first O(n) methods for detecting these bubble-like structures that correspond to genetic variation regions. The new linear-time feedback-arc primitive for tipless bidirected graphs is a strength that may be of independent interest, and the unified SPQR-tree approach demonstrates a conceptually simple way to extend the tool beyond graph drawing to other subgraph-identification tasks in computational biology.

major comments (1)

[Section presenting the linear-time feedback-arc algorithm for tipless bidirected graphs and its reduction from the SPQR/] The O(n) claim for snarls and ultrabubbles rests entirely on the new feedback-arc result for tipless bidirected graphs. The manuscript must explicitly verify that the auxiliary graph constructed from the SPQR-tree 2-separators and the subsequent DP traversals remains tipless and that the algorithm incurs no hidden super-linear cost (e.g., quadratic work in traversals or auxiliary-graph construction), given that the general feedback-arc problem is hard.

minor comments (2)

Clarify in the main text how many DP traversals are performed and what exact properties each maintains, to make the high-level description in the abstract fully traceable.
[Introduction] The 2018 papers that left the snarls and ultrabubbles problems open should be cited explicitly in the introduction for proper historical context.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for highlighting this important point regarding the explicit verification of the tipless property and linear-time bounds. We address the major comment below and have prepared revisions to strengthen the presentation.

read point-by-point responses

Referee: The O(n) claim for snarls and ultrabubbles rests entirely on the new feedback-arc result for tipless bidirected graphs. The manuscript must explicitly verify that the auxiliary graph constructed from the SPQR-tree 2-separators and the subsequent DP traversals remains tipless and that the algorithm incurs no hidden super-linear cost (e.g., quadratic work in traversals or auxiliary-graph construction), given that the general feedback-arc problem is hard.

Authors: We agree that making this verification fully explicit is valuable for rigor, particularly given the hardness result for the general case. The auxiliary graph is constructed by mapping each 2-separator from the SPQR-tree to a vertex and adding directed edges that encode the possible DP states for acyclicity; because the SPQR-tree decomposition operates exclusively on biconnected components of the input bidirected graph and the DP maintains only local separator information without introducing new degree-1 structures, the resulting auxiliary graph is tipless by construction. All traversals consist of a constant number of linear-time passes over the O(n)-size SPQR-tree, and the auxiliary graph itself has linear size, so the single feedback-arc computation incurs no super-linear overhead. To address the referee's request, we have added a new lemma (with a short proof) immediately following the description of the auxiliary-graph construction that formally establishes both the tipless property and the overall O(n) bound. This addition does not change the algorithm but improves clarity. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation composes independent linear primitives

full rationale

The paper's central claims rest on the standard linear-time SPQR-tree decomposition (a known external primitive) followed by DP traversals and a reduction to a newly proven linear-time feedback-arc algorithm on tipless bidirected graphs. No equation or step is shown to be self-definitional, no parameter is fitted and then renamed as a prediction, and no load-bearing uniqueness theorem or ansatz is imported via self-citation. The new feedback-arc result is presented as an independent algorithmic contribution whose proof does not loop back to the bubble-identification procedure. The overall O(n) bound is therefore obtained by composition rather than by construction from the target output.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard SPQR-tree theorem that encodes all 2-separators and on the new claim that feedback arcs can be found in linear time for tipless bidirected graphs. No free parameters or invented entities are introduced.

axioms (2)

standard math SPQR-tree decomposition encodes all 2-separators of a biconnected graph
Invoked as the foundation for the dynamic-programming traversals that decide which 2-separators define reportable subgraphs.
domain assumption Acyclicity of candidate subgraphs can be decided simultaneously via a single feedback-arc computation
Used to achieve overall linear time instead of testing each subgraph independently.

pith-pipeline@v0.9.0 · 5671 in / 1416 out tokens · 59245 ms · 2026-05-10T17:57:33.269476+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear
We employ the well-known SPQR-tree decomposition... acyclicity of linearly many subgraphs can be tested simultaneously via... feedback arcs... tipless bidirected graphs
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear
all feedback arcs can be computed in linear time for tipless bidirected graphs, while in general this is at least as hard as matrix multiplication

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

The Power of Graph Doubling: Computing Ultrabubbles in a Bidirected Graph by Reducing to Weak Superbubbles
cs.DS 2026-05 unverdicted novelty 7.0

Graph doubling reduces ultrabubble computation in bidirected graphs to weak superbubble detection, giving the first linear-time algorithm for the former.

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages · cited by 1 Pith paper

[1]

URLhttps://doi.org/10.1016/j.tcs.2008.09.065

doi: 10.1016/J.TCS.2008.09.065. URLhttps://doi.org/10.1016/j.tcs.2008.09.065. Harold N Gabow. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. InProc. 15th Annual ACM Symposium on Theory of Computing, pages 448–456, 1983. Michael R Garey and Robert E Tarjan. A linear-time algorithm for finding all feed...

work page doi:10.1016/j.tcs.2008.09.065 2008
[2]

PMID: 29461862

doi: 10.1089/cmb.2017.0251. PMID: 29461862. Amatur Rahman and Paul Medvedev. Assembler artifacts include misassembly because of unsafe unitigs and underassembly because of bidirected graphs.Genome Research, 32(9):1746–1753, 2022a. Amatur Rahman and Paul Medvedev. Uncovering hidden assembly artifacts: when unitigs are not safe and bidirected graphs are not...

work page doi:10.1089/cmb.2017.0251 2017