Near-Optimal Distributed Domination in Planar Graphs

1 Introduction

• Constant-factor approximations already exist in constant rounds on planar graphs, but the best possible approximation factor was unknown; a lower bound rules out factors below 7 − ε.The lower bound was improved from 5 − ε to 7 − ε for deterministic constant-round algorithms.Source: §1 · p. 1
• An (8 + ε)-approximation is computable deterministically in a constant number of LOCAL rounds on every simple planar graph.The algorithm applies for every ε > 0.Source: §1 · p. 2
• The leading approximation constant is one above the lower bound of 7, reducing the previous gap from 4 to 1 and closing three quarters of it.Whether a (7 + ε)-approximation is achievable on all planar graphs remains open.Source: §1 · p. 2
• A sharp structural bound on contacts between owner blocks underpins the new factor, and the blocks are proof tools the algorithm need not construct.The bound holds for every dominating set and every assignment to neighboring centers.Source: §1 · p. 2
• The algorithm adapts Heydt et al.'s three phases and final linear-programming procedure, using threshold 6 instead of 3 in the first phase.The new structural theorem gives a stronger bound on the size of the selected set.Source: §1 · p. 2
• A transfer theorem gives a deterministic (25 + ε)-approximation on bounded-Euler-genus graphs, improving the previous ratio of 34 + ε.For Euler genus 1 ≤ g ≤ 5, Heydt et al.'s bound is smaller than 25 + ε.Source: §1 · p. 2

2 Owner blocks and the structural theorem

• An owner assignment maps each center to itself and each non-center to one of its neighboring centers.The centers form the dominating set.Source: §2 · p. 3
• Each center's owner block contains the vertices assigned to it, and the center-to-non-center owner edges form an owner star.Blocks may contain extra internal edges and need not be just stars.Source: §2 · p. 3
• For a non-center x, k_x counts the distinct foreign blocks containing a neighbor, so multiple neighbors in one block count once.The weight of x is (k_x − 2)^+, positive exactly when k_x ≥ 3.Source: §2 · p. 3
• The contact graph has one vertex per center and an edge when the corresponding owner blocks have an edge between them; it remains planar when G is planar.Contracting owner stars, deleting loops, and keeping one edge per center pair constructs it.Source: §2 · p. 4
• Theorem 2.6 is stated for every planar graph, dominating set, and owner assignment; the proof treats 2-connected contact graphs, then cut vertices and disconnected graphs.The theorem statement supplied here does not include its bound.Source: §2 · p. 4

3 Tricolored faces and the 2-connected case

• The proof combines a two-corner saving per owner block with the global tricolored-corner bound to control W.The corner count in each block is bounded by its tricolored corners minus two; summing these bounds uses the total corner bound.Source: §3 · pp. 5, 8
• When H − d is connected, the foreign neighbors of x form an interval around x, and t(x) ≥ kx − 1.Each new foreign-block label in the interval requires a change between consecutive neighbors, corresponding to a distinct tricolored face.Source: §3 · pp. 5–6
• For each d, cyclically ordering edges leaving B_d by their other endpoint’s owner gives n_d label changes, including the wraparound.The changes correspond to tricolored corners at vertices of B_d.Source: §3 · p. 6
• At most 2q − 4 triangular faces are tricolored when a connected plane graph is partitioned into q ≥ 2 connected blocks.The proof maps each tricolored face to a vertex and contracts each block, obtaining a simple planar bipartite graph.Source: §3 · p. 7
• In a triangulation, the total number of tricolored corners is 3F3, so it is at most 6|D| − 12 for the owner blocks.Each tricolored face contributes three corners, and the face bound applies to the connected owner blocks.Source: §3 · pp. 7–8
• W ≤ 4|D| − 12 for any planar graph with dominating set D, fixed owner blocks, and 2-connected contact graph H.The proof extends the graph to a triangulation while retaining the owner blocks and does not decrease contact counts.Source: §3 · pp. 4, 5, 8

4.1 Splitting at a cut vertex

• Cut-vertex splitting creates smaller planar owner instances that share the cut vertex’s block, while non-centers outside that block retain their contact counts.Only non-centers in the shared block can change weight across pieces.Source: §4.1 · pp. 8–9
• A planar bipartite incidence graph bounds the total loss in weights of shared-block vertices whose contacts split across multiple pieces.The construction contracts each component region and retains owner edges from v to Z and contacts from Z to contracted vertices.Source: §4.1 · p. 10

4.2 Connected contact graphs

• Induction on the number of centers combines the cut-vertex estimate with the 2-connected case to bound the weight for every connected contact graph.The proof treats the case where every piece has two centers separately.Source: §4.2 · pp. 11–12

4.3 The general structural theorem

• For every planar graph, dominating set, and owner assignment, the total weight is at most (4|D| − 12)+.The proof sums bounds over positive-weight components; vertices with at least six foreign contacts then number at most (|D| − 3)+.Source: §4.3 · p. 12

5 The constant-round domination algorithm

• For each fixed ε, the deterministic LOCAL algorithm needs neither a plane embedding nor graph size, and its round count depends only on ε.It uses unique vertex identifiers.Source: §5 · p. 12

5.1 The three phases

• The first phase selects vertices whose neighborhoods cannot be dominated by six others; the second selects vertices with a partner sharing at least nineteen neighbors in R1; the third uses an LP-based routine on R.The output is S ∪ D3, where S = D1 ∪ D2.Source: §5.1 · p. 13

5.2 Used in the analysis

• The analysis bounds the first-two-phase selection by |S| ≤ (|D| − 3)+ + 7|S ∩ D|.The bound uses the estimate |bD6 \ D| ≤ (|D| − 3)+ and limits the number of partners per selected vertex to six.Source: §5.2 · pp. 13–14

6.1 Bounds used in the third phase

• The residual set R consists of vertices not dominated by S, and D \ S already dominates R, so a smallest set dominating R has size at most |D| − |S ∩ D|.The set used for this comparison may contain vertices outside R.Source: §6.1 · p. 14

6.2 The third phase

• The third-phase LOCAL routine uses residual-degree bound 114 and planar density bound three to obtain a (7 + ε) bound in rounds depending only on ε.The proof sets ξ = ε/7 in the routine’s bound.Source: §6.2 · p. 15

6.3 The approximation guarantee

• The three-phase algorithm returns a dominating set of size at most (8 + ε)|D|.S dominates vertices outside R, while D3 dominates R.Source: §6.3 · p. 15

7 Scope and further questions

• The coefficient one in the bound on |A| is sharp, but this does not prove that factor 8 + ε is optimal.Whether factor 7 + ε is achievable on all planar graphs remains open.Source: §7 · p. 15
• Closing the gap to 7 may require stronger joint analysis of the first two phases and the residual instance, or a different selection rule.Source: §7 · p. 15

7.1 A consequence for bounded Euler genus

• The transfer theorem gives a deterministic (25 + ε)-approximation on graphs of Euler genus at most g in C(g, ε) LOCAL rounds.This improves the transfer theorem's prior 34 + ε ratio; for Euler genus 1–5, the bound derived from Heydt et al. is smaller.Source: §7.1 · p. 15

• Generative AI assisted with proof constants, references, examples, English editing, organization, and LaTeX; the author checked the proofs and reviewed the figures.The author states responsibility for the results and final manuscript.Source: Use of generative AI · p. 16

• The argument is presented for cover size six and partner threshold nineteen, following Heydt et al. [12, Lemmas 8.1 and 8.2].Source: A Proof of the partner bound · p. 18
• With a cover Z of at most six vertices, every partner of v belongs to Z when N(v) ⊆ N[Z].The proof assigns nineteen common neighbors among six cover vertices; one covers at least four, yielding a K3,3 contradiction if the partner lies outside Z.Source: A Proof of the partner bound · p. 18
• Every vertex in D2 has at most six partners, and D1 and D2 are disjoint.Vertices in D1 have no partners; vertices in D2 have neighborhoods dominated by at most six other vertices.Source: A Proof of the partner bound · p. 18

• The residual-degree argument uses cover size six and partner threshold nineteen, following Heydt et al. [12, Lemma 8.7].Source: B Proof of the residual-degree bound · p. 18
• R = V \ N[S] is the set of vertices still undominated after the first two phases, where S = D1 ∪ D2.Source: B Proof of the residual-degree bound · p. 18
• A vertex with at least 115 neighbors in R would yield a contradiction, so every vertex has fewer than 115 neighbors in the residual set.Among 115 neighbors, one of six cover vertices covers at least twenty; after removing it if needed, nineteen common neighbors imply the vertex belongs to D2 and hence S, contradicting its neighbors remaining in R.Source: B Proof of the residual-degree bound · p. 18

C Sharpness and the meaning of the contact bound

• For each r ≥ 2, nested triangles form a triangulation with q = 3r vertices; adding one leaf per vertex makes the leaves a dominating set D.Assign each original vertex v to its leaf dv, forming owner blocks {v, dv}.Source: C Sharpness and the meaning of the… · p. 19, Figure 7 · p. 19
• |A| = q − 6 and W = 4q − 12, attaining the stated bounds for the construction.The q − 6 degree-six vertices have weight four; the other six non-centers have weight two.Source: C Sharpness and the meaning of the… · pp. 18–19
• D is minimum: disjoint closed neighborhoods around the leaves force every dominating set to contain at least q vertices, and D has size q.Source: C Sharpness and the meaning of the… · p. 19
• For each degree-six vertex v, covering N_G(v) with centers from D requires seven centers; (q − 6)/q tends to one as r grows.Thus the coefficient one in the bound on |A| cannot be reduced, even when D is minimum.Source: C Sharpness and the meaning of the… · pp. 18–19
• The examples show the bounds’ coefficients cannot be reduced, but do not establish that approximation factor eight is best possible.Source: C Sharpness and the meaning of the… · p. 19