Random Centres and the $\varepsilon$-Dependence of Constant-Round Planar Domination

Random Centres and the ε-Dependence of Constant-Round Planar Domination

arXiv:2610.38020v1 [cs.DC] 27 Oct 2026

Sebastian Senge Independent Researcher Abstract 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 + ε)-approximation given there runs in T0 + O((c0 /ε)κ ) rounds with κ = ln 3/ ln(24/23) ≈ 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, a layer-cake count combined with two degree inequalities
shows that for p ≥ 21/64 each level contracts at least an expected (1−p) 3−2(1−p)3 −(1−p)6 /9 fraction of the remaining weight. With p = 3/8, which takes three fair coins per part and level, this gives κ < 5.89. With p = 1/2, that is, one fair coin per part and level as in the original algorithm, it gives κ < 6.7. An analysis that counts only these join edges cannot give an exponent below 5.74. For every proper minor-closed class of density a, a bounded out-degree orientation gives the fraction (1 − p)(1 − (1 − p)k )/k with k = ⌈a⌉. The new exponent is never worse, and with about 12 log2 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 Ka,n . A bipartite density bound or a non-integer density improves it further. In particular, the planar bounds hold verbatim on the torus, the projective plane and the Klein bottle. We then turn to the dependence on ε of the (1 + ε)-approximations. 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/ε) 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/ε) rounds suffice for both approximations, so there the optimal number of rounds is Θ(1/ε). Machine-checked in Lean 4 with Mathlib are the level bounds for every p ∈ [21/64, 1], assuming only the classical edge bounds of planar graphs; the lower bound on paths, and the upper bound for algorithms that know the length, in an explicit model of r-round algorithms; and the deterministic upper bound on forests.

1

Introduction

1.1

Dominating sets and the LOCAL model

A set D of vertices of a graph G is dominating if every vertex lies in D or has a neighbour in D. The domination number γ(G) is the minimum size of a dominatingPset, and minimum P dominating set (MDS) is the problem of finding one. The integer program min v xv subject to u∈N [v] xu ≥ 1 for every v, where N [v] is the closed neighbourhood of v and xv ∈ {0, 1}, has optimum γ(G). Relaxing it to xv ≥ 0 gives the fractional domination number γf (G) ≤ γ(G) (Figure 1). MDS is NP-hard, even on planar graphs of maximum degree 3 [7]. It is a set cover problem whose sets are the closed neighbourhoods. The greedy algorithm, which repeatedly adds a vertex 1

1 3 1 3

1 3

v

1 3

(a) a dominating set D (black), γ=2

1 3

(b) xv = 13 is optimal: γf (C5 ) = 35 < 2 = γ(C5 )

(c) what v knows after T = 1 and T = 2 rounds

Figure 1: Dominating sets and local views. In (c), the shaded hexagons are the radius-1 and radius-2 neighbourhoods of v, from which a 1-round and a 2-round LOCAL algorithm decide the output of v. that dominates the most undominated vertices, therefore achieves ratio 1 + ln(∆ + 1) on graphs of maximum degree ∆ [12], and by the standard reduction from set cover, ratio (1 − ε) ln n is NP-hard [6]. Planar graphs are much easier: the layering technique of [2] gives a polynomial-time (1 + ε)-approximation for every fixed ε > 0. In distributed computing the input graph is the network itself. Every vertex is a processor that initially knows only its identifier and its neighbours, and it decides whether it belongs to D by exchanging messages with its neighbours. Dominating sets arise in this form as cluster heads in wireless ad hoc and sensor networks, where every node needs a coordinator within one hop and no node knows the whole topology. In the LOCAL model [18], computation proceeds in synchronous rounds. Vertices have distinct identifiers from a finite range, and in a randomized algorithm every vertex has its own infinite sequence of independent fair coins. In every round each vertex sends a message of arbitrary size to each neighbour and performs arbitrary local computation. After T rounds a vertex knows exactly its radius-T neighbourhood, so a T -round algorithm is a function from radius-T neighbourhoods to outputs, and the number of rounds measures how far a vertex has to look. A constant-round algorithm is local in the strongest sense. Its running time does not depend on the size of the network, a change in the graph affects only the outputs within constant distance, and on graphs of bounded degree it yields a sublinear-time algorithm that decides the output of a single vertex by exploring its neighbourhood [22].

1.2

Standard distributed algorithms

Parallel greedy. The greedy algorithm adds one vertex at a time. Its direct distributed version lets a vertex join when its span, the number of undominated vertices in its closed neighbourhood, is the largest within distance 2, so that vertices joining in the same round do not compete for the same undominated vertices. This can still take Ω(n) rounds, for example on a caterpillar whose spine vertices have decreasing spans, because then only one vertex joins per round. The algorithm of [11] removes this bottleneck by rounding spans up to powers of 2, so that many vertices tie. In every round, the vertices whose rounded span is maximal within distance 2 become candidates, every undominated vertex counts the candidates that dominate it, and every candidate v joins with probability 1/med(v), where med(v) is the median of these counts over the undominated vertices that v dominates. The expected size of the result is O(log ∆)γ(G), and the algorithm terminates in O(log n log ∆) rounds with high probability.

2

≤r

1

≤ 2r

leader centre part

leaf part ≤ 3r + 1

Figure 2: A star of parts of radius at most r becomes one part of radius at most 3r + 1 around the leader of its centre part. LP relaxation and rounding. A fractional dominating set x becomes a dominating set in two rounds. Every vertex joins independently with Pprobability min{1, xv ln(∆ + 1)}, and every vertex that is still undominated joins as well. Since u∈N [v] xu ≥ 1, a vertex remains undominated after the first step with probability at most e− ln(∆+1) = 1/(∆ + 1). Every vertex dominates at most P ∆ + 1 vertices, so n/(∆ + 1) ≤ γf (G), and the expected size is at most ln(∆ + 1) v xv + γf (G). In [15], covering and packing LPs are solved within a factor 1 + ε in O(log n/ε) rounds. Together with a rounding of this kind, this gives an O(log ∆)-approximation of MDS in O(log n) rounds. In the same paper it was shown that approximation, even a randomized one, p every polylogarithmic
needs Ω min{log ∆/ log log ∆, log n/ log log n} rounds. So on general graphs no constant-round algorithm has a constant ratio. Planar graphs in a constant number of rounds. Sparse classes behave differently. The algorithm of [16] has two steps. First, every vertex v whose open neighbourhood cannot be dominated by six vertices other than v joins D. This needs only the radius-2 neighbourhood of v. Second, every vertex that is still undominated adds a vertex of its closed neighbourhood that dominates the most undominated vertices. The algorithm runs in six rounds and has ratio 130 on planar graphs [16]. Planarity enters only in the analysis, which shows that the first step selects fewer than 3γ(G) vertices outside a minimum dominating set. This raised the question of the best ratio that a constant number of rounds can achieve on planar graphs (Section 1.3). Cluster-and-solve. Ratios close to the optimum need a global view of larger regions. Algorithms of this kind on sparse classes [5, 17] partition the graph into clusters of small radius such that few edges run between clusters, let one vertex of every cluster collect the cluster and solve it exactly, and combine the local solutions. The quality of the result depends on the weight of the edges between clusters, and the number of rounds on the cluster radius. In [5], this gives a (1 + ε)-approximation of MDS on planar graphs in O(log∗ n) rounds. A common way to build the clusters is repeated star contraction: every cluster picks a neighbouring cluster to merge with, such that the merges form vertex-disjoint stars. Every star becomes one cluster, and parts of radius at most r give a cluster of radius at most 3r + 1 (Figure 2).

3

this work, p = 12 κ < 6.7 this work, p = 38 κ < 5.89

original κ ≈ 25.81 κ

2

3

any star contraction, per-level worst case

4

5

6

any star contraction, join edges only

7

25.81

random-centre rule, join edges only

independent coins, join edges only

random-centre rule, all edges

Figure 3: Round exponents for planar graphs. Above the axis: proved upper bounds on κ. Below the axis: the smallest exponent that the indicated kind of analysis can give (Section 4).

1.3

Optimal ratio on planar graphs

In [10] it was shown that no deterministic constant-round algorithm achieves ratio 7 − ε on planar graphs. A sequence of works improved the upper bound [9, 23], and the gap was recently closed in [1]: for every ε > 0 there is a deterministic algorithm that outputs a dominating set of size at most (7 + ε)γf (G) in
T0 + O (c0 /ε)κ rounds,

κ=

ln 3 , ln(1/q)

q =1−

1 23 = , 8a 24

where a = 3 is the edge density of planar graphs (every subgraph H has at most a|V (H)| edges) and T0 , c0 are absolute constants. The exponent κ ≈ 25.81 comes from a randomized star-contraction clustering [17, 5]: each level grows part radii by a factor of 3 and reduces the expected weight between parts by a factor q. Bringing this weight down to an ε-fraction takes L ≈ ln(1/ε)/ ln(1/q) levels, and hence radius and round number 3L ≈ (1/ε)κ . Open Problem 4 of [1] asks whether this exponent can be substantially reduced. Our result. We change only the star-selection rule of the clustering step (Section 2). For planar graphs and p ∈ [21/64, 1], the per-level
reduction factor improves from 23/24 to 1 − φ(p) with φ(p) = (1 − p) 3 − 2(1 − p)3 − (1 − p)6 /9 (Theorem 10). For a class of density a, it improves from 1 − 1/(8a) to 1 − fk (p) with fk (p) = (1 − p)(1 − (1 − p)k )/k and k = ⌈a⌉ (Theorem 4). Everything else in [1] carries over unchanged (Section 3): the radius recursion, the view radius, the derandomization and the rounding. Theorem 1. For every ε ∈ (0, 1] there is a deterministic LOCAL algorithm that returns, on every ′ planar graph G, a dominating set of size at most (7 + ε)γf (G) in T0 + O((c0 /ε)κ ) rounds, where κ′ = ln 3/ ln(2097152/1740037) < 5.89, and T0 , c0 are as in [1, Cor. 8.1]. With one fair coin per part and level, as in [1], the same holds with κ′ = ln 3/ ln(1152/977) < 6.7, and with six fair coins (p = 21/64) it holds with κ′ < 5.83. The first bound uses three fair coins per part and level (p = 3/8). The six-coin exponent is within 10−3 of the best exponent that Theorem 10 gives for any p. Figure 3 compares the exponents for p = 3/8 and p = 1/2 with the limits of Section 4. For a general proper minor-closed class of density a, the exponent ln 3/ ln(1/q) improves as in Table 1. Lemma 5 shows that the new factor is never worse.

4

a

1 [1]: q = 1 − 8a

ours, p = 21

ours, best dyadic p

improvement

1 2 3 (planar) 6 10 100

8.23 17.02 25.81 52.18 87.34 878.34

3.82 5.30 6.97 12.84 21.44 219.18

3.82 5.14 6.42 10.08 14.81 115.67

2.15× 3.31× 4.02× 5.17× 5.89× 7.59×

Table 1: Round exponent κ = ln 3/ ln(1/q) for integer density a (so k = a). The best dyadic p uses at most 8 fair coins per part and level. Our exponents are rounded up, the improvement factors down. For planar graphs, Theorem 10 improves the row a = 3 to 6.67 (p = 1/2) and 5.83 (p = 21/64). Positioning. The improvement concerns the optimal-ratio regime. The algorithm of [23] is a deterministic (8+ε)-approximation whose last phase is that of [9]. That phase reduces to maximum degree Γ = O(1/ε) by selecting vertices at a constant-factor cost, and then runs the LP algorithm of [15] in O(r2 ) rounds with r = log Γ/ log(1+ε), roughly (log(1/ε)/ε)2 . That degree reduction loses a constant factor. To reach ratio 7, the algorithm of [1] instead computes a (1 + ε)-approximation of γf on the whole graph by cluster-and-solve. Among algorithms whose number of rounds does not depend on n, it is the only one known for target ratios in (7, 8], and Theorem 1 is its fastest version. The same holds for the other guarantees of [1, Thm. 6.2] that our substitution improves for every proper minor-closed class: the deterministic (1 + ε)-approximation of γf , the randomized algorithm with expected size (1 + ε)γ, and the ratio 2a + 1 + ε. On forests and on outerplanar graphs, Theorems 19 and 20 give much faster algorithms for the first two. Reaching ratio 7 + ε in poly(1/ε) rounds with an exponent close to 2 remains open (Section 7). The dependence on ε. Open Problem 3 of [1] asks for the optimal dependence on ε of the deterministic (1 + ε)-approximation of γf and of the randomized algorithm with expected size (1 + ε)γ. On paths, both need at least 1/ε − 4 rounds (Theorem 17), so Ω(1/ε) rounds are necessary on every minor-closed class that contains all paths. On forests (Theorem 19) and on outerplanar graphs of arbitrary maximum degree (Theorem 20), both run in O(1/ε) rounds, so the answer there is Θ(1/ε). The algorithms average the optimal solutions of overlapping windows of radius O(1/ε). On outerplanar graphs the windows live in a covering graph in which every long face unrolls into an infinite path. Formal verification. The bounds for one level of the rule (Section 2), in the planar case for every p ∈ [21/64, 1] and on the surfaces of Table 2, the resulting exponents and their limit as the density grows (Proposition 6), and Theorem 17 are checked in Lean 4 with Mathlib (Section 6). The direction of the orientation theorem of [8] that we use and Lemmas 8 and 11 are checked as well. Hence the level bounds assume only the classical edge bounds of planar graphs from Euler’s formula: at most 3n edges, and at most 2n if the graph is bipartite. Theorem 17 is checked in a model of r-round algorithms on paths, for deterministic and for randomized algorithms, and so is the upper bound 1 + 2/(2r + 3) on paths for algorithms that know the length. The integration into the algorithm of [1] is proved on paper, except for the step from the per-level factor to the exponent. The deterministic part of Theorem 19 is checked as well, with its explicit constants. Its randomized part and Theorem 20 are proved on paper, and we check their constructions numerically.

5

2

1 1

2

3

2 3

1 1

2 3

1

2 1

(a) parts whose coins come up heads become centres (black)

1

2 4

1

2

1

3

1

2 4

1

2

3

3

2

2

3

2

1

1

(b) every other part joins its heaviest centre neighbour

(c) two new parts; the weight between parts drops from 28 to 10

Figure 4: One level of the random-centre rule on a quotient Q of total weight 28. The join edges (bold in (b)) carry weight 13. The two edges between leaves of the same star, of weights 2 and 3, become internal as well. For Theorem 20, Lean checks only the steps that do not depend on the graph class: the packing bound, the repair and the averaging over windows.

2

One level of random-centre contraction

Let Q be a finite simple graph with edge weights w : E(Q) → R≥0 and distinct identifiers. For C ⊆ V (Q), a vertex P ∈ / C with a neighbour in C joins a neighbour c(P ) ∈ C that maximizes w(P P c(P )), breaking ties by identifier. The join edges are the edges P c(P ), and the gain is gain(C) = P ∈C / maxX∈C∩N (P ) w(P X), with max ∅ = 0. Figure 4 shows an example. Lemma 2. Distinct joining vertices have distinct join edges, so gain(C) is the total weight of a set of edges. Contracting each centre together with the vertices that joined it yields vertex-disjoint stars, and every join edge becomes internal. Proof. A join edge P c(P ) has exactly one endpoint outside C, namely P . Hence P c(P ) = P ′ c(P ′ ) forces P = P ′ . Centres do not join, and every non-centre joins at most one centre. For a finite set A let CA ⊆ A contain each element independently with probability p. Write s = 1 − p and g(m) = 1 − sm . Lemma 3 (vertex lemma). For p ∈ [0, 1] and weights w : A → R≥0 , h i X |A| · E max w(x) ≥ g(|A|) w(x). x∈CA

x∈A

Proof. We use induction on n + 1 = |A|; P the case A = ∅ is trivial. Let y ∈ A have maximum weight, and put A′ = A \ {y}, W ′ = x∈A′ w(x) and E ′ = E[maxx∈CA′ w(x)]. Conditioning on whether y ∈ CA gives E[maxCA w] = sE ′ + pw(y), because y is the heaviest centre whenever it is a centre. The induction hypothesis gives nE ′ ≥ g(n)W ′ , and the choice of y gives W ′ ≤ nw(y). Using g(n + 1) = 1 − s sn , a direct expansion verifies h

i


n (n+1) sE ′ +pw(y) −g(n+1) w(y)+W ′ = (n+1)s nE ′ −g(n)W ′ + nw(y)−W ′ np−s g(n) . Both terms are non-negative. For the second, Bernoulli’s inequality gives g(n) ≤ np, and s ≤ 1. For n ≥ 1 we divide by n. For n = 0 we have W ′ = 0, and the claim reads pw(y) ≤ sE ′ +pw(y). 6

Since g is concave with g(0) = 0, the ratio g(m)/m is non-increasing. Hence g(m)/m ≥ g(k)/k for 1 ≤ m ≤ k. Theorem 4. Suppose the edges of Q admit an orientation in which every vertex has out-degree at most k ≥ 1. If every vertex of Q is in C independently with probability p ∈ [0, 1], then
(1 − p) 1 − (1 − p)k E[gain(C)] ≥ fk (p) w(Q), fk (p) = . k P P Proof. Let O(P ) be the out-neighbourhood of P , so w(Q) = P X∈O(P ) w(P X). Fix P . Then maxX∈C∩N (P ) w(P X) ≥ maxX∈C∩O(P ) w(P X). The event P ∈ / C is independent of C ∩ O(P ), because P ∈ / O(P ). If O(P ) = ∅, the sum below is empty. Otherwise, by Lemma 3 applied to A = O(P ) and by the monotonicity of g(m)/m, h E [P ∈ / C]

max

w(P X)

i

≥ (1 − p)

X∈C∩N (P )

g(|O(P )|) |O(P )|

X X∈O(P )

w(P X) ≥ fk (p)

X

w(P X).

X∈O(P )

Summing over P proves the claim. By [8], a graph has an orientation with out-degree at most k if and only if every subgraph H satisfies |E(H)| ≤ k|V (H)|. A graph in a class of density a therefore admits such an orientation with k = ⌈a⌉. For planar graphs k = 3. Over p ∈ [0, 1], f3 is maximized at p = 1 − 4−1/3 ≈ 0.370. The dyadic choice p = 3/8 (three fair coins) gives f3 (3/8) = 1935/12288 ≈ 0.15747, and f3 (p) ≤ 63/400 for every p, so the loss is below 3 · 10−5 . Lemma 5. For every a ≥ 1/2, f⌈a⌉ (1/2) ≥ 1/(8a). Proof. Let k = ⌈a⌉ ≥ 1. Then fk (1/2) = (1 − 2−k )/(2k) ≥ 1/(4k), and k ≤ 2a: if k = 1 this follows from a ≥ 1/2, and if k ≥ 2 from k < a + 1 ≤ 2a. As the density grows, the improvement approaches a factor of 8, provided that p shrinks at the right speed.

1 Proposition 6. Let κAS (a) = ln 3/ ln 1/(1 − 8a ) and κ(a, p) = ln 3/ ln 1/(1 − f⌈a⌉ (p)) . If p = p(a) ∈ [0, 1] satisfies p → 0 and ap → ∞ as a → ∞, then κAS (a)/κ(a, p(a)) → 8. This holds for p = 2−j with j = ⌊ 21 ⌊log2 ⌈a⌉⌋⌋, that is, with j fair coins per part and level. For a fixed p ∈ (0, 1], the ratio tends to 8(1 − p). Proof. Let k = ⌈a⌉, y = 1/(8a) and f = fk (p). For 0 ≤ x < 1 we have x ≤ ln(1/(1 − x)) ≤ x/(1 − x), so the ratio ln(1/(1
− f ))/ ln(1/(1 − y)) lies between 8af (1 − y) and 8af /(1 − f ). Here 8af = 8 ka (1 − p) 1 − (1 − p)k , a/k → 1, and (1 − p)k ≤ e−pk ≤ e−ap → 0. Hence 8af → 8, and f = 8af · y → 0, so both bounds tend to 8. For a fixed p, (1 − p)k → 0 because k → ∞, and 8af → 8(1 − p). For the dyadic choice, 4j ≤ k < 4j+1 gives p2 < 4/a and (ap)2 ≥ a2 /(a + 1) ≥ a/2 for a ≥ 1.

2.1

A sharper count for planar graphs

Theorem 4 charges every edge to one endpoint only. For planar quotients we count every edge at both endpoints. For τ > 0 let Qτ be the spanning subgraph of the edges of weight at least τ , and let dτ (P ) be the degree of P in Qτ .

7

Lemma 7 (layer cake). If every vertex of Q is in C independently with probability p, then Z ∞X E[gain(C)] = s g(dτ (P )) dτ. 0

P

R∞ Proof. For fixed P , [P ∈ / C] maxX∈C∩N (P ) w(P X) = 0 [P ∈ / C] [C ∩ NQτ (P ) ̸= ∅] dτ . The event P ∈ / C has probability s and is independent of C ∩ N (P ), and Pr[C ∩ NQτ (P ) ̸= ∅] = g(dτ (P )). Take expectations, exchange them with the integral (the integrand is bounded and vanishes for τ > max w), and sum over P . Lemma 8. Every simple planar graph with degrees dv and n′ non-isolated vertices satisfies X X (A) |E| ≤ min(dv , 3), (B) 2|E| ≤ min(dv , 6) + 2n′ . v

v

Proof. (A) Let H = {v : dv ≥ 3}. At most 3|H| edges lie inside H, because every simple planar graph on m P vertices has P at most 3m edges. Every other edge has an endpoint v ∈ / H,Pand there are at most v∈H d = min(d , 3) of them. (B) Let H = {v : d ≥ 6}. Then v v / v ∈H / v∈H dv = P P v P 2|E(H)|+|E(H, H̄)| ≤ 6|H|+|E(H, H̄)|, so 2|E| = v min(dv , 6)+ v∈H (dv −6) ≤ v min(dv , 6)+ |E(H, H̄)|. The edges between H and H̄ form a simple bipartite planar graph on non-isolated vertices, which has at most 2n′ edges.
Lemma 9 (degree inequality). Let P p ∈ [21/64, 1] and c(s) = 2g(3) + g(6) /9 = (3 − 2s3 − s6 )/9. Every simple planar graph satisfies v g(dv ) ≥ c(s) |E|. Proof. Put β = (g(6) − g(3))/3 and α = (8g(3) − 5g(6))/9, so that α + 2β = c(s). Here β ≥ 0 because g is increasing, and α ≥ 0 because 9α = (1 − s3 )(3 − 5s3 ) and s3 ≤ 3/5. We claim that for every integer d ≥ 0,
g(d) ≥ α min(d, 3) + β min(d, 6) + 2[d ≥ 1] . Equality holds at d ∈ {0, 3, 6}. For d > 6 the right side is constant and g is increasing. For d ∈ {4, 5} the right side is the chord of the concave function g between 3 and 6. For d ∈ {1, 2} the claim reads 9g(1) ≥ 4g(6)−g(3) and 9g(2) ≥ 4g(3)+2g(6), that is, h1 (s) = 6−9s−s3 +4s6 ≥ 0 and h2 (s) = 3 − 9s2 + 4s3 + 2s6 ≥ 0. Both polynomials are decreasing on [0, 43/64] (h′1 ≤ −9 + 24s5 < 0, and h′2 = 6s(2s + 2s4 − 3) < 0), and h1 (43/64) P > 0.017, h2 (43/64) > 0.33. Summing the claim over all vertices and applying Lemma 8 gives v g(dv ) ≥ α|E| + 2β|E|. Theorem 10. Let Q be a simple planar graph. If every vertex of Q is in C independently with probability p ∈ [21/64, 1], then
(1 − p) 3 − 2(1 − p)3 − (1 − p)6 E[gain(C)] ≥ φ(p) w(Q), φ(p) = . 9 R∞ Proof. Every Qτ is a simple planar graph, and 0 |E(Qτ )| dτ = w(Q). Apply Lemma 9 to each Qτ inside Lemma 7. The values are φ(3/8) = 357115/2097152 ≈ 0.17029, φ(1/2) = 175/1152 ≈ 0.15191 and φ(21/64) ≈ 0.17181, compared with f3 (3/8) ≈ 0.15747 and f3 (1/2) = 7/48. Over p ∈ [0, 1], φ √ is maximized at s3 = ( 37 − 4)/7, that is, p ≈ 0.3324, where φ ≈ 0.17182. The count P is tight for its inputs. Over degree sequences that satisfy only (A) and (B), the infimum of v g(dv )/|E| is c(s). It is approached by two vertices of degree 3 per vertex of degree 6, together with a vanishing number of hubs incident to two thirds of the edges. The certificate above is the dual solution of this linear program. 8

2.2

Other classes

Planarity enters Theorem 10 only through Lemma 8, and its proof uses two density bounds. Let C be a class of graphs that is closed under taking subgraphs, and let a, b > 0 be such that every H ∈ C has |E(H)| ≤ a|V (H)| and every bipartite H ∈ C has |E(H)| ≤ b|V (H)|. Planar graphs have a = 3 and b = 2. Lemma 11. Every H ∈ C with degrees dv and n′ non-isolated vertices satisfies, for all reals t ≥ a and u ≥ 2a, X X min(dv , u) + b n′ . min(dv , t), (Bu ) 2|E| ≤ (At ) |E| ≤ v

v

P

Proof. As for Lemma 8. At most P a|Ht | ≤ v∈Ht min(dv , t) edges lie inside Ht = {v : dv ≥ t}. For Hu = {v : dv ≥ u} we have v∈Hu dv ≤ 2a|Hu | + |E(Hu , H̄u )| ≤ u|Hu | + |E(Hu , H̄u )|, and the edges between Hu and H̄u form a bipartite graph in C on at most n′ non-isolated vertices. Theorem 12. Let s = 1 − p. Let α1 , . . . , αm , β1 , . . . , βℓ ≥ 0 and ti ≥ a, uj ≥ 2a satisfy, for every integer d ≥ 0, X X
g(d) ≥ αi min(d, ti ) + βj min(d, uj ) + b [d ≥ 1] . i

j

If every vertex of aPsimple graph P Q ∈ C is in C independently with probability p, then E[gain(C)] ≥ s c w(Q) with c = i αi + 2 j βj . Proof. Every Qτ lies in C. Summing the certificate over its vertices and applying Lemma 11 gives P P g(dτ (P )) ≥ c |E(Qτ )|. Integrate as in Theorem 10. Lemma 9 is the case t = 3, u = 6, b = 2. Without any bipartite bound, a single threshold already improves Theorem 4 when a is not an integer. Corollary 13. Let a ≥ 1 and ca (s) = min{g(⌊a⌋)/⌊a⌋, g(⌈a⌉)/a}. Then E[gain(C)] ≥ s ca (s) w(Q) for every simple Q ∈ C. For integer a this is fa (p). For non-integer a and 0 < s < 1 it is larger than f⌈a⌉ (p). Proof. Take t = a and α = ca (s) in Theorem 12. For d ≤ ⌊a⌋ we have αd ≤ g(d), because g(d)/d is non-increasing. For d ≥ ⌈a⌉ we have αa ≤ g(⌈a⌉) ≤ g(d). For non-integer a, both terms of the minimum exceed g(⌈a⌉)/⌈a⌉, the first by strict concavity of g. For integer densities, no improvement over Theorem 4 is possible without excluding more structure. Proposition 14. Let k ≥ 1. For every p, on Kk,n with unit weights, the expected fraction of the edges that become internal is at most fk (p) + 1/n. Hence, on every class that contains Kk,n for all n, no analysis of the random-centre rule gives a per-level fraction above maxp fk (p). Such classes include the graphs of treewidth at most k and, for k ≤ 5, the Kk+2 -minor-free graphs, both of density k [19]. Proof. The leaves of a star in a bipartite graph lie on the side opposite to its centre and are pairwise non-adjacent, so the internal edges are exactly the join edges. A vertex of degree k has a join edge exactly when it is not a centre and one of the k hubs is, which has probability s(1 − sk ). The hubs have at most k join edges, and |E| = kn. Finally, Kk,n has treewidth k, and Kk+2 has treewidth k + 1. 9

By Proposition 14, Theorem 4 is optimal for every integer row of Table 1 whose class contains all Ka,n . In particular, K5 -minor-free graphs have the same density as planar graphs, but the rule cannot beat the exponent 6.41 on them. The improvement to 5.83 for planar graphs comes from excluding K3,n , which is what the bipartite bound b = 2 records. Surfaces. A simple graph with n ≥ 3 vertices that embeds in a surface of Euler genus e has at most 3n − 6 + 3e edges, and at most 2n − 4 + 2e if it is bipartite. For e ≤ 2 (the sphere, projective plane, torus and Klein bottle) this gives a = 3 and b = 2. Hence Theorem 10 and all its numbers, including the exponent 5.89 for p = 3/8, hold for graphs on these surfaces. For larger e we use ae = max{3, maxn min{(n − 1)/2, 3 − (6 − 3e)/n}} and be = max{2, maxn min{⌊n2 /4⌋/n, 2 − (4 − 2e)/n}}. Table 2 lists the resulting exponents. Every entry of the last column uses a certificate for Theorem 12 that was found by linear programming (sim/tight/surfaces.py). The certificates and the exponent bounds are checked in Lean (Section 6). Euler genus e

ae

be

[1]

Thm. 4

Cor. 13

Thm. 12

0, 1, 2 3 4 6 8 12 20 100 200

3 27/8 11/3 21/5 51/11 11/2 33/5 27/2 37/2

2 20/9 12/5 30/11 3 24/7 70/17 8 11

25.81 29.11 31.67 36.36 40.20 47.79 57.46 118.10 162.04

6.42 7.66 7.66 8.88 8.88 10.08 11.28 19.45 25.18

6.42 6.42 6.97 7.66 8.19 9.19 10.60 18.73 24.50

5.83 6.13 6.55 7.19 7.75 8.76 10.10 18.17 23.93

Table 2: Round exponents ln 3/ ln(1/q) for graphs on a surface of Euler genus e (for an orientable surface, e is twice the genus), at the best p with at most 8 fair coins. Our exponents are rounded up.

3

Plugging the rule into the clustering algorithm

We refer to the numbering of [1] and recall its notation. The clustering acts on a weighted graph H of the class C and maintains partitions P0 , P1 , . . . of V (H) into connected parts, each with a leader. For a partition P, cutw (P) is the total weight of the edges of H between different parts, and H/P is the quotient whose vertices are the parts and whose edge weights add up the weights between two parts. The σ-algebra Ft−1 is generated by the coins of the levels before t, and TC is as in [1, Thm. 5.4]. In Algorithm 1 (RandomCluster), we replace lines 6–13 at level t as follows. Every part P ∈ Pt−1 reads b level-t coins of its leader and becomes a centre with probability p = m/2b . Every non-centre part with a centre neighbour in the quotient Q = H/Pt−1 joins its heaviest centre neighbour, with ties broken by identifier. Every centre absorbs the parts that joined it, and every other part is unchanged. • Lemma 4.1 (partition, radius rt = 3rt−1 + 1, quotient in C, dependence on coins). The proof only uses that the new parts are vertex-disjoint stars whose leaves are adjacent to their centre in Q, which holds by Lemma 2.

10

• Lemmas 4.2 and 4.3. Fix the coins of levels < t. Then Q is fixed and lies in C, so it is asparse and has an orientation with out-degree at most ⌈a⌉. The centre events are independent, because distinct parts have distinct leaders. By Lemma 2 every join edge becomes internal, so cutw (Pt ) ≤ w(Q) − gain(C). Theorem 4 gives E[cutw (Pt ) | Ft−1 ] ≤ (1 − f⌈a⌉ (p)) cutw (Pt−1 ). This replaces Lemma 4.3 with q ′ = 1 − f⌈a⌉ (p), and Corollary 4.4 follows verbatim. For planar graphs, Q is a minor of a planar graph and has no parallel edges, so Theorem 10 gives q ′ = 1 − φ(p) instead, and for the classes of Section 2.2 Theorem 12 gives q ′ = 1 − sc. Lemma 4.2 is no longer needed. • Lemma 4.5 (view radius ρt = 2(3t − 1)). Let P = Pt−1 (y). The new part of y is determined by the centre status of P , its quotient neighbours C and their quotient neighbours R ⊆ BH (y, 6r + 2), together with the join choice c(R) of each such R. The choice c(R) depends on the quotient edges at R and on the coins of the parts meeting BH (y, 6r + 3). The proof in [1] shows that the ρt -view of y reveals all of these parts and their level-t coins. Hence ρt is unchanged. • Theorem 5.4. The bound TC + 9 · 3L on the number of rounds is unchanged. The algorithm uses bL instead of L fair coins per vertex, and the factor q becomes q ′ in both expectation bounds. • Theorem 6.1 (the derandomization of [13]) requires only a prescribed finite number of fair coins per vertex, which still holds. • Theorem 6.2 and Corollary 8.1 hold with q ′ in place of q. For planar graphs, p = 3/8 gives q ′ = 1740037/2097152, p = 1/2 gives q ′ = 977/1152, and p = 21/64 gives q ′ = 3642429005643/242 . This proves Theorem 1. The same substitution improves the randomized (1 + ε)-approximation and the deterministic fractional (1 + ε)-approximation of [1, Thm. 6.2] for every proper minor-closed class.

4

Limits of the approach

Theorem 10 bounds only the join edges, and this P cannot be pushed much further. For unit weights, Lemma 7 gives the exact value E[gain]/w = s v g(dv )/|E|. On the Apollonian network obtained from K4 by inserting a vertex into every face ten times (118100 vertices, script apo.py), this value is at most 0.17402 for every p (the maximum is at p ≈ 0.320), and it equals 0.17161 at p = 3/8, against φ(3/8) = 0.17029. Deeper networks lower these values slightly. Hence no lower bound on the expected gain of the rule, for any p, exceeds 0.17402, and the exponent of any analysis that counts only join edges is at least 5.74. Theorem 10 gives 5.83. Counting the edges between leaves of the same star helps only on graphs with triangles. Proposition 14 with k = 2 bounds the rule itself, with every internal edge counted: planar graphs contain all√K2,n , so no analysis of the random-centre rule yields a per-level fraction above maxp f2 (p) = 1/(3 3) ≈ 0.1925 on planar graphs, that is, an exponent below 5.13. No star contraction of the square grid contracts more than a 2/5 + o(1) fraction of its edges. The grid is triangle-free, so a star with ℓ leaves internalizes exactly ℓ edges. Each centre has at most 4 leaves, so at most 4n/5 edges become internal. Any analysis that bounds every level by a uniform worst-case fraction, with radius growth r 7→ 3r + 1, therefore cannot give an exponent below ln 3/ ln(5/3) ≈ 2.15. The two remaining propositions bound every analysis that counts only join edges, as ours does. 11

Proposition 15. For every even k ≥ 2 there is a triangulation G with n = 4k vertices and γ(G) = n/4. In every partition of G into stars, at most 3n/4 edges are join edges. Hence, for any one-level star contraction, an analysis that counts only join edges gives at most a 3n/(4(3n − 6)) → 1/4 fraction per level, and an exponent of at least ln 3/ ln(4/3) ≈ 3.819. Proof. Let H consist of k nested triangles ai bi ci , 0 ≤ i < k, where consecutive triangles are joined by the six edges ai bi+1 , ai ci+1 , bi ai+1 , bi ci+1 , ci ai+1 , ci bi+1 . For even i < k, the faces ai bi ci+1 and ai+1 bi+1 ci lie in the band between the triangles i and i + 1. These k faces are pairwise disjoint and cover V (H). Insert a new vertex into each of them. The result G is a triangulation with 3k + k = n vertices. The closed neighbourhoods of the inserted vertices partition V (G), so γ(G) ≥ k, and the inserted vertices form a dominating set. In a partition into stars, the centres and the singleton parts dominate G, so there are at least γ(G) parts. Every vertex that is not a centre or a singleton has exactly one join edge, so there are at most n − γ(G) = 3n/4 join edges, while |E(G)| = 3n − 6. It was conjectured in [20] that every sufficiently large triangulation satisfies γ ≤ n/4. If the conjecture holds, then Proposition 15 is the best such bound for triangulations. Proposition 16. Consider any rule in which every part becomes a centre independently with a probability that depends only on its weighted radius-r neighbourhood, without identifiers, and every non-centre joins a centre neighbour. On the m × m triangular grid with unit weights, the expected number of join edges is at most m2 maxs s(1 − s6 ) + O(rm). Hence an analysis of such a rule that counts only join edges gives at most 2 · 7−7/6 + o(1) ≈ 0.2066 per level, and an exponent of at least 4.74. Proof. All vertices at distance more than r + 1 from the boundary have the same probability p, and so do their six neighbours, because their neighbourhoods are isomorphic. Such a vertex has a join edge with probability s(1 − s6 ), where s = 1 − p. Every vertex has at most one join edge, at most O(rm) vertices lie near the boundary, and the grid has 3m2 − O(m) edges. The maximum of s(1 − s6 )/3 is attained at s = 7−1/6 .

5

The dependence on ε

The deterministic (1 + ε)-approximation of γf and the randomized algorithm with expected size (1+ε)γ run in (c0 /ε)κ rounds, both in [1] and with the rule of Section 2. Open Problem 3 of [1] asks for the optimal dependence on ε. For integral solutions on general graphs, a (1 + ε)-approximation of γ needs Ω(log n/ε) rounds [4]. The hard graphs lie in no proper minor-closed class, since on every such class f (ε) rounds suffice [1].

5.1

A lower bound on paths

Paths give a lower bound that is linear in 1/ε. We let a vertex learn in r rounds its radius-r ball together with all identifiers and degrees in it. This only strengthens the algorithm. Theorem 17. Let r ≥ 0 and L = 2r + 6 + (r mod 3). Let A be an r-round LOCAL algorithm that is either deterministic and outputs a fractional dominating set, or randomized and always outputs a dominating set. Then for some identifier assignment on the path PL , the (expected) size of the output is at least γ(PL ) + 2/3 = (1 + 2/L)γf (PL ). This holds even if A knows the graph. Consequently, every r-round algorithm of either kind has ratio at least 1 + 1/(r + 4) on paths, and a (1 + ε)-approximation needs at least 1/ε − 4 rounds.

12

Proof. Let R = r + 1 and M = L − 2R = 4 + (r mod 3), and number the vertices 0, . . . , L − 1. Draw the identifiers as a uniformly random injection into the finite identifier space, independently of the coins of A, and let xv be the P expected value of the output at v. Every outcome is a fractional dominating set, so x is one, and v xv is the average of the (expected) output size over the identifier assignments. If an isomorphism between radius-r balls that preserves the degrees in PL maps u to v, then xu = xv , because the identifiers on the two balls have the same distribution. Hence xv = xL−1−v for all v, and all M middle vertices R ≤ v < R + M have the same value µ: their balls are paths with 2r + 1 vertices of degree 2. Since M ≥ 3, the closed neighbourhood of R + 1 consists of middle vertices, so µ ≥ 1/3. Choose k ∈ {0, 1, 2} and t ≥ 0 with R + k = 3t + 2. The closed neighbourhoods of the vertices 0, 3, . . . , 3t are disjoint. Their P union {0, . . . , R + k − 1} consists of the left part {0, . . . , R − 1} and k middle vertices. Hence v<R xv + kµ ≥ t + 1 = (R + k + 1)/3. By the symmetry, and since M − 2k ≥ 0 and µ ≥ 1/3, X v

xv = 2

X v<R

xv + M µ ≥

2(R + k + 1) 2R + M + 2 L+2 + (M − 2k)µ ≥ = . 3 3 3

Finally 3 | L. The vertices 1, 4, . . . , L−2 dominate PL , and their closed neighbourhoods are disjoint, so γ(PL ) = γf (PL ) = L/3. The ratio bound follows from L ≤ 2r + 8. The bound holds whether or not the algorithm uses identifiers or knows n. The only obstruction is that the middle vertices cannot see the ends. The bound is close to exact. Every fractional dominating set of Pℓ has weight at least ⌈ℓ/3⌉. On Pℓ with ℓ ≥ 2r + 3, put xv = 2/3 at the two ends and xv = 1/3 at the other vertices. This is a fractional dominating set of weight (ℓ + 2)/3 ≤ (1 + 2/ℓ)⌈ℓ/3⌉, and every vertex knows its value from its own degree. On a shorter path every vertex sees the nearer end within distance r. If it also knows ℓ, it can output the average of a fixed minimum dominating set and its mirror image, which has weight ⌈ℓ/3⌉. Hence for every r ≥ 0 an algorithm that knows the length has ratio at most 1 + 2/(2r + 3), and on paths the smallest number of rounds for ratio 1 + ε, with 0 < ε ≤ 1, lies between 1/ε − 4 and 1/ε − 1/2. For r ≤ 15 we computed the exact optimal ratios. They are 1 + 2/L for algorithms that know the length. For algorithms that do not, with identifiers drawn independently of the length, they are 1 + 1/(r + 2) if r ̸≡ 2 and 1 + 1/(r + 3/2) if r ≡ 2 (mod 3) (script path sym.py). Theorem 17 does not cover deterministic algorithms that output dominating sets. In a constant number of rounds, they cannot beat ratio 3 on paths [1, Thm. 8.7]. Corollary 18. Let C be a minor-closed class. If C excludes some path, a minimum dominating set can be computed deterministically in a constant number of rounds. Otherwise, a deterministic (1 + ε)-approximation of γf on C, or a randomized algorithm with expected size (1 + ε)γ, needs at least 1/ε − 4 rounds. For planar graphs, the optimal number of rounds lies between 1/ε − 4 and O((c0 /ε)5.83 ). Proof. If Pk ∈ / C, every path in a graph of C has fewer than k vertices, so every component has diameter less than k. In k rounds every vertex sees its component, including all identifiers, and all vertices of a component agree on its lexicographically first minimum dominating set. Otherwise C contains all paths, since it is closed under subgraphs, and Theorem 17 applies. The upper bound for planar graphs is the six-coin exponent of Theorem 1, applied to the two guarantees of [1, Thm. 6.2] named above (Section 3).

13

5.2

Forests: the lower bound is tight

For forests, which have density a = 1, Table 1 gives (c0 /ε)3.82 rounds. We show that O(1/ε) rounds suffice, even with unbounded degrees. Theorem 19. There is a constant C such that for every ε ∈ (0, 1] the following hold. A deterministic LOCAL algorithm computes, on every forest G, a fractional dominating set of weight at most (1 + ε)γf (G) in C/ε rounds. A randomized LOCAL algorithm always outputs a dominating set of expected size at most (1 + ε)γ(G) in C/ε rounds. With Theorem 17, the optimal number of rounds on forests is Θ(1/ε), both for the deterministic fractional and for the randomized (1 + ε)-approximation. Proof. Repair. For U ⊆ V let opt(U ) be the smallest weight of an x ≥ 0 supported on U with x(N [u]) ≥ 1 for all u ∈ U . Let B ⊆ U meet N [u] for every u ∈ U with a neighbour outside U . For every fractional dominating set y of G, opt(U ) ≤ y(U ) + |B|.

(1)

Indeed, y on U plus weight 1 on B is feasible. The integral version of (1), for dominating sets, holds in the same way. Core and hairs. Let F be a forest and R ≥ 1. For an edge vw of F , let h(v, w) be the largest distance from v to a vertex of the component of F − v that contains w. The core K consists of the vertices v with h(v, w) ≥ R for at least two neighbours w. (a) K meets every component of F in a connected set. Let v, v ′ ∈ K and let z lie on the path between them. One of the two high branches of v avoids z, so the branch of z towards v has height at least R, and likewise towards v ′ . (b) Every vertex outside K in a component that meets K has distance at most R to K. Let u0 , . . . , uk be a shortest path from u0 ∈ / K to uk ∈ K. The branch of ui towards u0 has height at least i. The branch towards uk has height at least R, because it contains a high branch of uk that avoids uk−1 . So ui ∈ K for R ≤ i ≤ k, and minimality gives k ≤ R. Let a(u) be the nearest core vertex, and let hair(c) = {c} ∪ a−1 (c); by (a), a(u) is unique. Every neighbour w of a vertex u ∈ hair(c) \ {c} lies in hair(c): if w ∈ K then a(u) = w, and otherwise the path from one of u, w to K passes through the other. (c) Components of F that miss K have diameter less than 2R. On a path of length at least 2R, the vertex at distance R from one end would lie in K. (d) A core vertex v with at most one core neighbour has a path v, x1 , . . . , xR with x1 , . . . , xR ∈ hair(v). One of the high branches of v starts at a vertex outside K. By (a), this branch contains no core vertex, so it lies in hair(v), and it contains a vertex at distance R from v. Call a core vertex a branch vertex if it has no core neighbour or at least three. The other core vertices induce paths, the core paths. Let L be the number of core vertices with at most one core neighbour, and let dK be the degree in F [K]. Every core vertex v satisfies [v branch] + 2 ≤ dK (v) + 3 [dK (v) ≤ 1],

[v branch] dK (v) + 6 ≤ 3dK (v) + 6 [dK (v) ≤ 1], P as one checks for dK (v) = 0, 1, 2 and dK (v) ≥ 3. Since F [K] P is a forest, v∈K dK (v) ≤ 2|K|. Summing over K, there are at most 3L branch vertices, and b dK (b) ≤ 6L over the branch vertices b. 14

Deterministic version. Apply this to F = G, and let P be the set of vertices of the core paths. For u ∈ P and 0 ≤ k ≤ R, let P (u, k) be the set of vertices of the core path of u at distance at most k from u, and let s(u) S ∈ {0, 1, 2} be 2 minus the number of neighbours of u on its core path. For X ⊆ K let hair(X) = c∈X hair(c). The windows are: • hair(P (u, R)) for every u ∈ P , with weight 1/(2R + 1); • hair(P (e, R − t)) for every e ∈ P and 1 ≤ t ≤ R, with weight s(e)/(2R + 1); • hair(b) for every branch vertex b, with weight 1; • every component of G that misses K, with weight 1. On a core path p1 . . . pm , the windows of the first two kinds are the hairs of the sets {pj : |j −i| ≤ R} for 1 − R ≤ i ≤ m + R, each with weight 1/(2R + 1). Those with i ≤ 0 are the windows at e = p1 with t = 1 − i, and those with i > m are the windows at e = pm with t = i − m; if m = 1, then s(p1 ) = 2 accounts for both. So every vertex of P lies in windows of total weight exactly 1, and by (b) so does every vertex of its hair. A vertex of the hair of a branch vertex lies only in that window, and a vertex of a component that misses K only in that component. So every vertex lies in windows of total weight exactly 1. Let ∂U be the set of vertices of U with a neighbour outside U . By (b), the neighbours of a vertex of hair(c) \ {c} lie in hair(c), and so does every neighbour of c outside K. Hence a vertex of ∂ hair(X) lies in X and has a core neighbour outside X. For X = P (u, k), it is one of the at most two vertices at distance exactly k from u, or it lies in the set A of vertices of P with a branch neighbour. For X = {b} it is b, and the components have no boundary. Each vertex of A lies in windows of the first two kindsPof total weight 1, and all these windows together have weight (|P | + RS)/(2R + 1), where S = e∈P s(e). So X

wt(U ) |∂U | ≤ |A| +

U

2(|P | + RS) |P | + 3L ≤ |A| + + S + 3L. 2R + 1 R

Every vertex of A is an end of a core edge at a branch vertex, so |A| ≤ 6L. The number of neighbours of e ∈ P on its core path is dK (e) minus its number of branch neighbours. So s(e) is [dK (e) = 1] plus the number of branch neighbours of e, and S ≤ L + 6L = 7L. Now let y be a fractional dominating set. For every core vertex c with at most one core neighbour, take the path c, x1 , . . . , xR of (d). By (b), N [xj ] ⊆ hair(c). A vertex w lies in N [xj ] only for the c with w ∈ hair(c), and for at most three Pvalues of j, since the xj with w ∈ N [xj ] are at distance at most 2 from each other. So RL ≤ c,j y(N [xj ]) ≤ 3y(V ). Let I be the set of vertices of P with two core neighbours and no branch neighbour. A vertex w ∈ / K lies in N [z] with z ∈ I only for z = a(w), a branch vertex lies in no such N [z], and a vertex of P lies in N [z] only P for itself and its at most two neighbours on its core path. So |I| ≤ z∈I y(N [z]) ≤ 3y(V ), and |P | ≤ |I| + L + |A| ≤ 3y(V ) + 7L. Altogether, since L ≤ 3y(V )/R and R ≥ 1, X U

wt(U ) |∂U | ≤ 16L +

3y(V ) + 7L 48 + 3 + 21 72 ≤ y(V ) = y(V ). R R R

P 2 Let xU be the optimal solution of the problem defining opt(U ) that minimizes v xv ; it is P U unique, so the vertices of U agree on it. Output x = U wt(U )x . A vertex u is dominated in

15

each window that contains it, and these windows have total weight 1. By (1) with B = ∂U , for every fractional dominating set y, X

xv ≤

v

X U

 72  wt(U ) y(U ) + |∂U | ≤ 1 + y(V ). R

Take y optimal and R = ⌈72/ε⌉. A vertex decides membership in K within radius R, membership in P within R + 1, the value s(·) within R + 2, and its nearest core vertex within 2R. A window that contains v has its centre within 2R of v and all its vertices within 4R of v, by (b) and (c). So v finds the windows that contain it, and their problems, in its ball of radius 7R, and the algorithm runs in 7R ≤ 511/ε rounds. Randomized version. In O(1) rounds, compute a dominating set D0 with |D0 | ≤ cγ(G) for an absolute constant c [16]. Every vertex u ∈ / D0 picks a neighbour d(u) ∈ D0 , and d(v) = v for v ∈ D0 . Contracting the stars Sd = d−1 (d) gives a forest S H on D0 , and a round on H takes O(1) rounds on G. Let N = |D0 |. For W ⊆ V (H) let VW = d∈W Sd , and let ∂W be the set of d ∈ W with an H-neighbour outside W . If u ∈ VW has a neighbour w ∈ / VW , then d(u)d(w) is an H-edge leaving W , so d(u) ∈ ∂W ∩ N [u]. So (1) applies to U = VW and B = ∂W . Take the core and the hairs of F = H, with R ≥ 2. By (d), the hair of a core vertex with at most one core neighbour has more than R vertices. The hairs are disjoint, so L ≤ N/R. Cut the core edges at branch vertices; there are at most 6N/R of them. Every vertex of a core path draws an independent uniform value in [0, 1]. For a vertex u of a core path, let B(u) be the set of vertices of its core path at distance at most R from u, and let the anchor of u be the vertex of B(u) with the smallest value. Cut every edge uv of a core path whose ends have different anchors. This is a one-dimensional low-diameter decomposition in the spirit of [21]. The clusters are the resulting components of H[K] with their hairs, together with the components that miss K. All core vertices of a cluster have the same anchor, so the cluster has radius at most 2R + 1. If B(u) ̸= B(v), then B(u) ∪ B(v) has at least R + 2 vertices, and B(u)△B(v) has at most two. The anchors differ only if the smallest value in B(u) ∪ B(v) lies in B(u)△B(v), so uv is cut with probability at most 2/(R + 2). The core paths have fewer than N edges, so the expected number of cut edges is at most 8N/R. Each cluster W outputs its lexicographically first minimum dominating set for opt(VW ), integrally. Every cut edge puts at most two vertices into the sets ∂W . By the integral form of (1), the expected size is at most γ + 16N/R ≤ (1 + ε)γ for R = ⌈16c/ε⌉. A vertex sees its cluster, and the values that decide it, within distance O(R), so this takes O(R) rounds as well. The numerical checks are in tree frac.py and tree ldd.py. The proof uses forests only to build windows of radius O(R) and weighted boundary O(γf /R) locally. For planar graphs, such a local family of windows, with no dependence on n or on the maximum degree, would give Θ(1/ε) in the same way, and polylogarithmic losses would give Õ(1/ε). The star contractions of Section 2 give radius (c0 /ε)κ .

5.3

Outerplanar graphs

On outerplanar graphs, the inner faces take the place of the vertices of a tree. Short faces are seen locally, long faces are not. We remove the long faces by passing to a covering graph in which the face structure is a tree, and run the construction of Theorem 19 there. Vertices of high degree are handled by the way core paths are measured. Theorem 20. There is a constant C such that for every ε ∈ (0, 1] the following hold on every outerplanar graph G. A deterministic LOCAL algorithm computes a fractional dominating set of 16

weight at most (1 + ε)γf (G) in C/ε rounds. A randomized LOCAL algorithm always outputs a dominating set of expected size at most (1 + ε)γ(G) in C/ε rounds. With Theorem 17, the optimal number of rounds for both (1+ε)-approximations on outerplanar graphs is therefore Θ(1/ε), with no dependence on the maximum degree. On arbitrary graphs of maximum degree ∆, a deterministic (1+ε)-approximation of γf takes O(ε−4 log2 ∆) rounds [14]. In a constant number of rounds, the best ratio of a deterministic algorithm that outputs a dominating set of an outerplanar graph is 5 [3]. Proof. Let n = |V (G)| and m = |E(G)|, and let y be an optimal fractional dominating set of G. As in the deterministic part of the proof of Theorem 19, we work in G itself, here for both versions. We repeatedly use the packing bound : if the closed neighbourhoods of the vertices of a set A are pairwise disjoint, then γf (G) ≥ |A|, since each of them has y-weight at least 1. Faces. Fix an outerplanar embedding. Every vertex lies on the outer face, so the interior of a cycle C contains no vertex. It is cut by the chords of C into inner faces, all of whose vertices lie on C, and these faces form a tree under sharing an edge. A chord of the boundary of an inner face would enclose a vertex. Hence the inner faces are exactly the induced cycles of G, independently of the embedding. They are also isometric: a part of G outside an inner face F is attached to F at a vertex or at the two ends of an edge, so a path that leaves F returns through the vertex or edge by which it left. Two inner faces share at most one edge, and two faces with a common edge share no further vertex, since the common chord separates their other vertices. Fix ℓ ≥ 3. An inner face is short if it has at most ℓ vertices and a hole otherwise. Short faces are recognized in ℓ rounds. An ℓ-block is a class of short faces under the equivalence relation generated by sharing an edge, together with the vertices and edges of its faces. An edge on no short face is thin. The ℓ-blocks and the thin edges are the pieces, and every edge lies in exactly one piece. The faces of an ℓ-block B that contain a vertex v form a path in the weak dual of B, since the weak dual of the block of G that contains them is a tree. By the same uniqueness, two short faces at v lie in one ℓ-block if and only if they are joined by a sequence of short faces at v in which consecutive faces share an edge at v. So the pieces at v are determined by the faces at v, which have length at most ℓ or are seen to be longer within distance ℓ. Finally, every cycle C of length at most ℓ lies in one ℓ-block: the faces inside C are short, they are connected through shared edges, and every edge of C lies on one of them. The decomposition graph. Let D be the graph with the following nodes and bags: every short face, with its vertex set as bag; every thin edge, with its two ends; every vertex v that lies in no piece or in at least two pieces, with bag {v}. Two faces are adjacent if they share an edge. A vertex node v is adjacent to the thin edges at v and, for every ℓ-block B at v, to one face of B at v, chosen by the identifiers. The bags of two adjacent nodes meet in their adhesion, which is one vertex or one edge. Every edge of G lies in a bag. For every vertex v, the nodes whose bags contain v form a finite tree Dv . Let f be the number of inner faces, fs the number of short faces, t the number of thin edges, and let pv be the number of pieces at v. An ℓ-block B with nB vertices, m PB edges and fB faces satisfies nB − mB + fB = 1 andPcontains fB − P1 adjacencies of D. Hence P (|V (P )| − 1) = m − fs over the pieces P . Moreover v (pv − 1) = P |V (P )| − n, and vertices with pv = 1 are not nodes. Together with n − m + f = c(G), where c counts components, and c(D) = c(G), this gives X |E(D)| − |V (D)| + c(D) = (|V (P )| − 1) − n + c(G) = m − fs − n + c(G) = f − fs . P

So the cycle rank of D equals the number h of holes. 17

Few holes. We show h ≤ 3γf /(ℓ − 13). The inner faces, the bridges and the cut vertices of G form a forest T : two faces are adjacent if they share an edge, and a cut vertex is adjacent to the bridges at it and to one face of every other block at it. For distinct holes F and F ′ in one component, the path from F to F ′ in T leaves F through an edge or a vertex s of F : a chord of a block, with F and F ′ on different sides, or a cut vertex. So s separates F − s from F ′ − s, and F ∩ F ′ ⊆ s. Let S(F ) be the set of these P separators of F . They correspond to neighbours of F in the subtree of T spanned by the holes, so F |S(F )| ≤ 3h. Let W (F ) be the set of vertices of F at distance at least 2 from every element of S(F ). Since F is an induced isometric cycle, W (F ) has at least |F | − 4|S(F )| vertices, and it contains at least (|F | − 4|S(F )| − 2)/3 vertices at pairwise distance at least 3. Let u ∈ W (F ) and u′ ∈ W (F ′ ) for distinct holes in one component, and let s be the separator of F towards F ′ . Then u′ ∈ / s, since otherwise u′ ∈ F ∩ F ′ would lie in the separator of F ′ towardsPF . So every path from u to u′ passes through s, and d(u, u′ ) ≥ 3. By the packing bound, γf ≥ F (|F | − 4|S(F )| − 2)/3 ≥ h(ℓ − 13)/3. Unfolding. Let T be the universal cover of D, a forest, and let Π be its group of deck transformations. Every node of T carries the bag of its image in D. Let Ĝ be the graph whose vertices are the pairs (s, v) with s ∈ V (T ) and v in the bag of s, where (s, v) and (s′ , v) are identified whenever ss′ is an edge of T and v lies in its adhesion. Its edges join (s, u) and (s, w) whenever uw is an edge of G in the bag of s. Let π(s, v) = v. (i) π is a covering map, and Π acts on Ĝ freely and transitively on every fibre. The class of (s, v) consists of the pairs (s′ , v) with s′ in the copy of Dv in T that contains s, because Dv is a tree. Every edge vw of G lies in one piece, and within an ℓ-block in one face or in two adjacent faces of Dv . So the class has exactly one neighbour over every neighbour of v. The group Π permutes the copies of Dv freely and transitively. (ii) T is a tree decomposition of Ĝ. Its adhesions have at most two vertices, each bag has diameter at most ℓ/2 in Ĝ, and every vertex lies in finitely many bags. Every adhesion separates Ĝ, so a shortest path from an adhesion X to a vertex on one side of X stays on that side. Likewise, a path between two vertices of a bag that leaves the bag returns through the adhesion by which it left. So the bag of a face is an isometric cycle of Ĝ. (iii) Two distinct lifts of a vertex have distance more than ℓ. We claim that every closed walk of length at most ℓ lifts, from every starting point, to a closed walk. We use induction on the length. A backtrack lifts to a backtrack. A closed walk w0 . . . wk in which some vertex occurs twice among w0 , . . . , wk−1 splits into two shorter closed walks. Otherwise the walk is a cycle, so it lies in an ℓ-block B. Its lift stays in the copy of B that contains the starting point, and this copy maps isomorphically onto B. Now let v̂ ̸= v̂ ′ lie over v. A path between them of length at most ℓ would project to a closed walk whose lift from v̂, by unique path lifting, ends at v̂ ′ . (iv) Locality. The ball of radius r around a lift v̂ of v, with the nodes of T whose bags meet it, is determined by the subgraph of D induced by the nodes whose bags meet the ball of radius r around v. Paths from v̂ only pass through such nodes, and the corresponding part of T is the universal cover of that subgraph. A vertex therefore computes the ball in r + O(ℓ) rounds. Core and hairs. All distances are in Ĝ. For an edge ab of T with adhesion X, let h(a, b) be the largest distance from X to a vertex in a bag of the component of T − ab that contains b. By (ii), heights are monotone: if the side of cd that contains d is contained in the side of ab that contains b, then h(a, b) ≥ h(c, d). The core K consists of the nodes a with h(a, b) ≥ R for at least two neighbours b. All of this is invariant under Π, which preserves bags and identifiers. 18

(a) K meets every component of T in a connected set. The proof is that of Theorem 19(a). So every node outside K in a component that meets K has a unique nearest core node a(·). Let hair(c) = {c} ∪ a−1 (c). As in Theorem 19(b), an edge of T that leaves hair(c) joins c to a core node. (b) Every vertex in a bag of hair(c) has distance less than R + ℓ/2 from the bag of c. Let q be the neighbour of c towards a node of hair(c) whose bag contains the vertex. The side of qc that contains c contains a high side of c, so h(q, c) ≥ R. Since q ∈ / K, we get h(q, q ′ ) < R for all ′ other neighbours q of q. Each adhesion of q lies in its bag, which has diameter at most ℓ/2. (c) Components of T that miss K are finite, and their vertices span radius less than R + ℓ. Along an infinite ray, the adhesions leave every ball by (ii), so far out both directions are high. In a finite component, follow high directions without backtracking. The walk ends at a node with no high direction, or at an edge that is high in both directions and has no other high direction at its ends. (d) Hairs are disjoint and inject into G. If hair(c) and hair(c′ ) contain nodes s and gs with g ∈ Π, then gc = c′ . Fix an ownership, that is, a node of Dv for every v, chosen by the identifiers in the bags of Dv , and lift it. Then the vertices owned by the hairs of pairwise inequivalent core nodes project to disjoint sets, and injectively. Runs. A core node is a branch node if it has a number of core neighbours other than 2. The other core nodes have exactly two core neighbours, so the components of the subgraph of T that they induce are paths, the core paths. A core path is finite or infinite in both directions: a one-sided infinite path would contain nodes p and gp ̸= p with g ∈ Π, since D is finite. Then g would map it onto itself, but such a path has no automorphism other than the identity. Number the nodes of a core path as pi , with i in an interval of Z, and let Xi be the adhesion of the edge ei = pi pi+1 . For a vertex v, the indices i with v ∈ Xi form an interval, because the nodes whose bags contain v form a subtree. If this interval is nonempty, it is the run of v, and its length is its number of indices. Every index lies in the runs of the at most two vertices of its adhesion. A run is maximal if no other run strictly contains it, and every index lies in a maximal run. Two vertices may have the same run, and we count runs as intervals of indices. Let ρi be the length of the shortest maximal run that contains i. For a node p of a core path, with adhesions X and X ′ towards its two core neighbours, let λ(p) = d(X, X ′ ) if X ∩ X ′ = ∅, and λ(p) = 0 otherwise. Give ei the length µ(ei ) =

1 λ(pi ) + λ(pi+1 ) + , ρi 2

which does not depend on a direction and is invariant under Π. A vertex of high degree may lie in the adhesions of many consecutive edges, but these edges are then short. Let I1 , I2 , . . . be the maximal runs, ordered by their left ends. None contains another, so their right ends are ordered in the same way. No index lies in three of them, so Ic ∩ Ic+2 = ∅. (R1) If i ∈ Ic and j ∈ Ic′ with c′ ≥ c + 3, then Xi ∩ Xj = ∅. The run of a common vertex would contain the right end of Ic and the left end of Ic+3 . It would lie in a maximal run that contains the right end of Ic , that is, in Ic or in Ic+1 . Neither meets Ic+3 . P (R2) If k maximal runs meet an interval J of indices, then (k − 4)/2 ≤ ≤ k. For the i∈J 1/ρi P P upper bound, 1/ρi ≤ I∋i 1/|I| over the maximal runs I. For the lower bound, i∈I 1/ρi ≥ 1 for every maximal run I, since ρi ≤ |I| for i ∈ I. All but at most four of the k runs lie in J, since a run that sticks out contains an end of J, and every index lies in at most two of them. 19

P (R3) For a ≤ b, d(Xa , Xb ) ≤ 2 bi=a µ(ei ) + 3. Let I1 , . . . , Ik be the maximal runs that meet [a, b], in order, and let vc be a vertex with run Ic . Then v1 ∈ Xa and vk ∈ Xb , since the first of these runs contains a and the last contains b. If Ic and Ic+1 share an index, then d(vc , vc+1 ) ≤ 1. Otherwise Ic ends at some i and Ic+1 starts at i + 1. Among the maximal runs, only Ic contains i, so Xi ∩ Xi+1 = ∅. Then d(vc , vc+1 ) ≤ λ(pP is counted in i+1 ) + 2, and λ(pi+1 ) ≥ 1P full in µ(ei ) + µ(ei+1 ). Hence d(Xa , Xb ) ≤ k − 1 + 2 λ(pi+1 ), and k − 1 ≤ 2 bi=a 1/ρi + 3 by (R2). Windows. On every core path, fix ψ with ψ(pi+1 ) = ψ(pi ) + µ(ei ). The windows are: • for every core path and every real τ for which the following set is nonempty, the union of hair(p) over its nodes with τ ≤ ψ(p) ≤ τ + R, with weight dτ /R; • hair(b) for every branch node b, with weight 1; • every component of T that misses K, with weight 1. In every bounded range of τ the first family changes only finitely often, so sums over windows are finite sums of integrals. These families do not depend on the numbering of the core paths, neither on the origin nor on the direction, and they are invariant under Π. Every node of T lies in windows of total weight exactly 1. We identify a window with its node set QPand with the set W of vertices owned by Q. If a path window has the core nodes pa , . . . , pb , then b−1 i=a µ(ei ) ≤ R. By (R3), every Xi with a ≤ i < b lies within distance 2R + 3 of Xa . Every bag of pa , . . . , pb contains one of these adhesions and has diameter at most ℓ/2. With (b) and (c), every window has radius O(R + ℓ). Output. For a finite W ⊆ V (Ĝ) let opt+ (W ) be the smallest weight of an x ≥ 0 supported P on 2 N [W ] with x(N [u]) ≥ 1 for all u ∈ W , and let xW be the optimal solution that minimizes v xv . P Then xgW = g xW . Vertex v picks a lift v̂ and outputs xv = W wt(W ) xv̂W over the windows with v̂ ∈ N [W ]. The value does not depend on the lift. Since π maps N [û] bijectively onto N [u], X X X W x(N [u]) = ≥ wt(W ) xW (N [û]) ≥ 1. wt(W ) xŵ ŵ∈N [û]

W ∋û

W

The group Π is torsion-free and, by (i), acts freely on V (Ĝ). So no g ̸= 1 maps a finite window to itself, and the pairs P (v, W )Pwith v̂ ∈ N [W ] correspond to the pairs of a Π-orbit [W ] and a vertex of N [W ]. Hence v xv = [W ] wt(W ) opt+ (W ). Repair. Let ŷ = y ◦ π. For a window with node set P Q, let ∂Q be the set of edges of T with + exactly one end in Q. We claim opt (W ) ≤ ŷ(W ) + e∈∂Q |Xe |, where Xe is the adhesion of e. Let z ∈ W have a neighbour w ∈ / W . Walk in T from the owner of z to a node whose bag contains zw through nodes containing z, and then to the owner of w through nodes containing w. The first edge of this walk that leaves Q lies in ∂Q, and its adhesion contains z or w. Both lie in N [W ] and dominate z. Weight 1Pon these vertices and ŷ on W is feasible. Summing over orbits, and using P [W ] wt(W ) ŷ(W ) = v yv , we get X

xv ≤ γf (G) + 2

v

X

c(e),

[e]

where c(e) is the total weight of the windows with e ∈ ∂Q, and [e] ranges over the Π-orbits of edges of T , that is, over E(D). Counting. By (a), c(e) = 0 unless e joins two core nodes. If e lies on a core path, then c(e) ≤ 2µ(e)/R. If e meets a branch node, then c(e) ≤ 2. The core projects to a subgraph KD 20

of P D, and the number of core neighbours of a node equals its degree in KD . For a finite graph, deg≥3 (deg −2) is at most twice the cycle rank plus the number of vertices of degree 1. Here rk(KD ) ≤ rk(D) = h. So the branch nodes of D have at most 6h + 4N1 core neighbours in total, where N1 is the number of core nodes of D with at most one core neighbour. Such a core node c has a high side whose first node is not in K. By (a), this side lies in hair(c). It contains a shortest path u0 , . . . , uR from its adhesion, and the at least (R − 2)/3 vertices u2 , u5 , u8 , . . . have pairwise distance at least 3. Their closed neighbourhoods consist of vertices owned by hair(c). By (d) and the packing bound, N1 ≤ 3γf /(R − 2). A finite core path ends at two core edges that meet branch nodes, and an infinite one projects onto a component of KD that is a cycle. So there are at most 4h + 2N1 core pathsPup to Π. Next we bound µ(e) over the edges e of D on core paths. Fix a core path P , andPlet kP be its number of maximal runs, up to Π if P is infinite. As in the proof of (R2), 1/ρi ≤ I∋i 1/|I|. Summed over the edges of P , or over one period if P is infinite, the right side counts every maximal run once, up to Π. So the terms 1/ρi sum to at most kP . Number its maximal runs I0 , I1 , . . . , starting anywhere if P is infinite, so that Ic+kP is a translate of Ic . Pick an index td ∈ Id for every d ≡ 0 (mod 12). For c ≡ 6 (mod 12) with c + 6 ≤ kP − 4, let xc be a vertex of an adhesion with index in Ic . By (R1), the adhesions with indices in Ic , Ic±3 and Ic±6 are pairwise disjoint. Every adhesion separates Ĝ, so every path from xc to Xtc±6 has an inner vertex in an adhesion with index in Ic±3 . Hence N [xc ] consists of vertices owned by the hairs of the nodes pi with tc−6 < i ≤ tc+6 . For distinct c these nodes are distinct. If P is infinite, they lie in one period, since tc+6 lies before the left end of IkP −2 , and thus before the left end of theP translate IkP of I0 . There are at least (kP − 28)/12 values of c. By (d) and the packing bound, P kP ≤ 12γf + 28(4h + 2N1 ), over the core paths up to Π. Now let p be a node of a core path with λ(p) ≥ 6. Its bag is a face, since thin edges have λ ≤ 1 and vertex nodes have λ = 0, and by (ii) it is an isometric cycle. A shortest path in it between the two core adhesions of p contains at least (λ(p) − 5)/3 vertices at distance at least 3 from both adhesions and at pairwise distance at least P 3. Their closed neighbourhoods consist of vertices owned by hair(p). By the packing bound, p λ(p) ≤ 3γf + 5 |{p : λ(p) > 0}|. A node pi+1 with λ(pi+1 ) > 0 that is not an end of its core path has Xi ∩ Xi+1 = ∅, so a maximal run ends at i. So at most kP + 2 such nodes lie on P , up to Π. Altogether, X X X X µ(e) ≤ kP + λ(p) ≤ 6 kP + 3γf + 10(4h + 2N1 ) ≤ 75γf + 178(4h + 2N1 ). e

P

p

P

P

(1424/R + 12)h + (712/R So [e] c(e) ≤ 150γf /R +P P+ 8)N1 . Take ℓ = R + 13. For R ≥ 1500, the bounds on h and N1 give [e] c(e) ≤ 215γf /R, so v xv ≤ γf + 430γf /R. Take R = ⌈1500/ε⌉. The core, the runs and the lengths µ near a node are determined within distance O(R + ℓ). By (iv), the windows that contain or neighbour v̂ are computed in O(R + ℓ) = O(1/ε) rounds. Randomized version. Let ℓ = 6R + 5. Cut every core edge at a branch node, and every edge e of a core path with µ(e) > R. This splits the core paths into segments. Every edge e of a segment gets an exponential clock of rate µ(e). There is one clock for each edge of D, drawn by the vertex with the smallest identifier in its adhesion, so the clocks are invariant under Π. For a node p of a segment, let B(p) be the set of edges of the segment whose ends have ψ-distance at most R from p. If p has an edge in the segment, this edge lies in B(p), and the anchor of p is the edge of B(p) with the smallest clock. Cut every edge of a segment whose ends have different anchors. The clusters are the components of the remaining core with their hairs, and the components of T that miss K. All core nodes of a cluster lie within ψ-distance R of the ends of a common anchor. On a core path, µ ≥ 1/ρ > 0, and µ takes finitely many values since it is invariant under Π. So a ψ-interval of bounded length contains finitely many nodes, and every cluster is finite. As for the windows, (R3) shows that it has radius O(R + ℓ) = O(R). No g ̸= 1 maps a finite cluster to itself, so π is 21

injective on every cluster, and the projections of the clusters partition V (G). Each projected cluster C outputs the lexicographically first smallest set in N [C] that dominates P C. The walk argument, applied to a lift of a boundary vertex of C, bounds its size by |S ∩ C| + e∈∂Q |Xe | for a minimum dominating set S. So the expected size is at most γ + 4 E[#cut edges of D]. Let Pei and ei+k = gei with g ̸= 1 and k > 0 be edges′ of one core path. By (iii), d(Xi , Xi+k ) > ℓ− ′ 1, so i+k j=i µ(ej ) > (ℓ − 4)/2 > 3R by (R3). Let e = pp be an edge of a segment, with ψ(p) < ψ(p ). The edges in B(p) ∪ B(p′ ) lie in a ψ-interval of length µ(e) + 2R ≤ 3R, so they are lifts of distinct edges of D, and their clocks are independent. The anchors of p and p′ differ only if the smallest clock in B(p)∪B(p′ ) lies in B(p)△B(p′ ). This happens with probability µ(B(p)△B(p′ ))/µ(B(p)∪B(p′ )), where µ of a set of edges is their total length. An edge f whose ends sit at ψ-positions x < y lies in B(q) exactly when ψ(q) ∈ [y − R, x + R]. If f ∈ B(p) \ B(p′ ), then ψ(p) − R ≤ x < ψ(p′ ) − R, and all edges of the segment between x and ψ(p′ ) lie in B(p). So µ(B(p)) > R whenever B(p) ̸⊆ B(p′ ), and symmetrically for p′ . Hence e is cut with probability at most µ(B(p)△B(p′ ))/R. Moreover, f ∈ B(p)△B(p′ ) only if y − R ∈ (ψ(p), ψ(p′ )] or x + R ∈ [ψ(p), ψ(p′ )). This happens for at most two edges e of P the segment. Summing over the orbits, we bound the expected number of anchor P cuts in D by 2 f µ(f )/R, over the edges f of D on core paths. At most f µ(f )/R of them have µ(f ) > R, and at most 6h + 4N1 core edges meet a branch node. With the bounds of the counting and ℓ = 6R + 5, fewer than 248γf /R edges of D are cut in expectation for R ≥ 2200, and the expected size is less than γ + 992γ/R. Take R = ⌈2200/ε⌉. A node decides its cluster from the clocks within ψ-distance O(R). By (R3) they lie within distance O(R) in Ĝ, so by (iv) this takes O(R + ℓ) = O(1/ε) rounds. The numerical check is in outer frac.py. It covers rings, chains of holes and random outerplanar graphs of maximum degree 3, 4 and 6, and graphs with vertices of degree up to 320: fans, strips of alternating fans, Farey graphs, a hole with large fans glued to its outside, and random graphs that attach new faces preferentially at vertices of high degree. In all cases P the windows have weight exactly 1 at every vertex, the averaged x dominates, and the excess v xv − γf is at most the repair bound. That bound stays below 19γf /R, against 430γf /R in the proof, and it does not grow with the maximum degree. Every window lies within distance R + ℓ of one of its vertices. The holes in these graphs are long enough that no window wraps around one, so the script works in G itself and does not build Ĝ. For the randomized version, the script also samples the long and P µ(f )/R, against the anchor cuts on the core paths. Their expected number stays below 1.1 f P 3 f µ(f )/R in the proof.

6

Formal verification

The Lean files and the scripts named in this paper are in the repository https://github.com/ssenge/MinimumDominatingSetOnPlanarGraphs, in the directories lean/Op4/, sim/tight/ and sim/lower/. The Lean version is v4.36.0-rc1, and the Mathlib revision is pinned in lean/lake-manifest.json. Every checked theorem depends only on the standard axioms, and no proof is left open. The file RandomCentres.lean formalizes Section 2, with the random centre set modelled exactly as independent coins. It checks Lemma 2 (gain eq join edges), Lemma 3 (vertex bound), Theorem 4 (random centres), the identity between the arc sum and the edge weight, the value f3 (3/8) = 1935/12288 and the bound f3 ≤ 63/400, Lemma 5, and the bounds 6.4 < ln 3/ ln(1/(1−f3 (3/8))) < 6.42, ln 3/ ln(1/(1 − f3 (1/2))) < 7 and 25 < κ < 26. The file Orientation.lean proves the direction of the orientation theorem of [8] that we use, by Hall’s theorem: if every vertex set S spans at 22

most k|S| edges, there is an orientation with out-degree at most k (orientation of density). So Theorem 4 holds for every such graph (random centres density). The file Sharper.lean checks Section 2.1. Theorem 10 (sharper) is proved in a discrete form of Lemma 7, by induction on the number of edges of positive weight: the smallest positive weight t is subtracted from every positive edge, and the gain splits as t times the join indicator plus the gain of the remaining weights. Also checked are Lemma 9 from (A) and (B) (degree lemma), the certificates for p = 3/8 and p = 1/2 (cert three eighths, cert half), the values of φ, and the bounds 5.88 < κ′ < 5.89 and κ′p=1/2 < 6.7. In this file, Lemma 8 enters as a hypothesis on every symmetric weighting whose support lies in that of w. The certificate of Lemma 9 is checked for every p ∈ [21/64, 1] (cert range), with h1 and h2 bounded as in the proof. So sharper range gives Theorem 10 on the whole range, and kappa six coins gives 5.82 < κ′ < 5.83 for p = 21/64. The file General.lean checks Section 2.2: Theorem 12 (general, for finitely many real thresholds, through the layer-cake core sharper core), its degree inequality (degree lemma gen), and Corollary 13 (aonly, with the certificate cert aonly). Here too, the facts of Lemma 11 enter as hypotheses. The file Density.lean removes these hypotheses. It proves Lemmas 8 and 11 from two bounds on the support of w: every vertex set S spans at most a|S| edges, and for disjoint S and T at most b(|S| + |T |) edges join S to T (facts of density, planar facts). Both bounds pass to every weighting whose support lies in that of w. Hence Theorem 10 for every p ∈ [21/64, 1] (sharper range density) and Theorem 12 (general density) need only these two bounds on w, and Theorem 4 needs only the first (random centres densityA). For planar graphs, a = 3 and b = 2 by Euler’s formula, which we take as given. The file Surfaces.lean checks every row of Table 2 with e ≥ 3: the certificate (cert genuse), the conditions t ≥ ae and u ≥ 2ae on its thresholds, the per-level bound under the density bounds ae and be , obtained from general density (surface genuse), and the exponent bound in the last column (kappa genuse). The densities ae and be come from Euler’s formula on the surface. The row e ≤ 2 is Theorem 10. The file Asymptotic.lean checks Proposition 6: the limit 8 for every p(a) with p → 0 and ap → ∞ (expRatio tendsto eight), the limit 8(1 − p) for a fixed p (expRatio tendsto const), and the dyadic choice (dyadic p). It also checks that with p = 1/2 the exponent is at most that of [1] for every a ≥ 1/2 (never worse). The file Levels.lean checks the step from the per-level factor to the number of rounds in Section 3. If ct+1 ≤ q ct for every t and x ≥ 1, then L = ⌈log x/ log(1/q)⌉ levels give cL ≤ c0 /x and 3L ≤ 3xκ with κ = ln 3/ ln(1/q) (levels). This is how the factor q ′ enters the exponent of the round bound TC + 9 · 3L of [1, Thm. 5.4]. The algorithm of [1] and the rest of its analysis are not formalized. The file PathLower.lean checks the counting in Theorem 17. Every fractional dominating set of P2R+M with M ≥ 4 that is constant on the middle and invariant under reflection has weight at least (2R+M )/3+2/3 (path excess). For L = 2r+6+(r mod 3), 3 divides L and γ(PL ) = γf (PL ) = L/3 (path gamma). So the weight is at least (1+2/L)γf (PL ), where 1+2/L ≥ 1+1/(r+4) (path lower), and ratio 1 + ε forces r ≥ 1/ε − 4 (rounds lower). The files LocalPath.lean, LocalRandom.lean and LocalMeasure.lean check the symmetrization over identifiers in an explicit model of r-round algorithms on PL . The view of a vertex lists the identifiers and the degrees of the vertices at offsets −r, . . . , r, with an empty entry for offsets outside the path. In the randomized case it also lists their coins. The coins are independent of each other and of the identifiers, and all have the same law on an arbitrary probability space, so real-valued randomness is included. A ball in a path has no preferred direction, so the algorithm is a function of the view that does not change when the view is read backwards. It may depend 23

on L, r and the size of the identifier space. Suppose its output is a fractional dominating set for every injective identifier assignment and, in the randomized case, every outcome of the coins. In the randomized case the output at a vertex must also be integrable in the coins, which holds if it is measurable and bounded. Then for some assignment the (expected) weight is at least (1 + 2/L)γf (PL ) (local path lower, measure path lower). Hence the ratio is at least 1 + 1/(r + 4), and ratio 1 + ε forces r ≥ 1/ε − 4 (local rounds lower, measure rounds lower). As in the proof of Theorem 17, the identifier assignments and the coins are averaged together; permuting the coordinates of an independent and identically distributed vector of coins does not change its law. For coins with finitely many values, LocalRandom.lean gives an elementary version with finite sums. The file PathUpper.lean checks the upper bound on paths in the same model. Every fractional dominating set of PL has weight at least ⌈L/3⌉ (path lower ceil). For every r ≥ 0 and L ≥ 1, the algorithm described after the proof of Theorem 17 reads from the view only the distance to the nearer end, capped at r + 1. So it does not change when the view is read backwards, and it may use L. For every injective identifier assignment it outputs a fractional dominating set of weight at most (1 + 2/(2r + 3)) y(PL ) for every fractional dominating set y of PL (local path upper). Hence for 0 < ε ≤ 1 some r ≤ 1/ε − 1/2 gives ratio 1 + ε (local rounds upper). The file Windows.lean checks, for finite graphs, the steps of Theorems 19 and 20 that do not depend on the graph class: the packing bound (packing), the repair (1) (repair) and the averaging over windows (window average). For the averaging, let the windows cover every vertex with total weight exactly 1. Let every window U come with a set B that meets N [u] for every u ∈ U with a neighbour outside U , and with a solution that dominates U and is optimal among the vectors supported on a given set that contains U and B. Then P the weighted average of these solutions is a fractional dominating set of weight at most y(V ) + U wt(U ) |B| for every fractional dominating set y. This gives the first inequality of the averaging step in the proof of Theorem 19. In Theorem 20, packing applies as it is, and repair, on the finite graph induced by N [W ], gives the feasible solution of the repair step. For Theorem 20, the windows, the bounds on their boundaries, the averaging over Π-orbits with continuous weights in the covering graph, the randomized version and the round count are proved on paper only. The files ForestBasic.lean to ForestLocal.lean check the deterministic part of the proof of Theorem 19 on every finite forest: (a) to (d), the counts of branch vertices, the cover by windows of total weight exactly 1 (cover, with cover count on the core paths), the bounds RL ≤ 3y(V ) (card L le) and |P | ≤ 3y(V ) + 7L (card P le), and the bound (72/R) y(V ) on the weighted boundary (sum wt wB le). Lean lists the windows at an end e once for each of the s(e) directions, and every component C that misses the core once for each of its vertices, with weight 1/|C|. Instead of the optimum of least norm, the output averages one fixed optimal solution of each window problem, which exists by compactness (exists isOpt). It is a fractional dominating set of weight at most (1 + 72/R) y(V ) for every fractional dominating set y (forest frac). On any two forests in which the vertices at distance less than 7R from v have the same neighbours, the outputs at v are equal (forest local). Here the vertex set is the identifier space, and the identifiers that are not nodes are isolated vertices; the bound then holds on the nodes (forest frac on). The randomized part is not formalized.

7

Open questions • Can ratio 7 + ε be achieved in poly(1/ε) rounds with exponent close to 2, matching the (8 + ε) algorithm [23]? By [1], a deterministic (1 + ε)-approximation of γf on planar graphs, with no degree bound, in such a number of rounds would suffice ([1, Open Problem 3]). By

24

Corollary 18, the optimal number of rounds lies between 1/ε − 4 and O((c0 /ε)5.83 ), and for forests and for outerplanar graphs it is Θ(1/ε) (Theorems 19 and 20). Do planar graphs admit local windows of radius Õ(1/ε) and weighted boundary εγf (Section 5.2)? Or is there a planar lower bound that is superlinear in 1/ε? • In a constant number of rounds, deterministic algorithms that output dominating sets cannot beat ratio 3 on paths [1, Thm. 8.7], while for fixed ε a (1 + ε)-approximation on planar graphs takes O(log∗ n) rounds [5]. How do the dependencies on ε and on n combine, already on paths? • What is the worst case of the expected gain of the uniform rule on planar graphs? For the best p, it lies between 0.1718 (Theorem 10) and 0.1741 (Apollonian networks). • Is there a rule in which the centre decisions depend on each other and that provably contracts more than φ(p) per level? By Proposition 16, rules with independent coins cannot go below an exponent of 4.74 with an analysis that counts only join edges, and by Proposition 15 no such analysis of any star contraction goes below 3.81.

Use of AI Claude Opus 5.5 (Anthropic) was used throughout this research: to explore approaches, to develop and check proofs, to write the simulation scripts and the Lean formalization, and to draft the text.

References [1] S. Amiri and S. Siebertz. Almost optimal constant-round approximation of dominating set in graph classes with excluded minors. arXiv:2610.09618, 2026. [2] B. S. Baker. Approximation algorithms for NP-complete problems on planar graphs. J. ACM, 41(1):153–180, 1994. [3] M. Bonamy, L. Cook, C. Groenland, and A. Wesolek. A tight local algorithm for the minimum dominating set problem in outerplanar graphs. In DISC, LIPIcs 209, 2021. [4] Y.-J. Chang and Z. Li. The complexity of distributed approximation of packing and covering integer linear programs. In PODC, 2023. arXiv:2305.01324. [5] A. Czygrinow, M. Hańćkowiak, and W. Wawrzyniak. Fast distributed approximations in planar graphs. In DISC, 2008. [6] I. Dinur and D. Steurer. Analytical approach to parallel repetition. In STOC, 2014. [7] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. [8] S. L. Hakimi. On the degrees of the vertices of a directed graph. J. Franklin Inst., 279(4):290– 308, 1965. [9] O. Heydt, S. Kublenz, P. Ossona de Mendez, S. Siebertz, and A. Vigny. Distributed domination on sparse graph classes. arXiv:2207.02669, 2022.

25

[10] M. Hilke, C. Lenzen, and J. Suomela. Brief announcement: Local approximability of minimum dominating set on planar graphs. In PODC, 2014. [11] L. Jia, R. Rajaraman, and T. Suel. An efficient distributed algorithm for constructing small dominating sets. Distrib. Comput., 15(4):193–205, 2002. [12] D. S. Johnson. Approximation algorithms for combinatorial problems. J. Comput. System Sci., 9(3):256–278, 1974. [13] F. Kuhn. The Price of Locality: Exploring the Complexity of Distributed Coordination Primitives. PhD thesis, ETH Zurich, 2005. [14] F. Kuhn, T. Moscibroda, and R. Wattenhofer. The price of being near-sighted. In SODA, 2006. [15] F. Kuhn, T. Moscibroda, and R. Wattenhofer. Local computation: Lower and upper bounds. J. ACM, 63(2):17, 2016. [16] C. Lenzen, Y.-A. Oswald, and R. Wattenhofer. What can be approximated locally? Case study: Dominating sets in planar graphs. In SPAA, 2008. [17] R. Levi and D. Ron. A quasi-polynomial time partition oracle for graphs with an excluded minor. ACM Trans. Algorithms, 11(3):24, 2015. [18] N. Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193–201, 1992. [19] W. Mader. Homomorphiesätze für Graphen. Math. Ann., 178:154–168, 1968. [20] L. R. Matheson and R. E. Tarjan. Dominating sets in planar graphs. European J. Combin., 17(6):565–568, 1996. [21] G. L. Miller, R. Peng, and S. C. Xu. Parallel graph decompositions using random shifts. In SPAA, 2013. [22] M. Parnas and D. Ron. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theoret. Comput. Sci., 381(1–3):183–196, 2007. [23] W. Wawrzyniak. Near-optimal distributed domination in planar graphs. arXiv:2609.32736, 2026.

26

Related documents

• Random Centres and the $\varepsilon$-Dependence of Constant-Round Planar Domination#1488812
• Local large deviations for triangles in sparse random graphs#1036279
• Quasi-uniform designs from random candidates: optimal candidate complexity and farthest-point sampling#973598
• Sharp lower bounds for bisections of graphs with bounded maximum degree#1325920
• Hermite Brings a Laptop: Analyzing Frieze-Jerrum Rounding Yields Improved Approximations for Clustering Problems#1130038