Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors

2025/04/01 by Marthe Bonamy, Cyril Gavoille, Bonamy, Marthe +5 · 2 citations
Computer Science · #Distributed systems and fault tolerance #Complexity and Algorithms in Graphs #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2504.01091

Abstract

We show that graphs excluding K_2,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.

Cited by

• String graphs are quasi-isometric to planar graphs
• Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs

Related

• Distributed domination on sparse graph classes
• Local Approximability of Minimum Dominating Set on Planar Graphs
• A tight local algorithm for the minimum dominating set problem in\n outerplanar graphs
• Distributed distance domination in graphs with no K_2,t-minor
• Distributed Dominating Set Approximations beyond Planar Graphs