Fast and Practical Single-Exponential Algorithms for Branchwidth

Taiki Kaneda, Yasuaki Kobayashi, Hisao Tamaki · 2026

Read Fast and Practical Single-Exponential Algorithms for Branchwidth by Taiki Kaneda, Yasuaki Kobayashi, Hisao Tamaki (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-17396.txt.

Description

Kaneda, Kobayashi and Tamaki present exact single-exponential methods for branchwidth that are fast in theory and practice. A simple recurrence on vertex sets computes hypergraph branchwidth in time exponential with base four, the first single-exponential method for hypergraphs. A graph method runs in time exponential with base about 3.29, beating the prior 3.47 bound and overwhelmingly outperforming practical rivals in experiments. A second graph method is conjectured to improve the base further.

Catalog record

CREATORTaiki Kaneda, Yasuaki Kobayashi, Hisao Tamaki
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE93327
LICENSEhttp://creativecommons.org/publicdomain/zero/1.0/
RIGHTSCC0
SOURCEarXiv

Source: https://arxiv.org/abs/2605.17396

Browse the full library · About the Tower of Babel