Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors
Marthe Bonamy, Cyril Gavoille, Timothé Picavet, Alexandra Wesolek · 2025
We show that graphs excluding K2,t as a minor admit a f(t)-round 50-approximation deterministic distributed algorithm for Minimum Dominating Set. The result extends to Minimum Vertex Cover. Though fast and approximate distributed algorithms for such problems were already known for H-minor-free graphs, all of them have an approximation ratio depending on the size of H. To the best of our knowledge, this is the first example of a large non-trivial excluded minor leading to fast and constant-approximation distributed algorithms, where the ratio is independent of the size of H. A new key ingredient in the analysis of these distributed algorithms is the use of asymptotic dimension.