Almost Optimal Constant-Round Approximation of Dominating Set in Graph Classes with Excluded Minors

Saeed Amiri, Sebastian Siebertz

For every fixed proper minor-closed class $\mathcal{C}$ and every $\epsilon >0$, we give a deterministic LOCAL algorithm that returns a dominating set of size at most $(2a(\mathscr C)+1+ε)γ…