Almost tight distributed approximation for domination in sparse graph classes

1.1 Related works

• For distributed Minimum Dominating Set, bounded-expansion graphs admit constant-factor approximations in constant rounds; bounded-genus graphs admit a (34+ε)-approximation independent of genus [BGD+26], improved to (25+ε) [Waw26b] and then (7+ε) [AS26].Source: §1 · p. 2

1 Introduction

• d+1+ε is tight for bounded-expansion classes at every even d≥2, as powers of paths yield a d+1 lower bound.Additional graph structure can permit better ratios for particular classes.Source: §1 · pp. 2–3
• 7+ε applies to planar and bounded-genus graphs, while 5+ε applies to their triangle-free subclasses.These results match the cited Amiri and Siebertz bounds.Source: §1 · p. 3

1.2 Comparison with recent algorithms

• We add sunflower-sparsified hypergraph constraints to an LP, unlike [AS26]’s clustering and averaging approach and [Waw26b]’s refinement of Heydt et al.’s algorithm.The approach adapts preprocessing and LP rounding from.Source: §1.2 · p. 6
• Our guarantee is against integral MDS rather than the fractional optimum, but extends beyond proper minor-closed classes, including bounded queue-number and stack-number classes.The comparison also reports improved dependence on ε and polynomial local computation for fixed parameters.Source: §1.2 · p. 7

1.3 High-level overview

• The pipeline sparsifies hard-to-dominate hyperedges, selects inexpensive high-degree vertices, solves a combined hitting-set and domination LP, then rounds the fractional solution.The rounding selects vertices of weight at least 1/(d+1) and adds vertices left undominated; the d+1 factor arises only in rounding.Source: §1.3 · pp. 7–9
• The overview initializes R0 as V(G) \ X.Source: §1.3 · p. 9
• The overview returns P ∪ A ∪ U, where P contains vertices of degree greater than Γ in G′ and A ∪ U is obtained by running Algorithm 2 on (F, R1, x, d).It forms G′ using V(H) ∪ R0 and representatives of other nonempty R0-neighborhoods, sets F = G′ − P and R1 = R0 \ NG[P], and computes fractional solution x from Lemma 3.15.Source: §1.3 · p. 9

• A graph's open and closed neighborhoods describe its adjacent vertices and itself; a hypergraph consists of vertices and hyperedges, with rank and hitting sets defined from those hyperedges.Source: §2 · p. 9
• A minor is obtained by vertex or edge deletions and edge contractions, while Euler genus measures the least-genus surface in which a graph can be embedded.Source: §2 · p. 9
• Maximum average degree, arboricity, and degeneracy are linearly equivalent sparsity measures; depth-r shallow minors contract disjoint connected subgraphs of radius at most r, and ∇1 measures depth-one shallow-minor density.Source: §2 · pp. 9–10
• A graph class has bounded expansion when shallow-minor density is bounded at every depth; in particular, this bounds ∇1 and places the class within the theorem's applicability.Source: §2 · p. 10
• In the deterministic LOCAL model, vertices communicate synchronously with arbitrary-size messages, and a T-round output depends only on the T-radius neighborhood and its identifiers.Source: §2 · p. 10

3 The algorithm and its analysis

• A deterministic constant-round LOCAL algorithm gives a (d + 1 + ε)-approximation when ∇1(G) ≤ β and the theorem’s stated density condition holds.For mad(G) ≤ d, the corollary applies to bounded expansion classes with maximum average degree at most d.Source: §3 · p. 10

3.1 The rounding procedure

• One deterministic LOCAL round selects vertices with weight at least 1/(d + 1) and adds the still-undominated vertices of R.The returned set intersects every hyperedge and has size at most (d + 1) times the total vertex weight plus 4b/d.Source: §3.1 · pp. 10–11
• The rounding bound is the main bottleneck yielding the mad(G) + 1 term; losses in the other steps can be made arbitrarily small.When mad(G) ≤ d, the lemma’s additive parameter can be set to b = 0.Source: §3.1 · p. 11

3.2 Hard-to-dominate neighborhoods

• The set T of vertices outside a minimum dominating set whose neighborhoods cannot be dominated by at most q dominators has size at most ρ MDS(G).The proof uses a depth-one shallow minor and its edge-density bound.Source: §3.2 · pp. 12–13
• Adding T to a minimum dominating set forms a dominating set C of size at most (1 + ρ) MDS(G).For each vertex outside D ∪ T, its neighborhood can be dominated by a subset Dv ⊆ D of size at most q.Source: §3.2 · pp. 12–13

3.3 Constructing and sparsifying the hypergraph

• A small set A becomes a hyperedge when no set of at most q vertices outside A dominates X(A), forcing a hitting set to select within A.The construction maintains an invariant ensuring D ∪ T hits every hyperedge.Source: §3.3 · p. 13
• Replacing a sunflower with its kernel preserves all hitting sets of size at most q, since such a hitting set must intersect the kernel.The kernel intersects every set in the sunflower, whose petals are pairwise disjoint.Source: §3.3 · p. 13, Figure 3 · p. 14
• The final hypergraph H has rank at most r, bounded maximum degree, diameter-at-most-two hyperedges, and is hit by C ∩ V(H).Every hyperedge of H0 contains a hyperedge of H.Source: §3.3 · p. 14

3.4 Bounding the size of the residual set

• Claim 3.6 excludes K_{r+1,t} as a subgraph of G and establishes r ≤ d + 1.The exclusion follows from the graph’s density assumption.Source: §3.4 · pp. 14–15
• Every vertex has a constant number of neighbors in R0, so |R0| is at most (B2 + 1) MDS(G).The proof uses the bound on neighbors in R0 and the fact that D dominates R0.Source: §3.4 · p. 15
• The neighbor bound is proved by repeatedly adding a vertex that dominates at least a 1/q fraction of the remaining vertices in X(Ai) ∩ R0.After r additions, the assumed violation would leave more than qt vertices, contradicting the existence of at most q vertices outside Ar dominating X(Ar).Source: §3.4 · p. 15

3.5 Preparing the LP

• The LP requires hitting every hyperedge of H′ and fractionally dominating R1; its integral optimum is at most (1 + ρ) MDS(G).The stronger constraints ensure an integral solution can be combined with P to dominate the original graph.Source: §3.5 · pp. 15, 18
• The reduced graph G′ keeps H vertices and R0, plus one representative per distinct nonempty R0-neighborhood outside those sets.C′, used only in the analysis, replaces omitted vertices by their representatives while preserving its LP solution and size bound.Source: §3.5 · p. 16
• Removing P leaves F, residual hyperedges H′ disjoint from P, and undominated requests R1 = R0 \ NG[P].The resulting structure has bounded degree and hypergraph rank and degree, and C′ \ P hits H′ and dominates R1.Source: §3.5 · pp. 16–17
• Any set S that hits H′ and dominates R1 makes P ∪ S a dominating set of G.P handles already-dominated vertices, while S handles residual hyperedges and requests.Source: §3.5 · p. 18
• The constraint matrix has row sums at most max{r, Γ + 1} and column sums at most B1 + Γ + 1.Hitting constraints use at most r variables, and domination constraints use at most Γ + 1; variable appearances are bounded using H′ degree B1 and F degree Γ.Source: §3.5 · p. 18

3.6 Using the LP algorithm

• The incidence-network LP algorithm gives a (1 + ρ)-approximation when the matrix has no zero row and bounded row and column sums.Its round bound is O(ρ^-4 log M log Q), where M and Q bound those sums.Source: §3.6 · p. 18
• The hypergraphs, reduced graphs, and sets needed for the residual LP are computed in a constant number of rounds, independent of ρ.The local computation is polynomial for fixed d, β, b, and ρ.Source: §3.6 · pp. 18–19
• One incidence-network round can be simulated in at most two rounds on G, preserving the residual LP algorithm’s asymptotic running time.Constraint simulators are within distance two of their variable simulators in G.Source: §3.6 · pp. 18–19
• The local computation is polynomial in the view size for fixed parameters, although its exponent may depend on d, β, b, and ρ.Vertices enumerate bounded-size sets and hyperedge families during the construction.Source: §3.6 · p. 19
• The residual LP has a fractional solution computable in O_d,β,b(ρ^-4 log(1/ρ)^2) LOCAL rounds, with polynomial local computation for fixed parameters.Its solution follows by approximating an LP whose integral optimum is at most (1 + ρ) MDS(G).Source: §3.6 · p. 19

3.7 Taking care of the additive bound in the density

• The algorithm returns a dominating set of size at most a constant times the optimum plus a small additive term, in O_d,β,b(ρ^-4 log(1/ρ)^2) rounds.It uses polynomial local computation for fixed d, β, b, and ρ.Source: §3.7 · p. 20
• An α MDS(G) + λ bound can be converted to an (α + δ)-approximation in T + O(1 + λ/δ) rounds.The conversion preserves polynomial local computation for fixed λ and δ.Source: §3.7 · p. 20
• When MDS(G) ≤ h, vertices see the whole graph and choose the same canonical minimum dominating set; otherwise λ ≤ δ MDS(G).Here h = max{1, ⌈λ/δ⌉}; the local search adds O(h) rounds and is polynomial for fixed λ and δ.Source: §3.7 · p. 20

3.8 Putting the algorithm together

• For fixed d, β ≥ 1, and ε > 0, a deterministic constant-round LOCAL algorithm achieves a (d + 1 + ε)-approximation when mad(G) ≤ d and ∇1(G) ≤ β.Its round complexity is O_d,β(ε^-4 log(1/ε)^2), with polynomial local computation for fixed d, β, and ε.Source: §3.8 · p. 21

3.9 Tightness

• For every even integer d ≥ 2, the factor d + 1 is sharp as an infimum for deterministic constant-round LOCAL approximation.The lower bound uses powers of paths and their hereditary closures, which have bounded expansion and maximum average degree at most d.Source: §3.9 · p. 21

Bounded Euler genus

• A (7 + ε)-approximation is achieved in constant rounds for graphs of Euler genus at most g, including planar graphs, and is optimal up to ε.The algorithm needs no embedding and has polynomial local computation for fixed g and ε.Source: §4 · pp. 21–22

Triangle-free graphs of bounded Euler genus

• A (5 + ε)-approximation is achieved in constant rounds for triangle-free graphs of Euler genus at most g, including triangle-free planar graphs, and is optimal up to ε.The algorithm needs no embedding and has polynomial local computation for fixed g and ε.Source: §4 · p. 22

Further tight bounds

• For each fixed integer k ≥ 1 and ε > 0, deterministic LOCAL algorithms achieve approximation ratios on the stated graph classes, without requiring a layout or decomposition as input.For fixed k and ε, the algorithms run in O_k(ε^-4 log(1/ε)^2) rounds and use polynomial local computation; all are tight up to the ε term. Bounded queue-number and stack-number classes are not contained in any proper minor-closed class.Source: §4 · p. 22

Fractional domination

• Can the (d + 1 + ε) MDS(G) guarantee be strengthened to (d + 1 + ε) MDSf(G) for bounded ∇1 graphs?A fractional version of the set C construction could suffice; Amiri and Siebertz obtain this result for proper minor-closed classes [AS26].Source: §5 · p. 23

Weaker sparsity assumptions

• Which structural parameter weaker than bounded ∇1 suffices for a deterministic constant-round LOCAL (d + 1 + ε)-approximation when mad(G) ≤ d?The ∇1 bound cannot simply be dropped: graphs of arboricity two rule out a constant-factor constant-round approximation.Source: §5 · p. 23

Exact approximation value

• For real d ≥ 2, does some class with mad(C) ≤ d and bounded ∇1(C) rule out every constant-round ratio below d + 1?Source: §5 · p. 23
• Can the ε term be removed from the d + 1 + ε approximation ratio, and can the planar 7 + ε guarantee become a 7-approximation?The latter question remains open [AS26, Section 9].Source: §5 · p. 23

Small messages

• Does Corollary 1.1 hold in CONGEST, despite the algorithm's reliance on very large messages to gather neighborhoods and enumerate hyperedge constraints?Even a 7 + ε approximation in constant CONGEST rounds on planar graphs remains open [AS26, Section 9].Source: §5 · p. 24

Declaration of AI use

• The declaration marks approach development, proof development, and other supporting tasks as AI-assisted, but not the research question, writing, or bug checking.Source: Declaration of AI use · p. 24