pith. machine review for the scientific record. sign in

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

Francisco Sena , Aleksandr Politov , Corentin Moumard , Massimo Cairo , Romeo Rizzi , Manuel C\'aceres , Sebastian Schmidt , Juha Harviainen
show 1 more author
Alexandru I. Tomescu
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
0 comments X

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 1
Figure 1. Figure 1: Examples of superbubbles (a), snarls (b), and ultrabubbles (d) in directed graphs and bidirected graphs, [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
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. 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. 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. 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. 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. 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. 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. 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. 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. 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.

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)
  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)
  1. 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.
  2. [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

  1. 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)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

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

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

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

  1. 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. [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. [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