PaperlayerView exact revision on arXiv

Source-linked AI summary

Almost Optimal Constant-Round Approximation of Dominating Set in Graph Classes with Excluded Minors

Saeed Amiri, Sebastian Siebertz

arXiv:2610.09618v1cs.DScs.DCcs.DM

TL;DR

Constant-round deterministic approximation for planar minimum dominating set had a gap between the lower bound 7 and the best ratio 8 + ε. This paper combines local clustering, fractional solutions, and rounding for proper minor-closed classes, obtaining guarantees whose limiting constants match lower bounds for several graph families.

  • Problem

    For planar graphs, constant-round deterministic dominating set algorithms had ratio 8 + ε despite a lower bound of 7, leaving the optimal infimum unresolved.

    Source: §1 · p. 2

  • Method

    The paper combines sparse clustering, local fractional domination solutions, derandomization, and threshold rounding for proper minor-closed classes.

    Source: §1.2 · p. 5, §9 · p. 24

  • Results

    For every proper minor-closed class C, deterministic rounding returns a dominating set of size at most (2a(C) + 1 + ε)γf(G), while the limiting infima are 7 for planar graphs and the listed bounded-genus, width, and minor-free classes.

    Source: §9 · p. 24

  • Takeaways & Limitations

    The guarantees and path-power lower bounds determine optimal limiting constants for planar, bounded-genus, bounded-width, and Kt-minor-free graphs with 3 ≤ t ≤ 9.

    Source: §8.4 · p. 21, §9 · p. 24

    For Kt-minor-free graphs with t ≥ 10, the infimum remains between 2t − 3 and 2at + 1.

    Source: §9 · p. 24

Abstract

from arXiv · show

For every fixed proper minor-closed class $\mathscr C$ and every $\epsilon>0$, we give a deterministic LOCAL algorithm that returns a dominating set of size at most $(2a(\mathscr C)+1+\epsilon)\gamma_f(G)$ on every $G\in\mathscr C$. Here $a(\mathscr C)$ is the supremum edge-to-vertex ratio in~$\mathscr C$, and $\gamma_f(G)$ is the fractional domination number. The class also admits a deterministic $(1+\epsilon)$-approximation for fractional dominating set and a randomized algorithm that always returns a dominating set and has expected size at most $(1+\epsilon)\gamma(G)$. In each case, the number of rounds depends only on $\mathscr C$ and~$\epsilon$. None of these algorithms requires the number of vertices or the maximum degree as part of the input. For planar graphs, this gives the deterministic guarantee $(7+\epsilon)\gamma_f(G)$. Together with the lower bound of Hilke, Lenzen and Suomela, it determines the infimum of the deterministic constant-round approximation ratios for planar minimum dominating set as~$7$, settling a question that had remained open since their work. The corresponding infima, measured against the integral optimum, are $7$ for graphs of Euler genus at most any fixed $g\ge0$, $2t-3$ for $K_t$-minor-free graphs with $3\le t\le9$, and $2r+1$ for graphs of treewidth or pathwidth at most any fixed $r\ge1$. We also prove that, for every integer~\mbox{$r\ge1$}, no deterministic constant-round LOCAL algorithm achieves an approximation ratio below~\mbox{$2r+1$} on the $r$-th powers of paths, even when every vertex knows the number of vertices. This gives a new proof that the limiting constants are optimal for planar graphs, graphs of bounded treewidth or pathwidth, and $K_t$-minor-free graphs with $3\le t\le9$. For triangle-free planar graphs, the corresponding infimum is $5$.

1 Introduction

Constant-round dominating set approximation on planar graphs had reached ratio 8 + ε against a lower bound of 7. This paper gives guarantees for proper minor-closed classes and matching limiting constants for several graph families, using local clustering and rounding.

1.3 Related work

  • Earlier planar algorithms improved from ratio 130 to 52, 20, 11 + ε, and 8 + ε, while prior degree-dependent methods could reach 7.Prior work also established the cluster-and-solve and randomized-contraction techniques adapted here.Source: §1 · p. 2, §1.3 · pp. 5–6

1.1 Our results

  • For every fixed proper minor-closed class C and ε > 0, a deterministic LOCAL algorithm returns, on every G ∈ C, a dominating set of size at most (2a(C)+1+ε)γf(G), using rounds depending only on C and ε.Source: §1.1 · p. 3

1 Introduction

  • The planar infimum is 7, closing the gap between the previous 8 + ε algorithm and the lower bound of 7.The lower bound comes from a triangular-grid construction; the earlier algorithms had only reached 8 + ε.Source: §1 · p. 2, §1.1 · p. 3

1.1 Our results

  • Against the integral optimum, deterministic constant-round approximation-ratio infima are 7 for fixed Euler-genus bounds, 2t − 3 for Kt-minor-free graphs (3 ≤ t ≤ 9), and 2r + 1 for fixed treewidth or pathwidth r ≥ 1.For triangle-free planar graphs, the infimum is 5.Source: §1.1 · pp. 3–4

1.2 Proof overview

  • Randomized heavy-star contraction bounds expected cluster-boundary cost, while local LP solutions and threshold rounding yield fractional and integral domination guarantees.Derandomization replaces each randomized selection indicator with its locally computable probability, producing a feasible fractional solution; rounding then gives a planar factor of 7.Source: §1.2 · p. 5

1.4 Organization

  • The paper develops the model and rounding bound, presents randomized clustering and domination, proves derandomization and density refinements, and then derives graph-class consequences and lower bounds.The paper concludes with open problems.Source: §1.4 · p. 7

2 Preliminaries

The preliminaries define domination and the LOCAL model, then establish the graph-class and fractional-domination tools used by the algorithms. They also recall a constant-round constant-factor starting algorithm for proper minor-closed classes.

LOCAL model and definitions

  • A fractional dominating set assigns nonnegative weights so every closed neighborhood has weight at least one, and its optimum γf(G) is at most γ(G).The indicator vector of any integral dominating set is feasible for the fractional linear program.Source: §2 · p. 7

Graph classes and density

  • Every a-sparse graph admits a fractional orientation with out-degree at most a, used for size bounds rather than computed by the algorithms.When a is an integer, flow integrality yields an ordinary orientation with maximum out-degree at most a.Source: §2 · p. 7
  • Proper minor-closed classes are closed under taking subgraphs, and their edge density supplies sparsity bounds used in the analysis.For classes closed under disjoint unions, asymptotic density agrees with supremum density; the passage notes that bounded-genus classes distinguish these quantities.Source: §2 · pp. 7–8

LOCAL model and definitions

  • In the LOCAL model, vertices communicate in synchronous rounds with arbitrary-size messages and unrestricted local computation, but an R-round output depends only on a bounded-radius view.Vertices initially lack the graph order and maximum degree; an effectively computable function of a fixed-radius view can be evaluated with one additional round.Source: §2 · p. 8

Starting algorithm

  • Every fixed proper minor-closed class has a deterministic constant-round LOCAL algorithm giving a constant-factor dominating set without requiring graph order or maximum degree as input.For planar graphs, the cited explicit starting algorithm has factor 52 and round complexity T0.Source: §2 · p. 9

3 The rounding lemma

Threshold rounding converts a fractional dominating set on a sparse graph into an integral one with a controlled size increase. When the threshold comparisons are locally computable, this conversion adds only one communication round.

Size guarantee

  • (2a+1)|x| bounds the size of a dominating set obtained by rounding a fractional solution x on an a-sparse graph.The threshold is θ = 1/(2a+1); vertices meeting it enter D1, and uncovered vertices are added to D2.Source: §3 · pp. 9–10

Planar consequence

  • For planar graphs, γ(G) ≤ 7γf(G).This follows by applying the sparse-graph rounding bound with planar sparsity a = 3.Source: §3 · pp. 9–10

Distributed implementation

  • One additional round suffices to produce a dominating set of size at most (2a+1)ρ·OPT when an R-round algorithm supplies a ρ-approximate fractional solution and threshold comparisons are locally computable.This condition holds when a is a known positive rational and the solution entries are rational.Source: §3 · pp. 9–10

4 Randomized clustering

The clustering procedure repeatedly merges parts along selected heavy edges while preserving bounded-radius parts and the minor-closed class. Random choices make the total weight of edges between parts decrease geometrically in expectation.

Boundary-weight reduction

  • The expected weight of edges between parts contracts by a factor q = 1 − 1/(8a) per level, giving a geometric decrease after L levels.The contraction estimate applies conditionally on the preceding levels and uses the sparsity bound on each quotient.Source: §4 · pp. 10, 12

Star-contraction process

  • Each part selects a heaviest incident edge, reciprocal choices are resolved by identifiers, and fair leader coins select arcs from tail parts to head parts for merging.Each head absorbs selected incoming tails; other parts remain unchanged.Source: §4 · p. 10

Structural guarantees

  • At every level the parts partition the vertices, remain connected, and have bounded radius, so their simple quotient remains in the minor-closed class.The radius recurrence is rt = 3rt−1 + 1.Source: §4 · pp. 10–11

Weight of selected arcs

  • For planar graphs, the selected arc weight is at least w(Q)/6, recovering the earlier planar estimate.The argument extends the heaviest-edge selection bound to a-sparse graphs using fractional orientations.Source: §4 · pp. 11–12

Local implementation

  • A vertex can reconstruct its entire final part and leader from a view of radius ρL, enabling implementation in ρL + 1 rounds.The stated radius is ρt = 2(3^t − 1).Source: §4 · p. 13

5 The randomized algorithm

The randomized algorithm forms a quotient from groups around an initial dominating set, clusters it, and solves domination separately within each lifted cluster. Boundary repairs ensure feasibility, while the analysis controls their cost using the clustering boundary.

Feasibility and repair

  • Both variants return feasible global solutions for every coin outcome by solving within clusters and repairing boundary effects.The repair argument restricts a global optimum to each cluster and adds the leaders of boundary groups.Source: §5 · pp. 13–15

Algorithm construction

  • The algorithm groups vertices around an initial dominating set, forms a simple quotient in the class, and uses a common random partition before solving each cluster problem.It chooses either a minimum integral dominating set or an optimal fractional solution within each cluster.Source: §5 · pp. 13–14

Boundary cost

  • The number of boundary-group leaders is at most twice the number of quotient edges crossing final parts.Each crossing edge has two endpoints, and a boundary leader is an endpoint of such an edge.Source: §5 · p. 14

Output bounds

  • The integral and fractional cluster outputs are bounded by their respective global optima plus the number of boundary-group leaders.The passage states these bounds for every coin outcome.Source: §5 · p. 14

Round complexity

  • For L clustering levels, the algorithm uses at most L independent fair coins per vertex and runs in at most TC + 9·3^L rounds.Choosing L sufficiently large as a function of the class and ε yields the paper’s randomized guarantee.Source: §5 · p. 15

6 Derandomization

The section derandomizes fractional domination by having each vertex compute the exact expectation of its randomized output coordinate. Combined with threshold rounding, this yields constant-round guarantees for integral and fractional domination on each fixed proper minor-closed class.

Derandomization principle

  • Rational outputs and a finite, locally prescribed coin budget let each vertex compute its output coordinate’s expectation exactly.The computation simulates every assignment of coins in the vertex’s R-view, requiring R + 1 rounds.Source: §6 · p. 16

Theorem 6.2

  • Threshold rounding converts a fractional solution into an integral dominating set, with the bound determined by the class’s edge density.The proof uses a rational threshold slightly below 1/(2a + 1) to avoid exact comparisons with a possibly unspecified real density.Source: §6 · pp. 16–17
  • (1 + ε)γ(G) bounds the expected size of a randomized algorithm that always returns a dominating set.Its number of rounds depends only on the class and ε.Source: §6 · p. 17
  • (1 + ε)γf(G) bounds the weight of the rational fractional dominating set returned by a deterministic LOCAL algorithm.The derandomized algorithm computes expected output coordinates exactly in one additional round.Source: §6 · pp. 16–17
  • (2a + 1 + ε)γf(G) bounds the deterministic dominating-set size on every graph in the class.The deterministic algorithm uses a number of rounds depending only on the class and ε.Source: §6 · pp. 16–17

Uniformity

  • The algorithms require neither the graph order nor the maximum degree as input; arbitrary fixed classes need not have computable density descriptions.Uniformity in ε follows when rational upper approximations to the density can be computed; planar graphs have specified density 3.Source: §6 · p. 17

7 Rounding with an additive excess

This section extends threshold rounding to graphs whose edge count exceeds a linear density bound by a fixed additive amount. The resulting deterministic LOCAL guarantee uses asymptotic density and the integral domination optimum.

Rounding with excess

  • A fixed additive excess in |E(G)| ≤ d|V(G)| + b permits rounding with a factor 2d + 1 and an additive error.An additive-error reduction yields a multiplicative guarantee against γ(G), using asymptotic density.Source: §7 · p. 18
  • The extra cost is controlled by Φ_d(G), the total out-degree excess above d in a fractional orientation.The proof bounds this excess using an orientation obtained through a max-flow/min-cut argument.Source: §7 · p. 18
  • On d-sparse graphs, Φ_d(G) is zero and the earlier threshold-rounding bound is recovered.On general graphs some excess allowance is necessary: for K8, the threshold output has eight vertices although 7|x| is seven.Source: §7 · pp. 18–19
  • The rounding rule selects vertices with x_v ≥ 1/(2d + 1), then adds vertices not dominated by that selection.With exact rational comparisons, this construction is computable in one LOCAL round.Source: §7 · pp. 18–19

Corollary 7.3

  • (2d*(C) + 1 + ε)γ(G) bounds a deterministic constant-round dominating set on every graph in a proper minor-closed class.The bound uses the class’s asymptotic density rather than its largest edge density.Source: §7 · pp. 18–19

8 Sharp bounds and further consequences

The paper applies its density-based algorithms to planar, bounded-genus, and excluded-minor classes, and proves matching lower bounds for several families. These results determine optimal limiting constants for planar graphs, fixed Euler-genus bounds, selected excluded-clique classes, and bounded treewidth or pathwidth.

8.2 Subclasses of planar graphs

  • 5 is the infimum for triangle-free planar graphs, whose dominating-set guarantee is (5 + ε)γf(G).The square-grid lower bound matches this guarantee.Source: §8.2 · p. 20

8.3 Bounded Euler genus

  • For every fixed Euler-genus bound g, the integral-optimum infimum is 7; when g ≤ 2, the guarantee also holds against γf(G).The (7 + ε)γ(G) guarantee is independent of g in its approximation ratio.Source: §8.3 · p. 21

8.4 Excluded minors and lower bounds from path powers

  • Theorem 8.7 rules out deterministic constant-round ratios below 2r + 1 on r-th powers of paths, even when vertices know n.These graphs have pathwidth r and exclude K_{r+2} as a minor; the lower bound supplies sharp constants for several graph classes.Source: §8.4 · pp. 21, 22, 24
  • For integers 3 ≤ t ≤ 9, the cited result gives a 2t − 3 + ε approximation ratio on K_t-minor-free graphs.For ordinary minimum dominating set approximation, the infimum of achievable deterministic constant-round ratios in this range is 2t − 3.Source: §8.4 · p. 23
  • (2r + 1 + ε)γf(G) is the guarantee for graphs of treewidth at most r; the integral-optimum infimum is 2r + 1 for treewidth and pathwidth at most r.The path-power lower bound establishes the matching limiting constant.Source: §8.4 · pp. 23–24
  • The paper also gives (t + 2 + ε)γf(G) for K_{2,t}-minor-free graphs and (7 + ε)γf(G) for K5- and K3,3-minor-free graphs.The K5- and K3,3-minor-free classes have integral-optimum infimum 7.Source: §8.4 · p. 23

9 Conclusion and open problems

Combining established distributed techniques yields approximation guarantees for proper minor-closed graph classes and determines several optimal limiting ratios. The conclusion also identifies open questions about approximation bounds, round complexity, and model assumptions.

Conclusion

  • For each proper minor-closed class, adapted techniques yield a deterministic fractional (1+ε)-approximation and dominating-set bounds of (2a(C)+1+ε)γf(G) and (2d*(C)+1+ε)γ(G).The analysis compares fractional cluster solutions with the global fractional optimum and accounts for additive density excess.Source: §9 · p. 24
  • Together with lower bounds from powers of paths, these guarantees determine infima of deterministic constant-round approximation ratios for planar, fixed Euler-genus, treewidth/pathwidth-at-most-fixed-r≥1, and K_t-minor-free graphs (3≤t≤9); the planar infimum is 7.Source: §9 · p. 24

Open problems: Excluded minors

  • For K_t-minor-free graphs with t ≥ 10, the infimum remains between 2t−3 and 2a_t+1; for K_2,t-minor-free graphs with t ≥ 4, it lies in [5, min{t+2, 50}].The density refinement gives no further improvement for K_t-minor-free graphs because the class is closed under disjoint unions.Source: §9 · p. 24

Open problems: The exact ratio

  • Whether a deterministic constant-round algorithm attains ratio exactly 7 on every planar graph remains open.The round bound grows as ε tends to zero, while the lower bound excludes only ratios strictly below 7.Source: §9 · p. 24

Open problems: Round complexity and probability

  • Open questions include optimal ε-dependence for expected and deterministic fractional approximations, and γ(G)-conditions for high-probability 1+ε algorithms.The probability question asks when failure probability at most n−c is achievable for a prescribed constant c > 0.Source: §9 · p. 24

Open problems: Efficient deterministic algorithms

  • It remains open whether the polynomial round bounds can be substantially reduced or the guarantees achieved with local computation polynomial in each collected neighborhood.Source: §9 · p. 25

Open problems: Network models

  • Open questions include the optimal deterministic ratio on anonymous planar networks and whether CONGEST permits a constant-round (7+ε)-approximation.The CONGEST question specifies O(log n) bits per edge per round.Source: §9 · p. 25

Open problems: Planar subclasses

  • For planar graphs of girth at least g ≥ 5, determining the infimum of deterministic constant-round ratios remains open.Source: §9 · p. 25
Loading 2610.09618v1…