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

Abstract

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(\mathcal{C})+1+\epsilon ){\gamma }_f(G)$ on every $G\in \mathcal{C}$. Here $a(\mathcal{C})$ is the supremum edge-to-vertex ratio in $\mathcal{C}$, and ${\gamma }_f(G)$ is the fractional domination number. The class also admits a deterministic $(1+\epsilon )$-approximation for fractional dominating set and a randomized algorithm that always returns a dominating set and has expected size at most $(1+\epsilon )\gamma (G)$. In each case, the number of rounds depends only on $\mathcal{C}$ and $\epsilon$. None of these algorithms requires the number of vertices or the maximum degree as part of the input. For planar graphs, this gives the deterministic guarantee $(7+\epsilon ){\gamma }_f(G)$. Together with the lower bound of Hilke, Lenzen and Suomela, it determines the infimum of the deterministic constant-round approximation ratios for planar minimum dominating set as $7$, settling a question that had remained open since their work. The corresponding infima, measured against the integral optimum, are $7$ for graphs of Euler genus at most any fixed $g\ge 0$, $2t-3$ for $K_t$-minor-free graphs with $3\le t\le 9$, and $2r+1$ for graphs of treewidth or pathwidth at most any fixed $r\ge 1$. We also prove that, for every integer $r\ge 1$, no deterministic constant-round LOCAL algorithm achieves an approximation ratio below $2r+1$ on the $r$-th powers of paths, even when every vertex knows the number of vertices. This gives a new proof that the limiting constants are optimal for planar graphs, graphs of bounded treewidth or pathwidth, and $K_t$-minor-free graphs with $3\le t\le 9$. For triangle-free planar graphs, the corresponding infimum is $5$.