Pith Number

pith:WBLK45CE

pith:2026:WBLK45CE6EGTNMJMZZ47KE6WPR

not attested not anchored not stored refs resolved

The Power of Graph Doubling: Computing Ultrabubbles in a Bidirected Graph by Reducing to Weak Superbubbles

Aleksandr Politov, Alexandru I. Tomescu, Corentin Moumard, Francisco Sena, Juha Harviainen, Sebastian Schmidt

Doubling a bidirected graph maps its ultrabubbles exactly onto weak superbubbles in the resulting directed graph.

arxiv:2605.13074 v1 · 2026-05-13 · cs.DS

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{WBLK45CE6EGTNMJMZZ47KE6WPR}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

Graph doubling maintains connectivity and allows 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.

C2weakest assumption

That the correspondence between ultrabubbles in the original bidirected graph and weak superbubbles in the doubled directed graph holds for every possible bidirected graph and that existing superbubble algorithms transfer without correctness loss.

C3one line summary

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

References

12 extracted · 12 resolved · 1 Pith anchors

[1] 14 The Power of Graph Doubling: Reducing Ultrabubbles to Weak Superbubbles 2 Ouahiba Bessouf, Abdelkader Khelladi, and Thomas Zaslavsky 2012 · doi:10.1089/cmb.2012.0021

[2] URL: https://www.biorxiv.org/content/early/2025/10/01/2025. 09.29.678807, arXiv:https://www.biorxiv.org/content/early/2025/10/01/2025.09.29. 678807.full.pdf,doi:10.1101/2025.09.29.678807. 6 Fawaz Dabb 2025 · doi:10.1101/2025.09.29.678807

[3] On the notion of balance of a signed graph.Michigan Mathematical Journal, 2(2):143–146, 1953.doi:10.1307/mmj/1028989917 1953 · doi:10.1307/mmj/1028989917

[4] The sequence read archive: a decade more of explosive growth.Nucleic Acids Research, 50(D1):D387–D390, 01 2022.doi:10.1093/nar/gkab1053 2022 · doi:10.1093/nar/gkab1053

[5] 15 20 Taku Onodera, Kunihiko Sadakane, and Tetsuo Shibuya 2013

Receipt and verification

First computed	2026-05-18T03:08:58.816495Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

b056ae7444f10d36b12cce79f513d67c7226e00742ee95090a576547b61c40c5

Aliases

arxiv: 2605.13074 · arxiv_version: 2605.13074v1 · doi: 10.48550/arxiv.2605.13074 · pith_short_12: WBLK45CE6EGT · pith_short_16: WBLK45CE6EGTNMJM · pith_short_8: WBLK45CE

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/WBLK45CE6EGTNMJMZZ47KE6WPR \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: b056ae7444f10d36b12cce79f513d67c7226e00742ee95090a576547b61c40c5

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "873162b63dee08dd8527f9a0779d0600443382127f01097c6f88f533e08cad91",
    "cross_cats_sorted": [],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.DS",
    "submitted_at": "2026-05-13T06:47:46Z",
    "title_canon_sha256": "199473e09793f356aebc14277c16b2b1c75812b3741865bb7959a07ffc462c70"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.13074",
    "kind": "arxiv",
    "version": 1
  }
}