Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913833547726848 |
|---|---|
| author | Bonamy, Marthe Gavoille, Cyril Picavet, Timothé Wesolek, Alexandra |
| author_facet | Bonamy, Marthe Gavoille, Cyril Picavet, Timothé Wesolek, Alexandra |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_01091 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors Bonamy, Marthe Gavoille, Cyril Picavet, Timothé Wesolek, Alexandra Distributed, Parallel, and Cluster Computing Discrete Mathematics 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. |
| title | Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors |
| topic | Distributed, Parallel, and Cluster Computing Discrete Mathematics |
| url | https://arxiv.org/abs/2504.01091 |