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
| CREATOR | Tara Abrishami, Jadwiga Czyżewska, Kacper Kluk, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-20182