betaFeedback

WorksComputer Science

Paying for Fractional Error: Tight Constant-Round Approximation of Covering Problems with Short Broadcasts

Abstract

We present a general framework for deterministic constant-round approximation of covering problems in sparse networks in the broadcast CONGEST model, where every vertex broadcasts the same O(log⁡n)O(\log n)-bit message to all its neighbors. The framework combines two independent tools. The first is a solver that computes a (1+δ)(1+δ)-approximate solution of any local covering linear program with bounded positive integer costs on every class that excludes a fixed minor. The second is a rounding principle: a rounding rule that saves a fixed fraction of its own output, for every feasible input, pays for a solver error fixed in advance, so that an approximate fractional solution yields an exact coefficient. For ordinary domination, we achieve a 2a+12a+1 approximation against the fractional optimum γf(G)γ_f(G) for every fixed rational a≥1a\ge1, whenever every minor has a ratio of edges to vertices of at most aa. On planar graphs this is seven, matching the lower bound of Hilke, Lenzen, and Suomela. The coefficients are also optimal at bounded treewidth and pathwidth, for KtK_t-minor-free graphs with 3≤t≤93\le t\le9, on triangle-free planar graphs (five), and on planar graphs of large girth, where it approaches the optimal three. On every fixed surface the exact bound is 7γ(G)7γ(G), and we show that a bound of 7γf(G)7γ_f(G) is impossible on some fixed surfaces even sequentially. For total domination, on graphs without isolated vertices and under the same minor-density assumption, the exact coefficient is 2a2a against the fractional optimum, including the optimal six on planar graphs. Red-blue domination, and hence set cover and hitting set on planar incidence graphs, has the optimal limiting coefficient four. Our method also gives randomized constant-round and deterministic O(log⁡∗n)O(\log^* n)-round (1+ε)(1+\varepsilon)-approximation schemes, with the randomized cost guarantee holding in expectation.

Introduction

Many graph problems ask for a small set of vertices that meets a requirement near every vertex, including dominating set, total domination, and set cover on an incidence graph. In a distributed network, the graph also carries the messages, so a fast algorithm must make good local choices with the information that the vertices can exchange. Even a neighborhood of bounded radius may contain arbitrarily many vertices, which makes this a communication problem as well as an approximation problem.

We present a new, very general framework for local covering problems on sparse networks, with a fractional solver and a rounding principle that together achieve exact approximation coefficients. The algorithms work in the broadcast CONGEST model, where each vertex sends the same O(log⁡n)O(\log n)-bit message to all neighbors in a round, even when its degree is unbounded. Vertices have distinct O(log⁡n)O(\log n)-bit identifiers, and local computation is unrestricted. We obtain optimal coefficients against the fractional optimum for domination on several sparse classes and for total domination on planar graphs. Our results settle the question of the optimal approximation factors after a long sequence of improvements in distributed algorithms, and they do so even in the restrictive broadcast CONGEST model. For planar red-blue domination, the optimal limiting coefficient is four, with upper bound 4+ε4+\varepsilon for every fixed ε>0\varepsilon> 0. On graphs of any fixed Euler genus, we also achieve 7γ(G)7\gamma(G) without an embedding. However, we show that on some surfaces 7γf(G)7\gamma_f(G) is impossible even for sequential algorithms.

The planar question. Lenzen, Oswald, and Wattenhofer [47] initiated constant-round planar domination, and the best coefficient improved from 130 [48] through 52 [64], 11 + ε\varepsilon [36], and 8 + ε\varepsilon [66] to 7 + ε\varepsilon in the LOCAL model [6], where message sizes are unbounded. Hilke, Lenzen, and Suomela [33] ruled out every coefficient below seven for deterministic constant-round algorithms, even with unbounded messages. However, for the bounds 11 + ε\varepsilon, 8 + ε\varepsilon, and 7 + ε\varepsilon, the number of rounds depends on ε\varepsilon. Also, in the (7 + $\varepsilon)-approximation of Amiri and Siebertz [6], the treatment of cluster boundaries leaves a positive error for fixed parameters, so this approach does not give the exact coefficient seven and it seems unlikely that it can be adapted to achieve the optimum. In this work we finally close this gap even in the more restrictive broadcast CONGEST model by computing a dominating set DD satisfying

∣D∣≤7γf(G)≤7γ(G),|D| \le7\gamma_f(G) \le7\gamma(G),

where γ(G)\gamma(G) is the minimum size of a dominating set and γf(G)\gamma_f(G) is the fractional optimum, assigning nonnegative weights so that each closed neighborhood receives at least one in total.

A new framework for local covering problems

We present a new framework with two separate parts: a distributed solver that computes an approximately optimal fractional cover with short messages, and a rounding method that turns this cover into an integral solution with an exact approximation coefficient. The solver works on every class that excludes a fixed minor, and also gives integral approximation schemes. This separation lets the same communication procedures handle ordinary and total domination, restricted covering, and set cover and hitting set on sparse incidence graphs.

A solver for local covering programs. We consider the following setting. Each demand rr specifies a nonempty set C(r)C(r) of allowed candidates in its closed neighborhood. Each candidate vv knows its positive integer cost cv∈{1,…,b}c_v \in\{1,\ldots,b\} for a fixed bound bb. Every vertex knows whether it is a demand. For each demand rr and neighboring candidate vv, both vertices know whether vv is allowed to cover rr, and each demand also knows whether it can cover itself. This setting covers open neighborhoods, partial domination, forbidden candidates, and directed covering relations. We write the minimum fractional cost as

τc=min⁡{∑vcvxv:x≥0, ∑v∈C(r)xv≥1 for every demand r}.\tau_c = \min\left\{\sum_v c_vx_v : x \ge0,\ \sum_{v\in C(r)}x_v \ge1\text{ for every demand }r\right\}.

and let OPTc\mathrm{OPT}_c be the minimum cost of an integral cover. Distributed LP methods were developed in [45, 43], but, to our knowledge, no constant-round (1+δ)(1+\delta)-solver for these programs was known with short messages and unbounded degrees.

For rational a≥1a \ge1, let Ca\mathcal{C}_a be the class of graphs whose nonempty minors JJ satisfy ∣E(J)∣≤a∣V(J)∣|E(J)| \le a|V(J)|. In the following, density or sparsity will always mean the ratio of edges to vertices. Every class excluding a fixed minor lies in some Ca\mathcal{C}_a by a classical result of Mader [53], and planar graphs lie in C3\mathcal{C}_3. Our first main theorem is the following.

Theorem A. For fixed rationals ρ≥1\rho\ge1 and δ>0\delta> 0, and a fixed integer b≥1b \ge1, there is an algorithm that computes a feasible fractional cover of cost at most (1+δ)τc(1+\delta)\tau_c on every G∈CρG \in\mathcal{C}_\rho in a constant number of deterministic broadcast CONGEST rounds. The algorithm requires no auxiliary graph structure, degree bound, or knowledge of the graph order.

We explain the main ideas in § 2 and give full proofs in the main body of the paper. In a nutshell, the solver forms local covering tasks of bounded diameter that admit a cover of bounded cost. It finds short descriptions of local solutions and combines them into a near-optimal fractional cover, using only short broadcasts. The solver still introduces a small approximation error, and our second tool uses a saving in the rounding step to compensate for this error.

Paying for fractional error. The second tool uses the saving from rounding to absorb the error of the fractional solver. We say that a local rounding rule producing a set D(x)D(x) from a feasible fractional cover xx has slack δ>0\delta> 0 if

C(x)≥(1+δ)∣D(x)∣C(x) \ge(1+\delta)|D(x)|

for every feasible xx. Here C(x)=∑vcvxvC(x)=\sum_v c_vx_v is the cost of the fractional cover. The saving is proportional to ∣D(x)∣|D(x)| and holds for every feasible input, which allows us to use an approximately optimal solution.

Theorem B. Let a rounding rule have slack δ>0\delta> 0 on a covering program with fractional optimum τ\tau. Then every feasible xx with C(x)≤(1+δ)τC(x) \le(1+\delta)\tau satisfies ∣D(x)∣≤τ|D(x)| \le\tau. For dominating set on graphs of minor density at most a rational a≥1a \ge1, there is a transformation of the instance, computable in a constant number of broadcast rounds, after which threshold rounding has slack at least

δa=12a(2a+1)2\delta_a = \frac{1}{2a(2a+1)^2}

if 2a2a is an integer,

δa=min⁡{1−θa(a+1),θ⌊2a⌋+1}\delta_a = \min\left\{\frac{1-\theta}{a(a+1)},\frac{\theta}{\lfloor2a\rfloor+1}\right\}

otherwise,

where θ=2a−⌊2a⌋.\text{where }\theta=2a-\lfloor2a\rfloor.

The transformed fractional optimum is at most (2a+1)γf(G)(2a+1)\gamma_f(G) minus the number of vertices already selected. If 2a2a is not an integer, it suffices that all subgraphs have a ratio of edges to vertices of at most aa.

The first assertion follows from (1+δ)∣D(x)∣≤C(x)≤(1+δ)τ(1+\delta)|D(x)| \le C(x) \le(1+\delta)\tau. The second shows how to obtain the required saving for domination: when 2a2a is an integer, we first select the regions where the usual rounding bound could be tight, and assign the remaining candidates costs that record the budget left by this selection. When 2a2a is not an integer, the gaps between 2a2a and integer degrees give the saving directly. The solver accuracy can therefore be fixed independently of the input graph, and its error disappears from the final coefficient. For each new application, we need to bound the transformed fractional optimum and prove the rounding saving. The solver can then be reused. The tools also work separately, since the solver gives approximation schemes. Section 7 proves the general domination construction in Theorem B.

Exact coefficients for domination

We combine the tools to obtain coefficients determined by minor density, or by a smaller subgraph-density bound when 2a2a is noninteger. The planar case gives seven, while larger girth and other sparse classes give the following guarantees.

Theorem C. There exist deterministic constant-round broadcast CONGEST algorithms that return a dominating set DD with the following guarantees.

(i) For fixed rational a≥1a \ge1 and G∈CaG \in\mathcal{C}_a, the output satisfies ∣D∣≤(2a+1)γf(G)|D| \le(2a+1)\gamma_f(G).

(ii) For fixed rationals 1≤a≤ρ1 \le a \le\rho with 2a2a noninteger, the same bound holds for G∈CρG \in\mathcal{C}_\rho if every subgraph has a ratio of edges to vertices of at most aa.

(iii) For planar GG of girth at least a fixed integer g≥3g \ge3, we have ∣D∣≤(3+4/(g−2))γf(G)|D| \le(3+4/(g-2))\gamma_f(G).

The algorithms require no embedding, orientation, initial cover, degree bound, or knowledge of nn.

A planar graph of girth at least gg has subgraph density at most g/(g−2)g/(g-2), so part (ii) gives the girth bound except at g∈{3,4,6}g \in\{3,4,6\}. The case g=3g=3 follows from minor density, while girths four and six require a face-counting argument because contractions can create shorter cycles. Section 5.4 presents the planar construction, while Section 7 and Appendix A prove the general and high-girth bounds. As a corollary we obtain the optimal bounds in several important cases.

Corollary 1.1. The coefficients 7 on planar graphs and on graphs of Euler genus at most two, 5 on triangle-free planar graphs, 2r+12r+1 on graphs of treewidth or pathwidth at most r≥1r \ge1, and 2t−32t-3 for KtK_t-minor-free graphs, 3≤t≤93 \le t \le9, are optimal for deterministic constant-round algorithms. The lower bounds hold even in the LOCAL model and with respect to γ(G)\gamma(G).

For surfaces, this corollary gives 7γf(G)7\gamma_f(G) only up to Euler genus two, while Theorem E below gives 7γ(G)7\gamma(G) for every fixed Euler genus.

Graph classBound on ∣D∣|D|Optimal coefficient?
Planar7γf7\gamma_fYes
Triangle-free planar5γf5\gamma_fYes
Treewidth or pathwidth at most rr(2r+1)γf(2r+1)\gamma_fYes
KtK_t-minor-free, 3≤t≤93 \le t \le9(2t−3)γf(2t-3)\gamma_fYes
Every minor has density at most aa(2a+1)γf(2a+1)\gamma_fClass-dependent
Euler genus at most fixed ee7γ7\gammaYes

Table 1. Deterministic constant-round domination guarantees in broadcast CONGEST. The lower bounds in the rows marked optimal hold in the LOCAL model and against the integral optimum.

The lower bounds come from [33] for planar graphs and [6] for powers of paths. For triangle-free planar graphs, Bonamy, Cook, Groenland, and Wesolek [11] observed that large grids rule out every coefficient below five and conjectured that five could be achieved. Our theorem proves this conjecture and achieves the coefficients previously approached within ε\varepsilon in LOCAL [6]. The proof of Corollary 1.1, including the tight lower bounds, is given in Appendix § 12.2.

To the best of our knowledge, constant-round constant-factor approximations in broadcast CONGEST were previously known for bounded-genus graphs, but not for general excluded-minor classes; see § 3. Our framework therefore extends these guarantees to a broader family of graph classes, while also giving exact approximation coefficients. We must admit that this makes us quite proud, even though we were AI assisted on the final meters.

Schemes and general covering

The same construction also gives integral approximation schemes, using random bits in constant rounds or a deterministic partition in O(log⁡∗n)O(\log^{*} n) rounds, which is of independent interest.

Theorem D. For fixed rational ρ≥1\rho\ge1, integer b≥1b \ge1, and ε>0\varepsilon> 0, the following guarantees hold on every G∈CρG \in\mathcal{C}_{\rho}:

(i) There exists a randomized algorithm that computes an integral cover that is always feasible and has expected cost at most (1+ε)OPT⁡c(1+\varepsilon)\operatorname{OPT}_{c} in a constant number of broadcast CONGEST rounds.

(ii) If vertices know a common polynomial bound on the identifiers, there exists a deterministic algorithm that computes a feasible integral cover of cost at most (1+ε)OPT⁡c(1+\varepsilon)\operatorname{OPT}_{c} in O(log⁡∗n)O(\log^{*} n) broadcast CONGEST rounds.

The constants in the round bounds depend only on ρ,b,ε\rho,b,\varepsilon.

For domination, both schemes were known in LOCAL [6, 22] while our algorithms use short broadcasts and apply to all the stated covering problems with bounded costs. A direct adaptation of the argument of Lenzen and Wattenhofer [50] shows that the deterministic round bound is necessary already on cycles: for every fixed 0<ε<1/40 < \varepsilon< 1/4, approximation within 1+ε1+\varepsilon requires Ω(log⁡∗n)\Omega(\log^{*} n) rounds even in LOCAL. We present this observation in Appendix § 12.3 (Proposition C.1).

Other covering problems. Appendix D gives a general rounding rule with coefficient 2a+1+ε2a+1+\varepsilon, or 2a+ε2a+\varepsilon when no demand covers itself, against τc\tau_c, where every subgraph of the covering-incidence graph has a ratio of edges to vertices of at most aa. This includes weighted, partial, restricted, directed, total, and red-blue domination (Corollary D.1). For set cover and hitting set on planar incidence graphs the coefficient is 4+ε4+\varepsilon, with no bound on set sizes or element frequencies, and Theorem D also gives approximation schemes. The stronger total-domination results appear in Appendix § 12.6, the red-blue results in Appendix § 12.8, and further high-girth bounds in Appendices E and G.

Fixed surfaces

On every fixed surface, the framework achieves the same exact coefficient as in the planar case, with the integral optimum as benchmark.

Theorem E. For every fixed e≥0e \ge0, there is a deterministic constant-round broadcast CONGEST algorithm that returns a dominating set DD with ∣D∣≤7γ(G)|D| \le7\gamma(G) on every graph GG of Euler genus at most ee. The algorithm works on orientable and nonorientable surfaces and does not need an embedding.

The proof is given in § 9. Seven is optimal for deterministic constant-round algorithms, and on some fixed surfaces even a sequential algorithm cannot guarantee 7γf(G)7\gamma_f(G), so we cannot replace γ(G)\gamma(G) by γf(G)\gamma_f(G) in this theorem (Proposition I.1 in Appendix § 12.9).

Organization. § 2 explains the main ideas of the framework and its planar application. § 4 introduces the notation, and § 5 presents the framework and its planar application. Detailed proofs, further applications, and lower bounds appear in the subsequent sections and appendices.

An intuitive overview of the framework

In this section we explain how the fractional solver and the rounding principle work together. The solver is the same in all applications, while each application chooses its first selection, its costs, and its rounding rule. Let us begin with this connection and the planar example, before explaining how short messages are enough to find the fractional solution.

Transferring the budget before rounding

We first select a set FF of vertices by a local rule and then define a new covering problem, whose demands, candidates, and costs depend on this selection. For ordinary domination, the demands are the vertices not covered by FF, and every vertex outside FF remains a candidate, even if it is already covered. Other applications may keep additional demands or restrict the candidates. Write C(x)=∑vc(v)xvC(x) = \sum_v c(v)x_v for the cost of a feasible fractional cover of this new problem, and let τ′\tau' be its minimum fractional cost, with ∣F∣|F| counted separately.

The rounding must compensate for the error of the fractional solver. Suppose rounding xx gives a set D(x)D(x) such that F∪D(x)F \cup D(x) covers the original instance. To obtain a target coefficient α\alpha against a benchmark B(G)B(G) for the original problem, we need to show that

∣F∣+τ′≤αB(G),(1+δ)∣D(x)∣≤C(x)for every feasible x,|F| + \tau' \le\alpha B(G), \qquad(1+\delta)|D(x)| \le C(x) \quad\text{for every feasible } x,

where δ>0\delta> 0 is fixed for the graph class. The solver returns a feasible vector with C(x)≤(1+δ)τ′C(x) \le(1+\delta)\tau', so the second inequality gives ∣D(x)∣≤τ′|D(x)| \le\tau', and the first gives

∣F∪D(x)∣≤∣F∣+∣D(x)∣≤αB(G).|F \cup D(x)| \le|F| + |D(x)| \le\alpha B(G).

Thus the solver may make a fixed positive relative error, because the rounding saves the same fraction of its output size. The selection, the costs, and the rounding must all be computed in a constant number of broadcast CONGEST rounds.

We show that the saving is large enough by using the same quantities to bound the saving from below and the size of the rounded solution from above. For nonnegative quantities Si(x)S_i(x), suppose fixed positive constants αi,βi\alpha_i,\beta_i satisfy

C(x)−∣D(x)∣≥∑iαiSi(x),∣D(x)∣≤∑iβiSi(x).C(x) - |D(x)| \ge\sum_i \alpha_i S_i(x), \qquad|D(x)| \le\sum_i \beta_i S_i(x).

References

  1. [2][AF26] Sharareh Alipour and Ermiya Farokhnezhad. Distributed dominating set with optimal rounds and message size in bounded arboricity graphs. In Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 333-340. ACM, 2026. doi:10.1145/3816782.3819190.DOI
  2. [4][Ami21] Saeed Akhoondian Amiri. Deterministic CONGEST algorithm for MDS on bounded arboricity graphs, 2021. arXiv:2102.08076.arxiv.org/abs/2102.08076
  3. [5][AS16] Saeed Akhoondian Amiri and Stefan Schmid. Brief announcement: A log*-time local MDS approximation scheme for bounded genus graphs. In Distributed Computing, 30th International Symposium (DISC 2016), volume 9888 of Lecture Notes in Computer Science, pages 480-483. Springer, 2016. schmiste.github.io/disc16ds.pdf.
  4. [6][AS26] Saeed Amiri and Sebastian Siebertz. Almost optimal constant-round approximation of dominating set in graph classes with excluded minors, 2026. arXiv:2610.09618.arxiv.org/abs/2610.09618
  5. [7][ASS19] Saeed Akhoondian Amiri, Stefan Schmid, and Sebastian Siebertz. Distributed dominating set approximations beyond planar graphs. ACM Transactions on Algorithms, 15(3):39:1-39:18, 2019. doi:10.1145/3326170.DOI
  6. [8][AST90] Noga Alon, Paul Seymour, and Robin Thomas. A separator theorem for nonplanar graphs. Journal of the American Mathematical Society, 3(4):801-808, 1990. www.ams.org/jams/1990-03-04/S0894-0347-1990-1065053-0/, doi:10.1090/S0894-0347-1990-1065053-0.DOI
  7. [9][AW22] Saeed Akhoondian Amiri and Ben Wiederhake. Distributed distance-r covering problems on sparse high-girth graphs. Theoretical Computer Science, 906:18-31, 2022. Conference version in Algorithms and Complexity (CIAC 2021), Lecture Notes in Computer Science, vol. 12701, pp. 37-60, Springer, 2021. doi:10.1016/j.tcs.2022.01.001.DOI
  8. [10][Bak94] Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, 41(1):153-180, 1994. doi:10.1145/174644.174650.DOI
  9. [11][BCGW21] Marthe Bonamy, Linda Cook, Carla Groenland, and Alexandra Wesolek. A tight local algorithm for the minimum dominating set problem in outerplanar graphs. In 35th International Symposium on Distributed Computing (DISC 2021), volume 209 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1-13:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.13, doi:10.4230/LIPIcs.DISC.2021.13.DOI
  10. [12]Marthe Bonamy, Cyril Gavoille, Avinandan Das, Jukka Suomela, Timothé Picavet, and Alexandra Wesolek. Meta-theorems for cuttable distributed problems. In Proceedings of the 45th ACM Symposium on Principles of Distributed Computing (PODC), pages 382-389. ACM, 2026. jukkasuomela.fi/cuttable-distributed-problems/. Full version: arXiv:2605.19157. doi:10.1145/3796701.3815958.DOI
  11. [14]Marthe Bonamy, Cyril Gavoille, Timothé Picavet, and Alexandra Wesolek. Distributed approximation algorithms for minimum dominating set in locally nice graphs. arXiv preprint arXiv:2507.04960, 2025. doi:10.48550/arXiv.2507.04960.arxiv.org/abs/2507.04960
  12. [15]Marthe Bonamy, Cyril Gavoille, Timothé Picavet, and Alexandra Wesolek. Local constant approximation for dominating set on graphs excluding large minors. In Proceedings of the 44th ACM Symposium on Principles of Distributed Computing (PODC), pages 77-87. ACM, 2025. arXiv:2504.01091, doi:10.1145/3732772.3733531.DOI
  13. [16]Nikhil Bansal and Seeun William Umboh. Tight approximation bounds for dominating set on graphs of bounded arboricity. Information Processing Letters, 122:21-24, 2017. doi:10.1016/j.ipl.2017.01.011.DOI
  14. [17]Ernest J. Cockayne, R. M. Dawes, and Stephen T. Hedetniemi. Total domination in graphs. Networks, 10(3):211-219, 1980. doi:10.1002/net.3230100304.DOI
  15. [18]Andrzej Czygrinow and Michał Hańćkowiak. Distributed almost exact approximations for minor-closed families. In Algorithms - ESA 2006, volume 4168 of Lecture Notes in Computer Science, pages 244-255. Springer, 2006. doi:10.1007/11841036_24.DOI
  16. [19]Yair Caro and Michael A. Henning. Directed domination in oriented graphs. Discrete Applied Mathematics, 160(7-8):1053-1063, 2012. doi:10.1016/j.dam.2011.12.027.DOI
  17. [20]Vašek Chvátal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3):233-235, 1979. doi:10.1287/moor.4.3.233.DOI
  18. [21]Andrzej Czygrinow, Michał Hańćkowiak, and Wojciech Wawrzyniak. Fast distributed approximations in planar graphs. In Distributed Computing: 22nd International Symposium, DISC 2008, volume 5218 of Lecture Notes in Computer Science, pages 78-92. Springer, 2008. doi:10.1007/978-3-540-87779-0_6.DOI
  19. [22]Andrzej Czygrinow, Michał Hańćkowiak, Wojciech Wawrzyniak, and Marcin Witkowski. Distributed approximation algorithms for the minimum dominating set in Kₕ-minor-free graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018), volume 123 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1-22:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.ISAAC.2018.22.DOI
  20. [23]Andrzej Czygrinow, Michał Hańćkowiak, Wojciech Wawrzyniak, and Marcin Witkowski. Distributed CONGEST_BC constant approximation of MDS in bounded genus graphs. Theoretical Computer Science, 757:1-10, 2019. doi:10.1016/j.tcs.2018.07.008.DOI
  21. [24]Michal Dory, Mohsen Ghaffari, and Saeed Ilchi. Near-optimal distributed dominating set in bounded arboricity graphs. Distributed Computing, 37:387-398, 2024. doi:10.1007/s00446-023-00447-z.DOI
  22. [25]Zdeněk Dvořák. On distance r-dominating and 2r-independent sets in sparse graphs. Journal of Graph Theory, 91(2):162-173, 2019. arXiv:1710.10010, doi:10.1002/jgt.22426.
  23. [26]Guy Even, Mohsen Ghaffari, and Moti Medina. Distributed set cover approximation: Primal-dual with optimal locality. In 32nd International Symposium on Distributed Computing (DISC 2018), volume 121 of Leibniz International Proceedings in Informatics, pages 22:1-22:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. doi: 10.4230/LIPIcs.DISC.2018.22.DOI
  24. [27]Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634-652, 1998. doi:10.1145/285055.285059.DOI
  25. [29]Valentin Garnero, Ignasi Sau, and Dimitrios M. Thilikos. A linear kernel for planar red-blue dominating set. Discrete Applied Mathematics, 217:536-547, 2017. doi: 10.1016/j.dam.2016.09.045.DOI
  26. [30]S. L. Hakimi. On the degrees of the vertices of a directed graph. Journal of the Franklin Institute, 279(4):290-308, 1965. doi:10.1016/0016-0032(65)90340-6.DOI
  27. [32]Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen, and Krzysztof Onak. Local graph partitions for approximation and testing. In 50th Annual IEEE Symposium on Foundations of Computer Science, pages 22-31. IEEE Computer Society, 2009. math.mit.edu/~kelner/publications/localPartitioningConference.pdf, doi:10.1109/FOCS.2009.77.DOI
  28. [33]Miikka Hilke, Christoph Lenzen, and Jukka Suomela. Brief announcement: Local approximability of minimum dominating set on planar graphs. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing (PODC), pages 344-346. ACM, 2014. doi:10.1145/2611462.2611504.DOI
  29. [34]Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM, 32(1):130-136, 1985. doi:10.1145/2455.214106.DOI
  30. [35]Dorit S. Hochbaum. Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing, 11(3):555-556, 1982. doi:10.1137/0211045.DOI
  31. [36]Ozan Heydt, Sebastian Siebertz, and Alexandre Vigny. Local planar domination revisited. In Structural Information and Communication Complexity (SIROCCO 2022), volume 13298 of Lecture Notes in Computer Science, pages 154-173. Springer, 2022. doi:10.1007/978-3-031-09993-9_9.DOI
  32. [37]Michael A. Henning and Anders Yeo. Total Domination in Graphs. Springer Monographs in Mathematics. Springer, 2013. doi:10.1007/978-1-4614-6525-6.DOI
  33. [38]David S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9(3):256-278, 1974. doi:10.1016/S0022-0000(74)80044-9.DOI
  34. [39][Jør94] Leif K. Jørgensen. Contractions to K₈. Journal of Graph Theory, 18(5):431-448, 1994. doi:10.1002/jgt.3190180502.DOI
  35. [40][KMR07] Joachim Kneis, Daniel Mölle, and Peter Rossmanith. Partial vs. complete domination: t-dominating set. In SOFSEM 2007: Theory and Practice of Computer Science, volume 4362 of Lecture Notes in Computer Science, pages 367-376. Springer, 2007. doi: 10.1007/978-3-540-69507-3_31.DOI
  36. [41][KMW05] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. On the locality of bounded growth. In Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 60-68. ACM, 2005. doi:10.1145/1073814.1073826.DOI
  37. [42][KMW06] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. The price of being near-sighted. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 980-989. Society for Industrial and Applied Mathematics, 2006. www.cs.puc.edu/en-us/research/wp-content/uploads/2017/01/soda06.pdf, doi:10.1145/1109557.1109666.DOI
  38. [43][KMW16] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. Journal of the ACM, 63(2):17:1-17:44, 2016. doi:10.1145/2742012.DOI
  39. [44][KSV20] Simeon Kublenz, Sebastian Siebertz, and Alexandre Vigny. Constant round distributed domination on graph classes with bounded expansion. arXiv preprint arXiv:2012.02701, 2020. Conference version in SIROCCO 2021. doi:10.48550/arXiv.2012.02701.
  40. [45][KW05] Fabian Kuhn and Roger Wattenhofer. Constant-time distributed dominating set approximation. Distributed Computing, 17(4):303-310, 2005. doi:10.1007/s00446-004-0112-5.DOI
  41. [46][Lin92] Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. doi:10.1137/0221015.DOI
  42. [47][LOW08] Christoph Lenzen, Yvonne Anne Oswald, and Roger Wattenhofer. What can be approximated locally? case study: Dominating sets in planar graphs. In Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 46-54. ACM, 2008. doi:10.1145/1378533.1378540.
  43. [48][LPW13] Christoph Lenzen, Yvonne-Anne Pignolet, and Roger Wattenhofer. Distributed minimum dominating set approximations in restricted families of graphs. Distributed Computing, 26(2):119-137, 2013. doi:10.1007/s00446-013-0186-z.
  44. [49][LR15] Reut Levi and Dana Ron. A quasi-polynomial time partition oracle for graphs with an excluded minor. ACM Transactions on Algorithms, 11(3):24:1-24:13, 2015. doi:10.1145/2629508.
  45. [50][LW08] Christoph Lenzen and Roger Wattenhofer. Leveraging Linial’s locality limit. In Distributed Computing, 22nd International Symposium (DISC 2008), volume 5218 of Lecture Notes in Computer Science, pages 394-407. Springer, 2008. doi:10.1007/978-3-540-87779-0_27.DOI
  46. [51][LW10] Christoph Lenzen and Roger Wattenhofer. Minimum dominating set approximation in graphs of bounded arboricity. In Distributed Computing, 24th International Symposium (DISC 2010), volume 6343 of Lecture Notes in Computer Science, pages 510-524. Springer, 2010. doi:10.1007/978-3-642-15763-9_48.
  47. [52]Christoph Lenzen and Sophie Wenning. Tight bounds for constant-round domination on graphs of high girth and low expansion. In Stabilization, Safety, and Security of Distributed Systems (SSS 2024), volume 14931 of Lecture Notes in Computer Science, pages 277-291. Springer, 2024. doi:10.1007/978-3-031-74498-3_20.DOI
  48. [53]Wolfgang Mader. Homomorphieeigenschaften und mittlere Kantendichte von Graphen. Mathematische Annalen, 174:265-268, 1967. doi:10.1007/BF01364272.DOI
  49. [54]Wolfgang Mader. Homomorphiesätze für Graphen. Mathematische Annalen, 178:154-168, 1968. doi:10.1007/BF01350657.
  50. [55]Nabil H. Mustafa and Saurabh Ray. Improved results on geometric hitting set problems. Discrete & Computational Geometry, 44(4):883-895, 2010. doi:10.1007/s00454-010-9285-9.DOI
  51. [57]Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001. doi:10.56021/9780801866890.DOI
  52. [59]Timothé Picavet. Almost tight distributed approximation for domination in sparse graph classes, 2026. arXiv:2610.31203.arxiv.org/abs/2610.31203
  53. [60]Sridhar Rajagopalan and Vijay V. Vazirani. Primal-dual RNC approximation algorithms for set cover and covering integer programs. SIAM Journal on Computing, 28(2):525-540, 1998. doi:10.1137/S0097539793260763.DOI
  54. [61]Zi-Xia Song and Robin Thomas. The extremal function for K₉ minors. Journal of Combinatorial Theory, Series B, 96(2):240-252, 2006. doi:10.1016/j.jctb.2005.07.008.DOI
  55. [64]Wojciech Wawrzyniak. A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs. Information Processing Letters, 114(3):94-98, 2014. doi:10.1016/j.ipl.2013.11.008.DOI
  56. [65]Wojciech Wawrzyniak. A local approximation algorithm for minimum dominating set problem in anonymous planar networks. Distributed Computing, 28(5):321-331, 2015. doi:10.1007/s00446-015-0247-6.DOI
  57. [66]Wojciech Wawrzyniak. Near-optimal distributed domination in planar graphs, 2026. arXiv:2609.32736.arxiv.org/abs/2609.32736

Paper details

vlnc:W_hf5c2mwp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents