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
| CREATOR | Taiki Kaneda, Yasuaki Kobayashi, Hisao Tamaki |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 93327 |
| LICENSE | http://creativecommons.org/publicdomain/zero/1.0/ |
| RIGHTS | CC0 |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.17396