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

CREATORMarthe Bonamy, Cyril Gavoille, Timothé Picavet, Alexandra Wesolek
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE78 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-01091

Browse the full library · About the Tower of Babel