pith. sign in

arxiv: 2605.19157 · v1 · pith:G6NVTSPZnew · submitted 2026-05-18 · 💻 cs.DC · cs.DS

Meta-Theorems for Cuttable Distributed Problems

Marthe Bonamy , Avinandan Das , Cyril Gavoille , Timoth\'e Picavet , Jukka Suomela , Alexandra Wesolek This is my paper

Pith reviewed 2026-05-20 07:08 UTC · model grok-4.3

classification 💻 cs.DC cs.DS
keywords Minimum Dominating SetLOCAL algorithmsdistributed computingbounded genus graphsapproximation algorithmscuttable problemsmeta-theoremsplanar graphs
0
0 comments X

The pith

Any α-approximation LOCAL algorithm for Minimum Dominating Set on planar graphs yields an f(g)-round (3α+1)-approximation for graphs embeddable in a genus-g surface.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops meta-theorems that lift approximation guarantees for cuttable minimization problems from planar graphs to graphs of bounded genus. For Minimum Dominating Set this produces an f(g)-round algorithm with ratio 3α+1; feeding in the known planar 11+ε algorithm immediately gives a (34+ε) guarantee that beats the earlier 24g+O(1) bound. The same lifting works for Minimum k-Tuple Dominating Set and for the wider family of locally nice graphs that are controlled by asymptotic dimension. A sympathetic reader cares because the construction supplies a uniform, mechanical way to move existing planar distributed algorithms to surfaces without redesigning them from scratch.

Core claim

We prove that given any α-approximation LOCAL algorithm for Minimum Dominating Set on planar graphs, we can construct an f(g)-round (3α+1)-approximation LOCAL algorithm for MDS on graphs embeddable in a given Euler genus-g surface. The same meta-theorems extend the lifting to other cuttable minimization problems and to locally nice graph classes that rely on asymptotic dimension.

What carries the argument

Cuttable minimization problems, which permit systematic extraction of small subgraphs whose solutions remain in fixed proportion to the global solution restricted to the neighbourhood of each subgraph.

If this is right

  • The known 11+ε planar algorithm immediately yields a (34+ε)-approximation for MDS on genus-g graphs, improving the prior 24g+O(1) bound.
  • Constant-round approximation algorithms become available for Minimum k-Tuple Dominating Set on bounded-genus graphs.
  • The lifting applies verbatim to any other cuttable problem that already possesses a constant-round planar approximation.
  • The technique further extends to locally nice graph classes controlled by asymptotic dimension, beyond the bounded-genus case.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Any new problem shown to be cuttable would inherit the same planar-to-genus transfer at once.
  • The round function f(g) may be tightened by a more careful accounting of the surface embeddings used in the extraction step.
  • Similar meta-theorems could be attempted for minor-closed families or other topological graph classes once a suitable cuttable definition is found.
  • Concrete high-genus examples could be checked to verify that the proportionality constants in the extraction step remain stable.

Load-bearing premise

The problems must be cuttable, so that small subgraphs can be extracted whose solutions stay proportional to the global solution inside their local neighbourhood.

What would settle it

Exhibit one cuttable problem together with a planar α-approximation LOCAL algorithm such that no f(g)-round algorithm achieves ratio 3α+1 on some genus-g instance.

Figures

Figures reproduced from arXiv: 2605.19157 by Alexandra Wesolek, Avinandan Das, Cyril Gavoille, Jukka Suomela, Marthe Bonamy, Timoth\'e Picavet.

Figure 1
Figure 1. Figure 1: An example that shows that 𝑃 𝑟 is 2-colorable (𝑟 − 1)-bounded in 𝑃 for 𝑟 = 3 (on the left), and an example of a 3-coloring of grids for 𝑟 = 2 and 𝑓 (𝑟) = 2(𝑟 − 1) = 2 (on the right). 7Asymptotic dimension was originally defined on metric spaces by Gromov [Gro93] in the field of geometric group theory. 8However, those notions follow a different philosophy. In the study of asymptotic dimension, we want to mi… view at source ↗
Figure 2
Figure 2. Figure 2: Depicted in green is the dominating set 𝐷𝑢 for 𝑢 = 2. Note that 𝑑 (𝑢) is 1 or 5. Proof. Let 𝐺 be a planar graph, let 𝑌 be a nice dominating set of 𝐺 and let 𝐷 be the dominating set of 𝐺 returned by the algorithm. Let 𝑢 ∈ 𝑉 (𝐺) and let 𝐷𝑢 be the dominating set computed by 𝑢. That means • 𝐷𝑢 is nice • 𝐷𝑢 is lexicographically smallest nice set dominating 𝑁 4 [𝑢] The first key observation is that given disjoin… view at source ↗
Figure 3
Figure 3. Figure 3: The depiction of 𝐴, 𝐵,𝐶 in the proof of the key observation. 𝑦2 𝑦1 𝑦3 𝑦4 𝑑1 𝑑3 𝑑2 𝑑6 𝑑4 𝑑9 𝑑5 𝑑7 𝑑8 𝐺 𝑦2 𝑦1 𝑦3 𝑦4 𝐻(𝐺) 𝑦2 𝑦1 𝑦3 𝑦4 𝐻 ′ (𝐺) [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The plane graphs 𝐻 and 𝐻 ′ obtained from 𝐺. for some edge 𝑒 ∈ 𝐸(𝐻 ′ ). Since every edge 𝑒𝐺 contains at most 2 vertices of 𝑍, we have |𝑍 | ⩽ 12|𝑌 |. Therefore, there are at most 13|𝑌 | vertices of 𝑌 ∪ 𝑍 in 𝐷. It remains to bound |𝐷 \ (𝑌 ∪ 𝑍)|. Note that there are two types of vertices 𝑣 ∈ 𝑉 (𝐺) \ (𝑌 ∪ 𝑍). • 𝑁 [𝑣] ⊆ 𝑁 [𝑦𝑣 ] • 𝑁 [𝑣] ⊈ 𝑁 [𝑦𝑣 ] and 𝑣 is between two edges 𝑒𝐺, 𝑒′ 𝐺 in 𝐺 such that 𝑒 and 𝑒 ′ bound … view at source ↗
Figure 5
Figure 5. Figure 5: A depiction of 𝑥1, 𝑥2,𝑤1,𝑤2 for the vertex 𝑢1. adjacent to 𝑦1 or to 𝑦2 hence are at distance at most 3 to all vertices in 𝑓 (with respect to 𝑢, since 𝑢 is a neighbour of 𝑦2 or has a neighbour which is a neighbour of 𝑦2 as we are in the second case). But this means that 𝑤 is at distance at most 4 to all vertices in 𝑓 . Therefore, there are at most 2 6 choices for 𝐷𝑢 and 2 6 · 2 choices for 𝑑 (𝑢) if 𝑑 (𝑢) ∉ … view at source ↗
Figure 6
Figure 6. Figure 6: The tree 𝑇𝛼 has no 0-uniform 𝛼-approximations (here with 𝛼 = 2). Indeed, any 𝛼-approximation A of its minimum dominating set must contain the 𝛼 + 1 vertices of 𝑆 (green), and thus |A(𝑇𝛼 ) ∩ 𝑆 | = |𝑆 | ̸⩽ 𝛼 · MDS(𝑇𝛼, 𝑁0 [𝑆]) since 𝑆 can be dominated by a single vertex (the root). Proposition D.2. For every 𝜀 > 0, any 𝑟-round algorithm that returns a dominating set of size at most 𝛼 · MDS(𝐺) + 𝛽 on 𝐺, can be… view at source ↗
read the original abstract

We prove that given any $\alpha$-approximation LOCAL algorithm for Minimum Dominating Set (MDS) on planar graphs, we can construct an $f(g)$-round $(3\alpha+1)$-approximation LOCAL algorithm for MDS on graphs embeddable in a given Euler genus-$g$ surface. Heydt et al. [European Journal of Combinatorics (2025)] gave an algorithm with $\alpha=11+\varepsilon$, from which we derive a $(34 +\varepsilon)$-approximation algorithm for graphs of genus $g$, therefore improving upon the current state of the art of $24g+O(1)$ due to Amiri et al. [ACM Transactions on Algorithms (2019)]. It also improves the approximation ratio of $91+\varepsilon$ due to Czygrinow et al. [Theoretical Computer Science (2019)] in the particular case of orientable surfaces. We generalize this result into two directions: (1) by considering other graph problems studied in Distributed Computing such as Minimum $k$-Tuple Dominating Set, for which constant-round approximation algorithms were known for planar graphs, but not for graphs of bounded genus; and (2) by considering graph classes beyond bounded genus graphs, called locally nice, and relying on the asymptotic dimension of the class. We prove these results by a series of meta-theorems about cuttable minimization problems with constant-round approximation LOCAL algorithms. Roughly speaking, in cuttable problems, one can systematically extract small subgraphs whose solutions are in proportion to the global solution restricted to the neighbourhood of the subgraph.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper establishes meta-theorems for cuttable minimization problems in the LOCAL model. Given any α-approximation LOCAL algorithm for Minimum Dominating Set on planar graphs, it constructs an f(g)-round (3α+1)-approximation algorithm for MDS on Euler genus-g graphs. From the known 11+ε planar algorithm this yields a (34+ε)-approximation, improving the prior 24g+O(1) bound. The framework is extended to Minimum k-Tuple Dominating Set and to locally nice graph classes via asymptotic dimension, relying on systematic extraction of small subgraphs whose local solutions remain proportional to the global restriction.

Significance. If the central reductions hold, the work supplies a reusable lifting technique that converts planar distributed approximations into bounded-genus and locally-nice approximations while preserving an explicit constant-factor blow-up. The concrete improvement from 24g+O(1) to 34+ε for MDS, together with the generalization to k-tuple dominating set, constitutes a clear advance. The paper also supplies machine-checkable-style meta-theorems that separate the cuttable property from the specific approximation algorithm, which is a methodological strength.

major comments (2)
  1. [§3, Theorem 1] §3, Theorem 1 (main meta-theorem): the proof sketch for the (3α+1) factor must explicitly bound the contribution of the cuttable subgraph extraction step; it is not immediate from the stated definition that the local-to-global proportion introduces no hidden multiplicative loss beyond the factor of 3.
  2. [§5] §5, extension to locally nice classes: the reduction from asymptotic dimension to the round complexity f(g) is only outlined; a concrete dependence on the dimension parameter must be supplied to confirm that the claimed f(g) remains a function of g alone when the class is fixed.
minor comments (2)
  1. [§2] The notation for the cuttable decomposition (Definition 2.3) uses several overloaded symbols; a short table clarifying the roles of the extracted subgraph, its neighborhood, and the proportional solution would improve readability.
  2. [Figure 1] Figure 1 (illustration of cuttable extraction) is referenced but the caption does not state the precise approximation ratio preserved in the example; adding this would help readers verify the meta-theorem on a concrete instance.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the recommendation for minor revision. The comments highlight opportunities to strengthen the explicitness of our proofs, and we address each point below.

read point-by-point responses

  1. Referee: [§3, Theorem 1] §3, Theorem 1 (main meta-theorem): the proof sketch for the (3α+1) factor must explicitly bound the contribution of the cuttable subgraph extraction step; it is not immediate from the stated definition that the local-to-global proportion introduces no hidden multiplicative loss beyond the factor of 3.

    Authors: We agree that the proof sketch for Theorem 1 in §3 would benefit from an explicit bounding of the cuttable subgraph extraction step to confirm there is no hidden multiplicative loss. The (3α+1) factor is obtained by applying the given α-approximation algorithm to the extracted subgraphs (whose local solutions are proportional to the global optimum on their neighborhoods by the cuttable definition) and then combining this with a 3-factor arising from the bounded-genus covering and coloring argument. The proportion in the cuttable definition is at most 1 (no additional constant loss), so the overall factor remains exactly 3α+1. In the revised version we will insert a detailed calculation isolating this contribution. revision: yes

  2. Referee: [§5] §5, extension to locally nice classes: the reduction from asymptotic dimension to the round complexity f(g) is only outlined; a concrete dependence on the dimension parameter must be supplied to confirm that the claimed f(g) remains a function of g alone when the class is fixed.

    Authors: We agree that the outline in §5 should be expanded with an explicit dependence on the asymptotic dimension parameter d. For any fixed locally nice class the value of d is a constant, so the round complexity remains a function f(g) of genus alone. We will add the concrete functional dependence (derived from the standard lifting of asymptotic dimension to LOCAL round complexity) in the revised manuscript to make this transparent. revision: yes

Circularity Check

0 steps flagged

No significant circularity in meta-theorem reduction

full rationale

The paper's central derivation consists of meta-theorems that reduce any given α-approximation LOCAL algorithm for MDS (or related cuttable problems) on planar graphs to an f(g)-round (3α+1)-approximation on genus-g surfaces. This reduction is constructed explicitly via the cuttable property, which is defined independently as the ability to extract small subgraphs whose local solutions are proportional to the global restriction; the factor 3α+1 follows directly from the construction without parameter fitting or redefinition. Base-case planar algorithms are imported from external sources (Heydt et al.), and extensions to k-tuple dominating set and locally-nice classes reuse the same template. No equation or claim reduces by construction to its own inputs, and no load-bearing step relies on self-citation chains or uniqueness theorems from the authors' prior work.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard definitions of the LOCAL model, Euler genus, and the newly introduced notion of cuttable problems; no numerical free parameters are fitted and no new entities are postulated.

axioms (2)
  • standard math The LOCAL model allows nodes to exchange messages with neighbors in synchronous rounds and compute based on their radius-r view.
    Invoked throughout the meta-theorems as the underlying computational model.
  • domain assumption A problem is cuttable if small subgraphs can be extracted such that their local solutions remain proportional to the restriction of the global optimum.
    This is the key structural property used to prove the lifting; it is defined in the paper rather than taken from prior literature.

pith-pipeline@v0.9.0 · 5831 in / 1443 out tokens · 37855 ms · 2026-05-20T07:08:35.006490+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages · 1 internal anchor

  1. [1]

    Akhoondian Amiri, P

    S. Akhoondian Amiri, P. Ossona de Mendez, R. Rabinovich, and S. Siebertz , Distributed domination on graph classes of bounded expansion , in 30th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), ACM Press, July 2018, pp. 143--151. doi : http://doi.org/10.1145/3210377.3210383 10.1145/3210377.3210383

    work page doi:10.1145/3210377.3210383 2018

  2. [2]

    Auslander, T

    L. Auslander, T. A. Brown, and J. W. Youngs , The imbedding of graphs in manifolds , Journal of Mathematics and Mechanics, 12 (1963), pp. 629--634. http://www.jstor.org/stable/24900840 http://www.jstor.org/stable/24900840

    work page arXiv 1963

  3. [3]

    Awerbuch, A

    B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin , Network decomposition and locality in distributed computation , in 30th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, May 1989, pp. 364--369. doi : http://doi.org/10.1109/SFCS.1989.63504 10.1109/SFCS.1989.63504

    work page doi:10.1109/sfcs.1989.63504 1989

  4. [4]

    S. A. Amiri, S. Schmid, and S. Siebertz , Distributed dominating set approximations beyond planar graphs , ACM Transactions on Algorithms, 15 (2019), pp. Article No. 39, pp. 1--18. doi : http://doi.org/10.1145/3093239 10.1145/3093239

    work page doi:10.1145/3093239 2019

  5. [5]

    Bonamy, N

    M. Bonamy, N. Bousquet, L. Esperet, C. Groenland, C.-H. Liu, F. Pirot, and A. Scott , Asymptotic dimension of minor-closed families and Assouad -- Nagata dimension of surfaces , Journal of the European Mathematical Society, 26 (2024), pp. 3739--3791. doi : http://doi.org/10.4171/JEMS/1341 10.4171/JEMS/1341

    work page doi:10.4171/jems/1341 2024

  6. [6]

    The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size

    A. Balliu, S. Brandt, F. Kuhn, D. Olivetti, T. Picavet, and G. Schmid , The distributed complexity landscape on trees depends on the knowledge about the network size , 2026. https://arxiv.org/abs/2605.12787 https://arxiv.org/abs/2605.12787

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  7. [7]

    Larsen , xeditor =

    M. Bonamy, C. Gavoille, T. Picavet, and A. Wesolek , Local constant approximation for dominating set on graphs excluding large minors , in 44th Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM Press, June 2025. doi : http://doi.org/10.1145/3732772.3733531 10.1145/3732772.3733531

    work page doi:10.1145/3732772.3733531 2025

  8. [8]

    R. B. Boppana and M. M. Halld \'o rsson , Approximating independent sets in constant distributed rounds , in 32nd International Colloquium on Structural Information & Communication Complexity (SIROCCO), U. Schmid and R. Kuznets, eds., vol. 15671 of Lecture Notes in Computer Science, Springer, June 2025, pp. 144--158. doi : http://doi.org/10.1007/978-3-031...

    work page doi:10.1007/978-3-031-91736-3_9 2025

  9. [9]

    Czygrinow, M

    A. Czygrinow, M. Han \'c kowiak, E. Szyma \'n ska, W. Wawrzyniak, and M. Witkowski , Distributed local approximation of the minimum k -tuple dominating set in planar graphs , in International Conference on Principles of Distributed Systems, Springer, 2014, pp. 49--59

    work page 2014

  10. [10]

    Czygrinow, M

    A. Czygrinow, M. Hanćkowiak, E. Szymańska, W. Wawrzyniak, and M. Witkowski , Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs , Theoretical Computer Science, 662 (2017), pp. 1--8. doi : http://doi.org/https://doi.org/10.1016/j.tcs.2016.12.001 https://doi.org/10.1016/j.tcs.2016.12.001 , https://www.sciencedir...

    work page doi:10.1016/j.tcs.2016.12.001 2017

  11. [11]

    Czygrinow, M

    A. Czygrinow, M. Ha \'n \'c kowiak, and W. Wawrzyniak , Fast distributed approximations in planar graphs , in 22nd International Symposium on Distributed Computing (DISC), vol. 5218 of Lecture Notes in Computer Science, Springer, September 2008, pp. 78--92. doi : http://doi.org/10.1007/978-3-540-87779-0_6 10.1007/978-3-540-87779-0_6

    work page doi:10.1007/978-3-540-87779-0_6 2008

  12. [12]

    Czygrinow, M

    A. Czygrinow, M. Ha \'n \'c kowiak, and W. Wawrzyniak , Distributed approximation algorithms for the minimum dominating set in K _h -minor-free graphs , in 29th International Symposium on Algorithms and Computation (ISAAC), vol. 123 of LIPIcs, December 2018, pp. 22:1--22:12. doi : http://doi.org/10.4230/LIPIcs.ISAAC.2018.22 10.4230/LIPIcs.ISAAC.2018.22

    work page doi:10.4230/lipics.isaac.2018.22 2018

  13. [13]

    Czygrinow, M

    A. Czygrinow, M. Ha \'n \'c kowiak, W. Wawrzyniak, and M. Witkowski , Distributed CONGEST _ BC constant approximation of MDS in bounded genus graphs , Theoretical Computer Science, 757 (2019), pp. 1--10. doi : http://doi.org/10.1016/j.tcs.2018.07.008 10.1016/j.tcs.2018.07.008

    work page doi:10.1016/j.tcs.2018.07.008 2019

  14. [14]

    Coupette and C

    C. Coupette and C. Lenzen , A breezing proof of the KMW bound , in Symposium on Simplicity in Algorithms (SOSA), ACM-SIAM, January 2021, pp. 184--195. doi : http://doi.org/10.1137/1.9781611976496.21 10.1137/1.9781611976496.21

    work page doi:10.1137/1.9781611976496.21 2021

  15. [15]

    Feuilloley , Bibliography of distributed approximation beyond bounded degree , Tech

    L. Feuilloley , Bibliography of distributed approximation beyond bounded degree , Tech. Rep. http://arxiv.org/abs/2001.08510v4 2001.08510v4 [cs.CG] , arXiv, November 2023

    work page arXiv 2001

  16. [16]

    Fraigniaud, M

    P. Fraigniaud, M. G \"o \"o s, A. Korman, and J. Suomela , What can be decided locally without identifiers? , in 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM Press, July 2013, pp. 157--165. doi : http://doi.org/10.1145/2484239.2484264 10.1145/2484239.2484264

    work page doi:10.1145/2484239.2484264 2013

  17. [17]

    Fraigniaud, A

    P. Fraigniaud, A. Korman, and D. Peleg , Towards a complexity theory for local distributed computing , Journal of the ACM, 60 (2013), pp. Article No. 35, pp. 1--26. doi : http://doi.org/10.1145/2499228 10.1145/2499228

    work page doi:10.1145/2499228 2013

  18. [18]

    G \"o \"o s, J

    M. G \"o \"o s, J. Hirvonen, and J. Suomela , Lower bounds for local approximation , Journal of the ACM, 60 (2013), pp. Article No. 39, pp. 1--23. doi : http://doi.org/10.1145/2528405 10.1145/2528405

    work page doi:10.1145/2528405 2013

  19. [19]

    M. R. Garey and D. S. Johnson , Computers and Intractability - A Guide to the Theory of NP -Completeness , W.H. Freeman, 1979

    work page 1979

  20. [20]

    On the complexity of local distributed graph problems , booktitle =

    M. Ghaffari, F. Kuhn, and Y. Maus , On the complexity of local distributed graph problems , in 49th Annual ACM Symposium on Theory of Computing (STOC), ACM Press, June 2017, pp. 784--797. doi : http://doi.org/10.1145/3055399.3055471 10.1145/3055399.3055471

    work page doi:10.1145/3055399.3055471 2017

  21. [21]

    Gromov , Geometric Group Theory: Asymptotic invariants of infinite groups , Cambridge University Press, 1993

    M. Gromov , Geometric Group Theory: Asymptotic invariants of infinite groups , Cambridge University Press, 1993

    work page 1993

  22. [22]

    Heydt, S

    O. Heydt, S. Kublenz, P. Ossona de Mendez, S. Siebertz, and A. Vigny , Distributed domination on sparse graph classes , European Journal of Combinatorics, 123 (2025), p. 103773. doi : http://doi.org/10.1016/j.ejc.2023.103773 10.1016/j.ejc.2023.103773

    work page doi:10.1016/j.ejc.2023.103773 2025

  23. [23]

    Hilke, C

    M. Hilke, C. Lenzen, and J. Suomela , Brief announcement: local approximability of minimum dominating set on planar graphs , in 33rd Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM Press, July 2014, pp. 344--346. doi : http://doi.org/10.1145/2611462.2611504 10.1145/2611462.2611504

    work page doi:10.1145/2611462.2611504 2014

  24. [24]

    F. Kuhn, T. Moscibroda, and R. Wattenhofer , Local computation: Lower and upper bounds , Journal of the ACM, 63 (2016), pp. Article No. 17, pp. 1--44. doi : http://doi.org/10.1145/2742012 10.1145/2742012

    work page doi:10.1145/2742012 2016

  25. [25]

    Kublenz, S

    S. Kublenz, S. Siebertz, and A. Vigny , Constant round distributed domination on graph classes with bounded expansion , in 28th International Colloquium on Structural Information & Communication Complexity (SIROCCO), T. Jurdzi \'n ski and S. Schmid, eds., vol. 12810 of Lecture Notes in Computer Science, Springer, Cham, June 2021, pp. 334--351. doi : http:...

    work page doi:10.1007/978-3-030-79527-6_19 2021

  26. [26]

    Distributed Comput

    F. Kuhn and R. Wattenhofer , Constant-time distributed dominating set approximation , Distributed Computing, 17 (2005), pp. 303--310. doi : http://doi.org/10.1007/s00446-004-0112-5 10.1007/s00446-004-0112-5

    work page doi:10.1007/s00446-004-0112-5 2005

  27. [27]

    Kikuno, N

    T. Kikuno, N. Yoshida, and Y. Kakuda , The NP -completeness of the dominating set problem in cubic planar graphs , IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E63-E (1980), pp. 443--444

    work page 1980

  28. [28]

    Lenzen , Synchronization and symmetry breaking in distributed systems , PhD thesis, ETH Zurich, Switzerland, December 2011

    C. Lenzen , Synchronization and symmetry breaking in distributed systems , PhD thesis, ETH Zurich, Switzerland, December 2011

    work page 2011

  29. [29]

    Lenzen, Y

    C. Lenzen, Y. A. Oswald, and R. Wattenhofer , What can be approximated locally? -- C ase study: Dominating sets in planar graphs , in 20th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), ACM Press, June 2008, pp. 46--54. doi : http://doi.org/10.1145/1378533.1378540 10.1145/1378533.1378540

    work page doi:10.1145/1378533.1378540 2008

  30. [30]

    Lenzen, Y.-A

    C. Lenzen, Y.-A. Pignolet, and R. Wattenhofer , Distributed minimum dominating set approximations in restricted families of graphs , Distributed Computing, 26 (2013), pp. 119--137. doi : http://doi.org/10.1007/s00446-013-0186-z 10.1007/s00446-013-0186-z

    work page doi:10.1007/s00446-013-0186-z 2013

  31. [31]

    Lenzen and R

    C. Lenzen and R. Wattenhofer , Leveraging Linial 's locality limit , in 22nd International Symposium on Distributed Computing (DISC), vol. 5218 of Lecture Notes in Computer Science, Springer, September 2008, pp. 394--407. doi : http://doi.org/10.1007/978-3-540-87779-0_27 10.1007/978-3-540-87779-0_27

    work page doi:10.1007/978-3-540-87779-0_27 2008

  32. [32]

    Mohar and C

    B. Mohar and C. Thomassen , Graphs on Surfaces , The Johns Hopkins University Press, 2001

    work page 2001

  33. [33]

    Naor and L

    M. Naor and L. Stockmeyer , What can be computed locally , SIAM Journal on Computing, 24 (1995), pp. 1259--1277. doi : http://doi.org/10.1137/S0097539793254571 10.1137/S0097539793254571

    work page doi:10.1137/s0097539793254571 1995

  34. [34]

    Polylogarithmic-time deterministic network decomposition and distributed derandomization , booktitle =

    V. Rozho n and M. Ghaffari , Polylogarithmic-time deterministic network decomposition and distributed derandomization , in 52nd Annual ACM Symposium on Theory of Computing (STOC), ACM Press, June 2020, pp. 350--363. doi : http://doi.org/10.1145/3357713.3384298 10.1145/3357713.3384298

    work page doi:10.1145/3357713.3384298 2020

  35. [35]

    Suomela , Survey of local algorithms , ACM Computing Surveys, 45 (2013), pp

    J. Suomela , Survey of local algorithms , ACM Computing Surveys, 45 (2013), pp. Article No. 24, pp. 1--40. doi : http://doi.org/10.1145/2431211.2431223 10.1145/2431211.2431223

    work page doi:10.1145/2431211.2431223 2013

  36. [36]

    von Rickenbach, R

    P. von Rickenbach, R. Wattenhofer, and A. Zollinger , Algorithmic models of interference in wireless ad hoc and sensor networks , IEEE/ACM Transactions on Networking, 17 (2009), pp. 172--185. doi : http://doi.org/10.1109/TNET.2008.926506 10.1109/TNET.2008.926506

    work page doi:10.1109/tnet.2008.926506 2009

  37. [37]

    P.-J. Wan, K. M. Alzoubi, and O. Frieder , Distributed construction of connected dominating set in wireless ad hoc networks , in 21st Annual Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), vol. 3, June 2002, pp. 1597--1604. doi : http://doi.org/10.1109/INFCOM.2002.1019411 10.1109/INFCOM.2002.1019411

    work page doi:10.1109/infcom.2002.1019411 2002

  38. [38]

    Wan and C.-w

    P.-j. Wan and C.-w. Yi , On the longest edge of gabriel graphs in wireless ad hoc networks , IEEE Transactions on Parallel and Distributed Systems, 18 (2007), pp. 111--125. doi : http://doi.org/10.1109/TPDS.2007.253285 10.1109/TPDS.2007.253285

    work page doi:10.1109/tpds.2007.253285 2007