← 研踪 PaperTrailarXiv:2610.38020 · v1
Random Centres and the $\varepsilon$-Dependence of Constant-Round Planar Domination
首次提交 2026-10-28 06:16
版本更新 2026-10-28 06:16
雷达观测 2026-10-30 10:23
摘要
It was recently shown (arXiv:2610.09618) that the infimum of the approximation ratios of deterministic constant-round LOCAL algorithms for minimum dominating set on planar graphs is 7. The $(7+\varepsilon)$-approximation given there runs in $T_0+O((c_0/\varepsilon)^κ)$ rounds with $κ=\ln 3/\ln(24/23)\approx 25.81$, and it is asked there whether this exponent can be substantially reduced. We replace the heaviest-edge star selection in its clustering step by a random-centre rule: every part becomes a centre independently with probability $p$, and every non-centre joins its heaviest centre neighbour. For planar graphs this gives $κ<5.89$ with $p=3/8$ (three fair coins per part and level) and $κ<6.7$ with $p=1/2$. An analysis that counts only the join edges cannot go below $5.74$. For every proper minor-closed class of density $a$, the new exponent is never worse, and with about $\frac12\log_2 a$ fair coins per part and level it is smaller by a factor that tends to $8$ as the density grows. This is optimal for the rule when $a$ is an integer and the class contains all $K_{a,n}$. The planar bounds hold verbatim on the torus, the projective plane and the Klein bottle. We then turn to the dependence on $\varepsilon$. On paths, every deterministic $r$-round algorithm for fractional domination, and every randomized one that always outputs a dominating set, has (expected) ratio at least $1+1/(r+4)$. So these approximations need $Ω(1/\varepsilon)$ rounds on every minor-closed class that contains all paths, and on paths this is tight up to an additive constant. On forests and on outerplanar graphs, with no bound on the degree, $O(1/\varepsilon)$ rounds suffice, so there the optimal number of rounds is $Θ(1/\varepsilon)$. The planar level bounds, the bounds on paths and the deterministic bound on forests are machine-checked in Lean 4 with Mathlib.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-10-28 06:16 · 最新观测版本
Random Centres and the $\varepsilon$-Dependence of Constant-Round Planar Domination
It was recently shown (arXiv:2610.09618) that the infimum of the approximation ratios of deterministic constant-round LOCAL algorithms for minimum dominating set on planar graphs is 7. The $(7+\varepsilon)$-approximation given there runs in $T_0+O((c_0/\varepsilon)^κ)$ rounds with $κ=\ln 3/\ln(24/23)\approx 25.81$, and it is asked there whether this exponent can be substantially reduced. We replace the heaviest-edge star selection in its clustering step by a random-centre rule: every part becomes a centre independently with probability $p$, and every non-centre joins its heaviest centre neighbour. For planar graphs this gives $κ<5.89$ with $p=3/8$ (three fair coins per part and level) and $κ<6.7$ with $p=1/2$. An analysis that counts only the join edges cannot go below $5.74$. For every proper minor-closed class of density $a$, the new exponent is never worse, and with about $\frac12\log_2 a$ fair coins per part and level it is smaller by a factor that tends to $8$ as the density grows. This is optimal for the rule when $a$ is an integer and the class contains all $K_{a,n}$. The planar bounds hold verbatim on the torus, the projective plane and the Klein bottle. We then turn to the dependence on $\varepsilon$. On paths, every deterministic $r$-round algorithm for fractional domination, and every randomized one that always outputs a dominating set, has (expected) ratio at least $1+1/(r+4)$. So these approximations need $Ω(1/\varepsilon)$ rounds on every minor-closed class that contains all paths, and on paths this is tight up to an additive constant. On forests and on outerplanar graphs, with no bound on the degree, $O(1/\varepsilon)$ rounds suffice, so there the optimal number of rounds is $Θ(1/\varepsilon)$. The planar level bounds, the bounds on paths and the deterministic bound on forests are machine-checked in Lean 4 with Mathlib.
查看此版本解读 →查看此版本原文 ↗