arXiv · Oct 7, 2026
Almost Optimal Constant-Round Approximation of Dominating Set in Graph Classes with Excluded Minors
By Saeed Amiri, Sebastian Siebertz
For every fixed proper minor-closed class mathscr C and every ε>0, we give a deterministic LOCAL algorithm that returns a dominating set of size at most (2a(mathscr C)+1+ε)γ_f(G) on every G∈mathscr C. Here a(mathscr C) is the supremum edge-to-vertex ratio in mathscr C, and γ_f(G) is the fractional domination number. The class also admits a deterministic (1+ε)-approximation for fractional dominating set and a randomized algorithm that always returns a dominating set and has expected size at most (1+ε)γ(G). In each case, the number of rounds depends only on mathscr C and ε. 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+ε)γ_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≥0, 2t-3 for K_t-minor-free graphs with 3≤ t≤9, and 2r+1 for graphs of treewidth or pathwidth at most any fixed r≥1. We also prove that, for every integer r≥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≤ t≤9. For triangle-free planar graphs, the corresponding infimum is 5.