Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors
Marthe Bonamy, Cyril Gavoille, Timothé Picavet, Alexandra Wesolek · 2025
Read Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors by Marthe Bonamy, Cyril Gavoille, Timothé Picavet, Alexandra Wesolek (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-2504-01091.txt.
Description
Marthe Bonamy, Cyril Gavoille, Timothé Picavet, and Alexandra Wesolek design a fast network algorithm in this 2025 paper. The task is the dominating set problem: pick few nodes so every node sits next to a chosen one. In distributed computing, each node decides using only local chatter, so speed and accuracy trade off.
For networks that avoid a certain dense pattern as a minor, their method finishes in a number of rounds set only by that pattern's size. Its picks stay within a fixed factor of the best possible, no matter how large the excluded pattern is. Earlier methods all lost accuracy as the pattern grew. The same approach covers the vertex cover problem, and a dimension tool drives the analysis.
Catalog record
| CREATOR | Marthe Bonamy, Cyril Gavoille, Timothé Picavet, Alexandra Wesolek |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-01091