On coarse tree decompositions and coarse balanced separators

Tara Abrishami, Jadwiga Czyżewska, Kacper Kluk, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski · 2025

Read On coarse tree decompositions and coarse balanced separators by Tara Abrishami, Jadwiga Czyżewska, Kacper Kluk, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski (2025) 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-2502-20182.txt.

Description

Tara Abrishami and co-authors ask whether a classic graph trade-off survives in a rough, coarse view of networks, in a 2025 paper. In fine graph theory, tree-likeness and the size of balanced cuts rise and fall together. Coarse theory blurs detail: bags and cuts need only be coverable by few balls of set radius.

The team proves that small coarse cuts force tree layouts whose bags are coverable by slightly more balls of the same radius. A second layout pays a bit more radius for fewer balls per bag. When the graph also has bounded doubling size, the two notions match fully in the coarse world. The results extend a workhorse tool of algorithm design to networks seen from afar.

Catalog record

CREATORTara Abrishami, Jadwiga Czyżewska, Kacper Kluk, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-20182

Browse the full library · About the Tower of Babel