Timothé Picavet (LaBRI)
Title: Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors
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.
The talk will be in English if there is a non-(sufficiently)-French-speaking person in the audience and in French otherwise.