arXiv CSopen access

Meta-Theorems for Cuttable Distributed Problems

arXiv:2605.19157v1 [cs.DC] 18 May 2026

Meta-Theorems for Cuttable Distributed Problems MARTHE BONAMY, LaBRI, University of Bordeaux, CNRS, France AVINANDAN DAS, Aalto University, Finland CYRIL GAVOILLE, LaBRI, University of Bordeaux, CNRS, France TIMOTHÉ PICAVET, LaBRI, University of Bordeaux, CNRS, France JUKKA SUOMELA, Aalto University, Finland ALEXANDRA WESOLEK, LaBRI, University of Bordeaux, CNRS, France We prove that given any 𝛼-approximation LOCAL algorithm for Minimum Dominating Set (MDS) on planar graphs, we can construct an 𝑓 (𝑔)-round (3𝛼 + 1)-approximation LOCAL algorithm for MDS on graphs embeddable in a given Euler genus-𝑔 surface. Heydt et al. [European Journal of Combinatorics (2025)] gave an algorithm with 𝛼 = 11 + 𝜀, from which we derive a (34 + 𝜀)-approximation algorithm for graphs of genus 𝑔, therefore improving upon the current state of the art of 24𝑔 + 𝑂 (1) due to Amiri et al. [ACM Transactions on Algorithms (2019)]. It also improves the approximation ratio of 91 + 𝜀 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 𝑘-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. CCS Concepts: • Theory of computation → Distributed computing models; Graph algorithms analysis. Additional Key Words and Phrases: distributed algorithm, meta-theorem, LOCAL model, dominating set

1

Introduction

Minimum Dominating Set (MDS) is a famous minimization problem on graphs, known to be NP-complete even in cubic planar graphs [GJ79, KYK80]. The goal is to find a smallest subset of vertices of the input graph that intersects all radius-1 balls of the graph. In this paper, we focus our attention on distributed algorithms that can approximate MDS on the graph underlying the topology of the network. Due to the covering property of a dominating set, the problem and its variants (like Connected Dominating Set [WAF02]) get increasingly more attention in Networking, in particular for mobile and ad-hoc networks. Not only are mobile networks important for point-to-point communications, but specialized ad-hoc networks, such as sensor networks, are important for environmental monitoring tasks. We refer to [KW05, vRWZ09] for extended discussions about the motivations of MDS for routing purposes of such networks. In the LOCAL model, √︁ approximating MDS up to a constant factor in general 𝑛-vertex graphs is known to require Ω( log 𝑛/log log 𝑛 ) rounds [KMW16, CL21]. On the positive side, it is possible to (1 + 𝜀)-approximate MDS for any graph in poly(𝜀 −1 log 𝑛) rounds by combining the techniques of [GKM17] and of [RG20, Corollary 3.11]. For specific graphs, better round complexities can be achieved; cf. [LPW13, Suo13] for a large collection of results (including unit-disk graphs, and planar graphs as a basis of the Gabriel graph

2

Marthe Bonamy, Avinandan Das, Cyril Gavoille, Timothé Picavet, Jukka Suomela, and Alexandra Wesolek

model widely used in ad-hoc networks [WY07]). For instance, 𝑂 (log∗ 𝑛) rounds suffice for planar graphs [CHW08], or more generally for 𝐾𝑡 -minor-free graphs [CHW18] and for sub-logarithmic expansion graphs1 [ASS19], and 𝑜 (log∗ 𝑛) rounds are not sufficient to get a (1 + 𝜀)-approximation of MDS on cycles [CHW08] or unit-disk graphs [LW08]. So, achieving constant-round algorithms must be at the price of relaxing the (1 + 𝜀) approximation ratio. For planar graphs, the quest for constant-approximation and constant-round algorithms seems to start with [LOW08][Len11, Chp. 13][LPW13], with a 130-approximation. Since then, a long line of research has been aimed at improving this ratio. In short, the best approximation ratio to date is 11 + 𝜀, due to [HKOdM+ 25]. We refer to the nice survey of [HKOdM+ 25] for planar graphs and sub-families, including lower bounds. In the meantime, the quest for constant-approximation ratio and constant-round distributed algorithms has been proposed for larger classes of graphs. However, very few examples are known of graph classes 𝒞(𝑝), depending on some fixed parameter 𝑝, where MDS can be solved by a LOCAL algorithm with round complexity 𝑓 (𝑝) and truly-constant approximation ratio (independent of 𝑝). Larger graph classes that make good candidates for extending planar graphs are 𝐻 -minor-free graphs, with some graph 𝐻 not limited to 𝐾5 or 𝐾3,3 . For 𝐾𝑝 -minor-free graphs, we only know of an exponential approximation ratio in 𝑝 [KSV21, HKOdM+ 25], whereas a linear approximation ratio could be possible. For 𝐾3,𝑝 -minor-free graphs [HKOdM+ 25], the dependency is much better (linear in 𝑝), but still not truly constant. Very recently, it was shown [BGPW25] that, for 𝐾2,𝑝 -minor-free graphs, the approximation ratio is 50 regardless of the value of 𝑝. On the other end of the spectrum, the narrowest way to meaningfully extend planar graphs is through embeddable graphs2 on surfaces3 of Euler genus 𝑔. Such surfaces can be obtained from a sphere by adding 𝑔/2 ⩾ 0 handles4 (if they are orientable) or by adding 𝑔 ⩾ 1 cross-caps5 (if they are nonorientable). The Euler genus of a graph 𝐺 is the minimum number 𝑔 such that 𝐺 embeds on a surface of Euler genus 𝑔. In this context, [ASS19, Theorem 3.11] proposed an (24𝑔 + 𝑂 (1))approximation algorithm with constant-round complexity (actually linear in 𝑔). For graphs of orientable genus 𝑔, i.e., embeddable on an orientable surface of genus 𝑔, [CHWW19] designed a constant-round algorithm that returns a dominating set of size at most 91M + 76𝑔 − 66, where M is the optimal size. By adding a simple extra brute-force step in their algorithm, we can convert it into a (91 + 𝜀)-approximation (cf. Proposition D.2), so with a ratio independent of 𝑔. However, the result of [CHWW19] does not transfer to graphs of bounded Euler genus, as for any 𝑔, there are graphs embeddable on the projective plane6 (so of Euler genus 1) that cannot be embedded on any orientable surface of genus 𝑔 (so of orientable genus at least 𝑔 + 1). So, for these graphs, the approximation ratio will be 91 + 𝜀, but with the number of rounds possibly depending on the number of vertices6 . Graphs of Euler genus 𝑔 are included in 𝐾3,2𝑔+3 -minor-free graphs, because the Euler genus of 𝐾3,2𝑔+3 is at least 𝑔 + 1 (cf. [MT01, Theorem 4.4.7]) and the class of Euler genus-𝑔 graphs is closed under taking minors. We observe that the approximation ratio for 𝐾3,𝑝 -minor-free graphs, for √ 𝑝 = 2𝑔 + 3, due to [HKOdM+ 25, Theorem 2.2] provides an approximation ratio of 𝑂 ( 𝑔). Indeed, 1 Roughly speaking, the expansion of a graph 𝐺 is a function 𝑓 that, for any 𝑟 , bounds the maximum edge density of a

depth-𝑟 minor of 𝐺 by 𝑓 (𝑟 ), where a depth-𝑟 minor is a minor of 𝐺 where each branch set has radius at most 𝑟 . 2 I.e., that can be drawn on the surface without edge crossing, like planar graphs for the sphere. 3 That are compact, connected 2-dimensional manifold without boundary. 4 By adding a handle, we mean that two disjoint disks of the sphere are replaced by a cylinder. 5 By adding a cross-cap, we mean that a disk of the sphere is replaced by a Möbius strip. 6 For instance, a cycle with 𝑛 = 2𝑔 + 6 vertices where opposite vertices are connected by an extra edge as Euler genus 1 but orientable genus at least 𝑔 + 1 = 𝑛/2 − 2, cf. [ABY63].

Meta-Theorems for Cuttable Distributed Problems

3

the ratio of their algorithm is precisely (2 + 𝜀) (2∇1 + 1), where ∇1 is the maximal edge density of a √︁ depth-1 minor of any graph of the class. As we can check (cf. Proposition D.3) that ∇1 ⩽ 3𝑔/2 + 3, √︁ √︁ the approximation ratio is at most 4 3𝑔/2 + 14 + 𝜀. As it may occur that ∇1 ⩾ 3𝑔/2 − 𝑂 (1) for some Euler genus-𝑔 graph (cf. Proposition D.3), the best known approximation ratio for MDS in √ Euler genus-𝑔 graphs is Θ( 𝑔), and 91 + 𝜀 for orientable genus-𝑔 graphs. It is important to note that no LOCAL algorithms for Euler genus-𝑔 graphs can achieve simulta√ neously constant round complexity and constant approximation ratio. Indeed, by taking 𝑛 = Ω( 𝑔), √︁ since there exists 𝑛-vertex graphs of Euler genus Θ(𝑛 2 ), the Ω( log 𝑛/log log 𝑛 ) lower bound √︁ of [KMW16, CL21] yields a lower bound of Ω( log 𝑔/log log 𝑔 ). Our Contributions. In the remainder of the paper, by “LOCAL algorithm”, we mean deterministic distributed algorithm in the classical LOCAL model. • We propose a (34 + 𝜀)-approximation LOCAL algorithm for MDS in Euler genus-𝑔 graphs whose round complexity depends only on 𝑔 (cf. Corollary 4.3). This improves approximation ratios in both the orientable (previously 91 + 𝜀) and non-orientable (previously 24𝑔 + 𝑂 (1)) genus case. The analysis of the algorithm uses the fact that such graphs have asymptotic dimension at most two. • This result follows directly from more general meta-theorems. More generally, we prove that any constant-round 𝛼-approximation for MDS on planar graphs can be turned into a 𝑓 (𝑔)-round (3𝛼 + 1)-approximation algorithm for MDS on Euler genus-𝑔 graphs, for some function 𝑓 . • We extend this result in two ways. First, we show that our meta-theorems hold for all local minimization problems that are well-behaved (including MDS and its variants). We provide a simple graph-theoretic property on the problem that is sufficient for our meta-algorithms to apply. This significantly simplifies proofs and circumvents having to reason about various algorithms. • We apply our results on problems such as Minimum 𝑘-Tuple Dominating Set (cf. Corollary 4.5), obtaining constant-ratio approximations on problems where none were previously √ known. We also obtain a ratio of 𝑂 ( 𝑔) for Minimum Connected Dominating Set in Euler genus-𝑔 graphs. • Second, we prove that our meta-theorems hold on much broader “locally nice” graph classes, such as locally bounded-genus graphs, or locally bounded-genus graphs with a bounded number of apex vertices (whose unconstrained neighborhoods can break the surface embeddability of the graph). • We prove three versions of our meta-theorem (see Meta-Theorem I, Meta-Theorem II and Meta-Theorem III), making it easily applicable and adapted to different situations. Unlike similar notions, such as the classical network decomposition [AGLP89], no preliminary construction is required for any of our algorithms. Obviously, they depend on the parameters of the graph classes on which they are applied, like the Euler genus 𝑔 and/or the asymptotic dimension of the class with its control function. Organization. Basic notations and asymptotic dimension are introduced in Section 2. Section 3 derives a 616-approximation for MDS on bounded-genus graphs, gently introducing the ideas and motivations of the later meta-theorems. Finally, Section 4 presents our different meta-theorems, and their applications to different problems of the literature.

4

2

Marthe Bonamy, Avinandan Das, Cyril Gavoille, Timothé Picavet, Jukka Suomela, and Alexandra Wesolek

Preliminaries

Graphs and Domination. A subset 𝑋 ⊆ 𝑉 (𝐺) dominates 𝑆 if 𝑆 ⊆ 𝑁 [𝑋 ]. We denote by MDS(𝐺, 𝑆) the minimum size of a subset of 𝑉 (𝐺) dominating 𝑆. Note that MDS(𝐺, 𝑉 (𝐺)), denoted by MDS(𝐺) for short, is the size of a minimum dominating set for 𝐺. Asymptotic Dimension. In this section, we focus on defining asymptotic dimension7 (a non-trivial task, as it happens) and explaining how to exploit it, in the hope that others may be able to exploit it in turn. A graph 𝐺 with a spanning subgraph 𝐻 is 𝑘-colorable 𝛿-bounded in 𝐻 if each vertex of 𝐺 can be assigned a color from {0, . . . , 𝑘 − 1} so that the distance in 𝐻 between any two vertices taken in a monochromatic path of 𝐺 is at most 𝛿. In other words, all monochromatic connected components of 𝐺 must have a weak diameter in 𝐻 at most 𝛿. A proper 𝑘-coloring of 𝐺 is nothing else than a 𝑘-coloring 0-bounded in 𝐻 . If 𝐻 has diameter 𝐷, then it is 1-colorable 𝐷-bounded in 𝐻 . The asymptotic dimension of a graph class 𝒞 is a non-negative integer denoted by asdim(𝒞), and related to the 𝑘-coloring boundedness of the 𝑟 -th power of 𝐺. It is a notion closely related to sparse partitions8 and weak sparse covers (see [BBE+ 24, §1.8] for precise connection between these notions). Recall that the 𝑟 -th power of 𝐺, denoted by 𝐺 𝑟 , is the graph obtained from 𝑉 (𝐺) by adding edges between pairs of vertices at distance at most 𝑟 in 𝐺. Rather than giving its standard definition, we prefer the following equivalent one9 : Proposition 2.1 ([BBE+ 24, Proposition 1.17]). For every graph class 𝒞, asdim(𝒞) ⩽ 𝑑 if and only if there exists a function 𝑓 : N → N, called control function, such that for every 𝐺 ∈ 𝒞 and integer 𝑟 ⩾ 1, 𝐺 𝑟 is (𝑑 + 1)-colorable 𝑓 (𝑟 )-bounded in 𝐺. Any associated control function 𝑓 that makes asdim(𝒞) = 𝑑 is also called a 𝑑-dimensional control function of 𝒞. The Assouad-Nagata dimension of 𝒞 has a similar definition, except that the control function must be linear. A crude example is that paths have Assouad-Nagata dimension 1, because, for each 𝑟 ⩾ 1, it suffices to alternatingly color subsets of 𝑟 consecutive vertices with two colors, see Fig. 1.

distance 4 > 𝑟

diameter 2 ⩽ 𝑓 (𝑟 ) = 𝑟 − 1

Fig. 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). 7 Asymptotic dimension was originally defined on metric spaces by Gromov [Gro93] in the field of geometric group theory. 8 However, those notions follow a different philosophy. In the study of asymptotic dimension, we want to minimize the

dimension. In the study of sparse partitions and covers, the main goal is to minimize a function of the dimension and the diameter of the sets. 9 In the original Proposition 1.17 of [BBE+ 24], 𝐺 𝑟 is (𝑑 + 1)-colorable 𝑓 (𝑟 )-bounded in 𝐺 𝑟 , instead of in 𝐺. By following this original definition, the function 𝑓 is not a control function, whereas in Proposition 2.1 it is.

Meta-Theorems for Cuttable Distributed Problems

5

More generally, 𝑑-dimensional grids have a 𝑑-dimensional control function 𝑓 (𝑟 ) = 𝑑 · (𝑟 − 1). Trees, and more generally graph classes of bounded treewidth (resp. layered treewidth) have asymptotic dimension 1 (resp. 2). Planar graphs, and more generally the classes of 𝐻 -minor-free graphs (for any fixed 𝐻 ) have asymptotic dimension 2 as shown by [BBE+ 24]: the dependency in 𝐻 only shows in the control function 𝑓 . Dense graph classes may also have small asymptotic dimension. For example, it is sufficient that there is a quasi-isometry into a class having small asymptotic dimension10 . The dense class of chordal graphs, being quasi-isometric to the class of trees, has asymptotic dimension 1. Intuitively, each connected component of a color class in 𝐺 𝑟 can be viewed as a “simple” component of the graph, that we already understand well. In the setting of LOCAL algorithms with constant round complexity 𝑟 /2, each vertex can observe only its distance-(𝑟 /2) neighborhood. If the underlying graph class has asymptotic dimension 𝑑, this neighborhood intersects at most 𝑑 + 1 such simple parts. As a result, we can derive strong approximation guarantees, since each vertex’s view of the graph remains constrained and conceptually simple. We observe that all our algorithms make use of the control function 𝑓 , but not for any particular pre-computing coloring or partitioning, so that the asymptotic dimension 𝑑 is actually used only in analysis of the approximation ratio. 3

MDS on Bounded Euler Genus Graphs

This section explains how asymptotic dimension helps us devise approximation algorithms for MDS on Euler-genus-𝑔 graphs. It also serves as an introduction to the method of cutting and motivates the later meta-theorems. The following algorithm for planar graphs will serve as a black-box building block for the more involved algorithm of Theorem 3.2. Proposition 3.1. There is a 205-approximation LOCAL algorithm A for Minimum Dominating Set in planar graphs with round complexity 6. To present the algorithm (cf. Algorithm 1) we first need to define the “best” minimum dominating sets of a labelled graph 𝐻 . Among all dominating sets, we first discard those which contain some 𝑣 for which there exists 𝑤 with 𝑁 [𝑣] ⊊ 𝑁 [𝑤], and among the remaining ones, we declare “best” the one lexicographically smallest considering the labels of the vertices. Algorithm 1 The algorithm for dominating set on planar graphs. Require: A planar graph 𝐺. Ensure: A dominating set 𝐷 of 𝐺 such that |𝐷 | ⩽ 205 · MDS(𝐺). 1: 𝐷 ← ∅ 2: Each vertex 𝑢 computes 𝐺 [𝑁 5 [𝑢]] and all minimum dominating sets of 𝑁 4 [𝑢] in 𝐺. Among those sets, 𝑢 selects the “best” one as 𝐷𝑢 . 3: Each vertex 𝑢 picks the vertex 𝑣𝑢 of smallest label in 𝐷𝑢 ∩ 𝑁 [𝑢], and adds it to 𝐷. By construction, Algorithm 1 outputs a dominating set 𝐷 within 6 rounds. In fact, Algorithm 1 is very natural in the sense that in order to compute a global dominating set we use local dominating sets. The proof on the approximation factor is given in the Appendix C.1. We extend Algorithm 1 to genus 𝑔 graphs by dealing separately with local subgraphs of 𝐺 which are planar and which are not  planar. For a graph 𝐺, the 𝑇 -error set of 𝐺 w.r.t. planarity is the vertex set defined by 𝑋 = 𝑢 ∈ 𝑉 (𝐺) | 𝐺 [𝑁 𝑇 [𝑢]] is not planar . 10 It is conjectured in [BBE+ 24] that, even more generally, any graph class forbidding some graph as a fat minor should also

have asymptotic dimension at most 2.

6

Marthe Bonamy, Avinandan Das, Cyril Gavoille, Timothé Picavet, Jukka Suomela, and Alexandra Wesolek

Theorem 3.2. There exists a function 𝐶 such that for any 𝑔, there is a 616-approximation LOCAL algorithm for Minimum Dominating Set in Euler genus-𝑔 graphs with round complexity 𝐶 (𝑔). Proof. Suppose 𝐺 has Euler genus 𝑔 and let 𝑓 be a 2-dimensional control function of the class of Euler genus-𝑔 graphs. A 2-hop in 𝑋 ⊂ 𝑉 (𝐺) is a sequence of vertices 𝑥 1, . . . , 𝑥𝑘 in 𝑋 such that consecutive vertices are at distance at most two in 𝐺. Algorithm 2 The algorithm for dominating set on bounded genus graphs. Require: A graph 𝐺 of genus ⩽ 𝑔. Ensure: A dominating set 𝐷 of 𝐺 such that |𝐷 | ⩽ 616 · MDS(𝐺). 1: If 𝑁 𝑓 (10)+5 [𝑢] is planar, 𝑢 runs Algorithm 1 on the corresponding locally planar subgraph. Let 𝑋 be the set of undominated vertices after step 1. 2: If 𝑢 ∈ 𝑋 , 𝑢 computes lexicographically smallest minimum set 𝐷𝑋 ′ in 𝐺 which dominates the set 𝑋 ′ ⊆ 𝑋 of vertices reachable from 𝑢 with a 2-hop in 𝑋 . It adds 𝑁 [𝑢] ∩ 𝐷𝑋 ′ to 𝐷.

Claim 3.3. The round complexity is some constant 𝐶 (𝑔) depending only on 𝑔. Proof of claim. It suffices to show that there is no 2-hop of weak diameter ⩾ 2(𝑓 (10) + 6)𝑔 of vertices in 𝑋 . Suppose such a 2-hop on vertices of 𝑋 exists. Take two vertices 𝑥 and 𝑦 on the 2-hop which are at least 2(𝑓 (10) +6)𝑔 apart. Note that for any 𝑖 < 2(𝑓 (10) +6)𝑔 there exists a vertex on the 2-hop at distance 𝑖 or 𝑖 + 1 from 𝑥. Hence there exist 𝑢 1, . . . 𝑢𝑔+1 ∈ 𝑋 where 𝑢𝑖 is at distance 2(𝑓 (10) + 6)(𝑖 − 1) or 2(𝑓 (10) + 6) (𝑖 − 1) + 1 from 𝑥. Therefore, the sets 𝑁 𝑓 (10)+5 [𝑢 1 ], . . . , 𝑁 𝑓 (10)+5 [𝑢𝑔+1 ] are pairwise disjoint and they are non-planar, so the genus of the graph is at least 𝑔 + 1 by additivity (cf. [MT01, Theorem 4.4.3]). As the genus is at most 𝑔, this is a contradiction. ⋄ The coloring of the asymptotic dimension gives us color classes 𝐶 1, 𝐶 2, 𝐶 3 , such that: • 𝐶𝑖 = 𝐵𝑖1 ∪ · · · ∪ 𝐵𝑖𝑗𝑖 with11 diam𝐺 (𝐵𝑖𝑗 ) ⩽ 𝑓 (10) for all 1 ⩽ 𝑗 ⩽ 𝑗𝑖 , and • for any 𝑗 ≠ ℓ, we have 𝐵𝑖𝑗 ≠ 𝐵𝑖ℓ . More precisely, 𝐵𝑖𝑗 and 𝐵𝑖ℓ are at distance at least 11. The Cutting. Let 𝑌𝐺 be a minimum dominating set of 𝐺. Let 𝐺 ′ = 𝐺 [𝑁 [𝑌 ′ ]] where 𝑌 ′ = 𝑌𝐺 ∩ 5 𝑁 [𝐵𝑖𝑗 ]. Note that 𝐺 ′ contains 𝑁 4 [𝐵𝑖𝑗 ] and | MDS(𝐺 ′ )| ⩽ |𝑌𝐺 ∩ 𝑁 5 [𝐵𝑖𝑗 ] |. The Analysis Outside of the Error Set. Note that 𝐺 ′ either contains only vertices from 𝑋 or contains at least one vertex which is not in 𝑋 and is therefore planar. Hence, vertices in 𝐵𝑖𝑗 \ 𝑋 choose at most 205 · | MDS(𝐺 ′ )| ⩽ 205 · |𝑌𝐺 ∩ 𝑁 5 [𝐵𝑖𝑗 ] | vertices as their neighbourhood of distance 5 in 𝐺 and 𝐺 ′ is the same. Vertices not in 𝑋 choose at most 205|𝑌𝐺 | vertices in each color class. Across all color classes, this adds up to at most 3 · 205|𝑌𝐺 |. The Analysis With Non-Empty Error Set. Let 𝑋 1, . . . , 𝑋𝑘 be the 2-hop components. Note that for two distinct 2-hop components 𝑋𝑖 and 𝑋 𝑗 , the neighbourhoods 𝑁 [𝑋𝑖 ] and 𝑁 [𝑋 𝑗 ] do not intersect. As |𝐷𝑋𝑖 | ⩽ |𝑌𝐺 ∩ 𝑁 [𝑋𝑖 ] |, the vertices in 𝑋 choose at most |𝑌𝐺 | vertices. In total, at most 3 · 205|𝑌𝐺 | + |𝑌𝐺 | = 616 · | MDS(𝐺)| vertices are added to 𝐷: the algorithm is a 616-approximation. □ 11We denote by diam (𝑋 ) the largest distance in 𝐺 between any two vertices of 𝑋 . 𝐺

Meta-Theorems for Cuttable Distributed Problems

7

In fact, if Algorithm 1 gives an approximation ratio 𝛼, then the above algorithm for genus 𝑔 graphs is a (3𝛼 + 1)-approximation algorithm. One might now ask whether any algorithm for MDS on planar graphs can be turned into one for genus 𝑔 graphs. We show that this is indeed possible. In order to do so, we need to show that the cutting step and its analysis work for any MDS algorithm for planar graphs. We delve into this deeper in the next section. 4

Meta-Theorems

In this section, we present our meta-theorems, which take as input a LOCAL approximation algorithm for a graph class 𝒞 and returns a LOCAL approximation algorithm for a broader class 𝒟 that locally looks like graphs in 𝒞, possibly with some local exceptions. Meta-theorems using black-box LOCAL algorithms might be difficult to state as there are some subtle issues with vertex identifiers (see for instance [FKP13, FGKS13, GHS13]). The LOCAL model assumes the input graph 𝐺 has unique 𝑂 (log 𝑛)-bit vertex labels, i.e., with identifiers polynomial in 𝐺. In particular, running a LOCAL algorithm A on only a small part 𝐻 of 𝐺 might fail because: (1) vertex labels in 𝐻 may not be polynomial in 𝐻 anymore, and (2) algorithm A may require polynomial-size identifiers to work properly. Thus, Meta-Theorem I assumes that the black-box algorithm A does not require polynomial identifiers. This captures all order-invariant algorithms12 . In contrast, Meta-Theorem II and Meta-Theorem III allow A to use polynomial identifiers, but impose restrictions on the optimization problem. Due to space constraints, Meta-Theorem II & III are presented in Section A. From Locally-𝒞 to Locally Nice Graphs. Given a graph class 𝒞, we say that a graph class 𝒟 is 𝑇 -locally-𝒞 if for all 𝐺 ∈ 𝒟 and 𝑢 ∈ 𝑉 (𝐺), 𝐺 [𝑁 𝑇 [𝑢]] ∈ 𝒞. This definition can already capture many graph classes, such as graphs of girth at least 2𝑘 + 2: those are just graphs that are 𝑘-locally-𝒯, where 𝒯 is the class of trees. Similarly, graphs embedded on a surface with edge-width13 at least 2𝑘 + 2 are 𝑘-locally-𝒫, where 𝒫 is the class of planar graphs. However, our meta-theorem captures broader classes of graphs as it can support local exceptions. Given  a graph class 𝒟 and 𝐺 ∈ 𝒟, the 𝑇 -error set of 𝐺 w.r.t. 𝒞 is the vertex set defined by 𝑋 = 𝑢 ∈ 𝑉 (𝐺) | 𝐺 [𝑁 𝑇 [𝑢]] ∉ 𝒞 . In other words, this is the set of vertices that are witnesses for 𝐺 not being 𝑇 -locally-𝒞. Clearly, if 𝐺 has no 𝑇 -errors, that is 𝑋 = ∅, then 𝐺 is 𝑇 -locally-𝒞. Given a 𝜌-local14 problem Π, the class 𝒟 is 𝑇 -locally 𝛿-nice w.r.t. 𝒞 and Π, if the maximum weak diameter in any 𝐺 ∈ 𝒟 of any connected component of 𝐺 [𝑁 2𝜌 [𝑋 ]] is at most 𝛿, where 𝑋 is the 𝑇 -errors of 𝐺 w.r.t. 𝒞. This means that the set of 𝑇 -errors can be covered by far-away bounded-radius balls of 𝐺. By Proposition C.11, bounded Euler genus graphs form a locally nice class of graphs w.r.t. 𝒫. Uniform Approximation. Our meta-theorems are inspired by the intriguing property [BGPW25, Proposition 3.1] that any approximate algorithm A for MDS is going to perform well in a target graph class 𝒟 that is locally-𝒞, as long as 𝒟 has small asymptotic dimension, and A makes "good local choices" in 𝒞. More precisely, a LOCAL algorithm A is a 𝑘-uniform 𝛼-approximation in 𝒞, if for all 𝐺 ∈ 𝒞 and 𝑆 ⊆ 𝑉 (𝐺), |A(𝐺) ∩ 𝑆 | ⩽ 𝛼 · MDS(𝐺, 𝑁 𝑘 [𝑆]), where A(𝐺) is the set returned by A when run on 𝐺, and MDS(𝐺, 𝑋 ) is the minimum size of a subset of 𝑉 (𝐺) dominating vertices of 𝑋 in 𝐺. Unless explicitly said, we will assume for convenience that 𝑘 ⩾ 1, as otherwise only very 12 A model where vertices have unique labels, but the output of A is invariant under relabelings preserving the label

order [GHS13].

13 The length of shortest noncontractible cycle in the embedded graph.

14 A problem whose solution can be verified by checking all neighborhoods of radius 𝜌. See next page for a formal definition.

8

Marthe Bonamy, Avinandan Das, Cyril Gavoille, Timothé Picavet, Jukka Suomela, and Alexandra Wesolek

restricted graph classes 𝒞 can support 0-uniform constant-approximation algorithms for MDS (cf. Proposition D.1). We can now state properly the fact that any 𝑘-uniform approximate algorithm that performs well for 𝒞, performs well for a locally-𝒞 class of bounded asymptotic dimension. It can be shown that the bounded asymptotic dimension assumption cannot be removed, even for MDS15 . Proposition 4.1 ([BGPW25, Proposition 3.1]). Let A be a 𝑘-uniform 𝛼-approximation LOCAL algorithm for Minimum Dominating Set in a hereditary16 class of graphs 𝒞 with round complexity 𝑟 ⩾ 1. Let 𝒟 be a graph class with 𝑑-dimensional control function 𝑓 , and that is17 (𝑓 (2𝑘 + 2) + 𝑟 )locally-𝒞. Then A is also an 𝛼 (𝑑 + 1)-approximation algorithm on 𝒟. We extend Proposition 4.1 in multiple ways. First, we allow 𝒟 to be locally nice, and secondly, we prove that this also applies to problems other than MDS. This means that, for example, any approximate algorithm A solving a well-behaved problem that performs well on planar graphs can be converted into an algorithm B that performs well on bounded genus graphs, as long as A is 𝑘-uniform on 𝒞, and 𝒟 has small asymptotic dimension. Before giving the full statement of Meta-Theorem I, we define the class of problems we are interested in. LOCAL Optimization Problems. As defined in [GHS13], a simple graph problem Π is an optimization problem in which a feasible solution18 is a subset of vertices or edges, and the goal is to optimize the size of a feasible solution. A simple graph problem Π is 𝜌-local if there is a LOCAL algorithm R with round complexity 𝜌 that can recognize a feasible solution19 . Algorithm R recognizes 𝑆 as a feasible solution if and only if, whenever applied on 𝐺 with 𝑆 given, R returns true for all vertices of 𝐺. See Section B.1 for more formal definitions. We are mainly interested in small locality problems, that is when 𝜌 is constant, as clearly all simple graph problems are 𝜌-local for 𝜌 large enough. A lot of well-known problems such as optimization variants of LCL problems [NS95]. This includes Minimum Vertex Cover, Minimum Dominating Set, Maximum Independent Set, Maximal Matching, and Minimum 𝑘-Tuple Dominating Set. The distance-𝑑 versions of these problems20 are also 𝑑-local problems. However, Minimum Connected Dominating Set is Ω(𝑛)-local21 . Our framework includes problems such as Red-Blue Dominating Set that can take vertex or edge input labels on the graph, and problems defined on arbitrarily large degree graphs. In this work, we focus on subsets of vertices, but the techniques presented here extend to subsets of edges. In our setting, we restrict our attention to cases where the vertices do not have access to 𝑛, the size of the graph. For some problems, such as Minimum Dominating Set, this restriction can 15 This can be achieved by observing that a simple constant-round 3-approximation LOCAL algorithm exists for MDS in

trees, but (high) girth-𝑔 graphs do not admit a constant-round 𝑜 (𝑔)-factor approximation. The latter follows by combining Ramsey-theoretic arguments with the lower bound proof due to [GHS13] based on 2𝑘-regular graphs of girth 𝑔, where vertices can be linearly ordered so that a positive fraction of them have pairwise isomorphic radius-𝑟 neighbourhoods, for any 𝑟, 𝑘, 𝑔. 16 A class of graphs closed under vertex deletion. 17 The original statement claimed erroneously that 𝒟 being 𝑡 -locally-𝒞 for 𝑡 = 𝑓 (2𝑘 + 1) is enough, instead of the correct 𝑡 = 𝑓 (2𝑘 + 2) + 𝑟 . This has no impact, as in practice we use Proposition 4.1 in Corollary 4.4 only for 𝑘 ⩽ 𝑟 = 𝑂 (1). 18 Here, a feasible solution is any subset of vertices or edges that satisfies the constraints of the graph problem. Said differently, an admissible candidate solution. 19We do not require that the algorithm checks the optimality of the solution. If we require this, most interesting problems would require 𝜌 = Ω (𝑛) to be 𝜌-local. 20 E.g. for Minimum Dominating Set, every vertex has a dominating vertex in its distance-𝑑 neighborhood. 21 In a 𝑛-vertex cycle, no LOCAL algorithm R of round complexity < 𝑛/2 can distinguish the situation where a feasible solution is 𝑆 = 𝑉 (𝐺 ) \ {𝑢 } from the situation where 𝑆 = 𝑉 (𝐺 ) \ {𝑢, 𝑣 } with two opposite vertices 𝑢, 𝑣.

Meta-Theorems for Cuttable Distributed Problems

9

be relaxed22 . However, we omit this case for brevity, since we are not aware of any constant-round algorithm for a 𝜌-local problem that requires 𝑛. As, in the LOCAL model with constant number of rounds, the literature mostly studies minimization problems, we also focus on those. Observe that many classically interesting problems like Maximum Independent Set and Maximum Matching do not admit constant-time constant-ratio approximations (see [BH25] for references), even on the restricted graph class of paths23 . Given a 𝜌-local problem Π, a graph 𝐺 and 𝑋 ⊆ 𝑉 (𝐺), we define OPTΠ (𝐺, 𝑋 ) as the optimal size of a subset of vertices of 𝐺 that is feasible on 𝑋 (and not necessarily for vertices outside 𝑋 ). We naturally extend the definition of 𝑘-uniform algorithm as follows: a LOCAL algorithm A is a 𝑘-uniform 𝛼-approximation for Π in a class of graphs 𝒞, if for all 𝐺 ∈ 𝒞 and 𝑆 ⊆ 𝑉 (𝐺), |A(𝐺) ∩ 𝑆 | ⩽ 𝛼 · OPTΠ (𝐺, 𝑁 𝑘 [𝑆]). We can now state our strengthening of Proposition 4.1. Note that we further require (when the set of errors is not empty) that our problem is additive, that is, any superset of a solution feasible on 𝑋 is still feasible on 𝑋 . For instance, MDS is additive because adding vertices to any dominating set maintains a dominating set. Theorem 4.2 (Meta-Theorem I). Let A be a 𝑘-uniform 𝛼-approximation LOCAL algorithm that does not require polynomial identifiers, for an additive 𝜌-local problem Π in a class of graphs 𝒞 with round complexity 𝑟 , where 𝒞 is hereditary and stable by disjoint union. Let 𝒟 be a graph class of asymptotic dimension 𝑑 with 𝑑-dimensional control function 𝑓 that is 𝑇 -locally 𝛿-nice w.r.t. 𝒞 and Π, where 𝑇 = 𝑓 (2𝑘 + 2𝜌) + max {𝑘 + 𝜌, 𝑟 }. Then, there exists a max{𝑘, 𝜌 }-uniform (𝛼 (𝑑 + 1) + 1)approximation algorithm B on 𝒟 with round complexity 𝑇 + 𝛿 + 2. Furthermore, if 𝒟 is 𝑇 -locally 𝒞, the approximation ratio is 𝛼 (𝑑 + 1) and the additivity condition can be dropped. Cutability. It may be difficult to prove that some algorithm is 𝑘-uniform. Instead, we provide a simple sufficient criterion for deciding if any constant-round constant-ratio approximation algorithm for Π is 𝑘-uniform. A 𝜌-local problem Π is cuttable for a hereditary graph class 𝒞 with parameter 𝛽 > 0 if for all 𝐺 ∈ 𝒞 and 𝑋 ⊆ 𝑉 (𝐺), there exists some 𝑌 ⊇ 𝑋 such that OPTΠ (𝐺 [𝑌 ]) ⩽ 𝛽 · OPTΠ (𝐺, 𝑋 ). Informally, this asks that 𝑋 can be augmented into a set 𝑌 (if not the whole vertex set) so that the graph induced by this bigger set 𝑌 has an optimal solution somewhat smaller than the optimal feasible solution for 𝑋 . For instance, MDS is cuttable with parameter 𝛽 = 1 (see Claim C.3), as is the distance-𝑑 version of MDS (see Proposition C.6). We prove in Section C.6 the fundamental property that every constant-round constant-ratio approximation for a cuttable problem is also 𝑘-uniform (as long as the algorithm does not require polynomial identifiers). Therefore, MDS admits uniform approximation algorithms. This means we can actually use Meta-Theorem I for any cuttable problem without the 𝑘-uniform assumption. Actually, for MDS, we can show that this property holds even if the algorithm requires polynomial identifiers (cf. Proposition C.2). 22 In full generality, this applies to all problems for which, for every 𝑛, there exists an 𝑛-vertex graph within the input graph

class that has bounded diameter and admits a constant-size solution. For MDS on planar graphs, we can take a depth-1 tree. 23 The rough intuition for this is that on paths, any constant-time algorithm run on a vertex far away from the end of the path sees the same neighborhood, and therefore will output the same result on every vertex or edge. The only way to comply with the problem description, unlike minization problem like MDS, is to not take any vertex in the independent set (or any edge in the maximum matching), at least in the middle of the path. This leads to an arbitrarily bad approximation ratio.

10

Marthe Bonamy, Avinandan Das, Cyril Gavoille, Timothé Picavet, Jukka Suomela, and Alexandra Wesolek

Recall that Euler genus-𝑔 graphs have asymptotic dimension at most 2, and are locally nice (cf. Proposition C.11). Thus, Meta-Theorem I implies that any constant-round 𝛼-approximation for MDS gives a 𝐶 (𝑔)-round (3𝛼 + 1)-approximation for graphs of Euler genus 𝑔. The best known ratio for MDS in planar graphs is 𝛼 = 11 + 𝜀 due to Heydt et al. [HKOdM+ 25]. Therefore, Corollary 4.3. For any 𝜀 > 0, for any 𝑔, there is a 𝑘 (𝜀)-uniform (34 + 𝜀)-approximation LOCAL algorithm for Minimum Dominating Set in Euler genus-𝑔 graphs with round complexity 𝐶 (𝜀, 𝑔) for some functions 𝐶 and 𝑘. We can even go one step further by applying Meta-Theorem I to the uniform approximation LOCAL algorithm derived from Corollary 4.3, and the class 𝒞 of Euler genus-𝑔 graphs. We immediately obtain the following, where 34.01 can be thought of as 34 + 𝜀. Corollary 4.4. Let 𝒞 be the class of Euler genus-𝑔 plus graphs, and 𝒟 be a graph class of asymptotic dimension 𝑑 that is 𝑟 -locally-𝒞 for some 𝑟 large enough. Then, there is a 34.01(𝑑 + 1)-approximation LOCAL algorithm for Minimum Dominating Set in 𝒟 with round complexity 𝐶 (𝑑, 𝑔, 𝑟 ) for some function 𝐶. Actually, Corollaries 4.3 and 4.4 hold for the larger class of Euler genus-𝑔 plus 𝑎-apex graphs, i.e. graphs obtained from a graph of Euler genus 𝑔 where at most 𝑎 vertices are allowed to have an arbitrary neighborhood. These graphs exclude 𝐾3+𝑎,2𝑔+3+𝑎 as minor (as, without apices, the graphs exclude 𝐾3,2𝑔+3 ), and thus have asymptotic dimension 2 as well. They are also locally nice, since 𝑎 apices cannot create short-cuts longer than 2𝑎. So, the approximation ratio is preserved, whereas the round complexity depends on 𝑎. Moreover, our results can be applied to get approximation algorithms on graphs of bounded Euler genus for all other minimization problems in the Distributed Computing literature that admit a constant-round, constant-ratio approximation on planar graphs (for a comprehensive list of such problems, see the survey of Feuilloley [Feu23]). For instance, let us focus on the Minimum 𝑘-Tuple Dominating Set problem (studied extensively in [WAF02]), a generalization of Minimum Dominating Set. In this variant, the goal is to find the smallest subset of vertices such that every vertex outside the set is adjacent to at least 𝑘 vertices within it. The classical MDS problem corresponds to the special case 𝑘 = 1. For planar graphs, this problem admits a constant-round 𝑘/(𝑘 − 2)-approximation algorithm [CHS+ 14] for 𝑘 > 2, and a 6-approximation [CHS+ 17] for 𝑘 = 2. Both algorithms do not require polynomial identifiers. Using the fact that Minimum 𝑘-Tuple Dominating Set is cuttable and additive (cf. Proposition C.5), that Euler genus-𝑔 graphs are locally nice (cf. Proposition C.11), and by applying Proposition C.7 and Meta-Theorem I, we get the following: Corollary 4.5. For every 𝑘 ⩾ 2, there is a 𝐶 1 (𝑘)-uniform 𝛼-approximation LOCAL algorithm for Minimum 𝑘-Tuple Dominating Set in Euler genus-𝑔 graphs with round complexity 𝐶 2 (𝑔, 𝑘), for some functions 𝐶 1, 𝐶 2 , where 𝛼 = 19 if 𝑘 = 2 and 𝛼 ⩽ 3𝑘/(𝑘 − 2) + 1 otherwise. For Minimum Connected Dominating Set [WAF02], which is an example of non-local problem, √ we can obtain a constant-round approximation with ratio 𝑂 ( 𝑔) in Euler genus-𝑔 graphs by applying the "connected" reduction from MDS in bounded expansion graphs due to [AAOdMRS18, √︁ Theorem 5.8]. This gives an approximation ratio of 2𝛼∇1 ⩽ 68 3𝑔/2 + 𝑂 (1), where 𝛼 = 34 + 𝜀 is √︁ the best approximation ratio for MDS in Euler genus-𝑔 graphs (Corollary 4.3), and ∇1 ⩽ 3𝑔/2 + 3

Meta-Theorems for Cuttable Distributed Problems

11

(Proposition D.3) is the expansion of Euler genus-𝑔 graphs. We leave open the question of improving the ratio to a constant independent of the genus.

12

Marthe Bonamy, Avinandan Das, Cyril Gavoille, Timothé Picavet, Jukka Suomela, and Alexandra Wesolek

Acknowledgments The first, third and fourth authors have been partially supported by the French ANR projects ENEDISC (ANR-24-CE48-7768) and TEMPOGRAL (ANR-22-CE48-0001). The second author was supported in part by the Research Council of Finland, Grants 363558 and 359104. The sixth author was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy - The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID:390685689). References [AAOdMRS18] 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: 10.1145/3210377.3210383. [ABY63] 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. [AGLP89] 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: 10.1109/SFCS.1989.63504. [ASS19] 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: 10.1145/3093239. [BBE+ 24] M. Bonamy, N. Bousqet, 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: 10.4171/JEMS/1341. [BBK+ 26] 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. [BGPW25] 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: 10.1145/3732772.3733531. [BH25] R. B. Boppana and M. M. Halldó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: 10.1007/978-3-031-91736-3_9. [CHS+ 14] A. Czygrinow, M. Hanćkowiak, E. Szymańska, W. Wawrzyniak, and M. Witkowski, Distributed local approximation of the minimum 𝑘-tuple dominating set in planar graphs, in International Conference on Principles of Distributed Systems, Springer, 2014, pp. 49–59. [CHS+ 17] 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: https://doi.org/10.1016/j.tcs.2016.12.001, https://www.sciencedirect.com/science/article/pii/S0304397516307071. [CHW08] A. Czygrinow, M. Hańć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: 10.1007/978-3-540-87779-0_6. [CHW18] A. Czygrinow, M. Hańćkowiak, and W. Wawrzyniak, Distributed approximation algorithms for the minimum dominating set in 𝐾ℎ -minor-free graphs, in 29th International Symposium on Algorithms and Computation (ISAAC), vol. 123 of LIPIcs, December 2018, pp. 22:1–22:12. doi: 10.4230/LIPIcs.ISAAC.2018.22. [CHWW19] A. Czygrinow, M. Hańćkowiak, W. Wawrzyniak, and M. Witkowski, Distributed C O N G E S T 𝐵𝐶 constant approximation of MDS in bounded genus graphs, Theoretical Computer Science, 757 (2019), pp. 1–10. doi: 10.1016/j.tcs.2018.07.008. [CL21] 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: 10.1137/1.9781611976496.21. [Feu23] L. Feuilloley, Bibliography of distributed approximation beyond bounded degree, Tech. Rep. 2001.08510v4 [cs.CG], arXiv, November 2023. [FGKS13] P. Fraigniaud, M. Göö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: 10.1145/2484239.2484264.

Meta-Theorems for Cuttable Distributed Problems

13

[FKP13] 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: 10.1145/2499228. [GHS13] M. Göö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: 10.1145/2528405. [GJ79] M. R. Garey and D. S. Johnson, Computers and Intractability - A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979. [GKM17] 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: 10.1145/3055399.3055471. [Gro93] M. Gromov, Geometric Group Theory: Asymptotic invariants of infinite groups, Cambridge University Press, 1993. [HKOdM+ 25] 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: 10.1016/j.ejc.2023.103773. [HLS14] 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: 10.1145/2611462.2611504. [KMW16] 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: 10.1145/2742012. [KSV21] 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ński and S. Schmid, eds., vol. 12810 of Lecture Notes in Computer Science, Springer, Cham, June 2021, pp. 334–351. doi: 10.1007/978-3-030-79527-6_19. [KW05] F. Kuhn and R. Wattenhofer, Constant-time distributed dominating set approximation, Distributed Computing, 17 (2005), pp. 303–310. doi: 10.1007/s00446-004-0112-5. [KYK80] 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. [Len11] C. Lenzen, Synchronization and symmetry breaking in distributed systems, PhD thesis, ETH Zurich, Switzerland, December 2011. [LOW08] C. Lenzen, Y. A. Oswald, and R. Wattenhofer, What can be approximated locally? – Case 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: 10.1145/1378533.1378540. [LPW13] 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: 10.1007/s00446-013-0186-z. [LW08] 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: 10.1007/978-3-540-87779-0_27. [MT01] B. Mohar and C. Thomassen, Graphs on Surfaces, The Johns Hopkins University Press, 2001. [NS95] M. Naor and L. Stockmeyer, What can be computed locally, SIAM Journal on Computing, 24 (1995), pp. 1259–1277. doi: 10.1137/S0097539793254571. [RG20] V. Rozhoň 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: 10.1145/3357713.3384298. [Suo13] J. Suomela, Survey of local algorithms, ACM Computing Surveys, 45 (2013), pp. Article No. 24, pp. 1–40. doi: 10.1145/2431211.2431223. [vRWZ09] 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: 10.1109/TNET.2008.926506. [WAF02] 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: 10.1109/INFCOM.2002.1019411. [WY07] 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: 10.1109/TPDS.2007.253285.

14

A

Marthe Bonamy, Avinandan Das, Cyril Gavoille, Timothé Picavet, Jukka Suomela, and Alexandra Wesolek

When the black-box algorithm requires polynomial identifiers

As we have seen, Proposition C.7 applies to lots of optimization problems. However, it does not fulfil the polynomial identifiers requirement of the LOCAL model. We would like to have the same statement to apply in the LOCAL model with polynomial identifiers with the same assumptions. However, assigning new identifiers to vertices while maintaining control of the output of the algorithm is very challenging. Ramsey-type techniques (for example, for finding lower bounds on the approximation ratio on particular graph classes [HLS14]) can be useful for this, but only on very particular graphs: ones where each neighborhood is similar. In general graphs, to the best of our knowledge, we do not know how to adapt this technique. Thankfully, for locally-𝒞 classes, where the set of errors is empty, we can weaken the statement of Proposition C.7 in a way that we can still apply a variation of Meta-Theorem I afterwards. The trick is to modify the coloring given by the asymptotic dimension so that all color classes are almost balanced in size (see Lemma C.12). With this technique, we just need to apply uniformity on sets that are large. Formally, LOCAL algorithm A is an 𝜀-weakly 𝑘-uniform 𝛼-approximation for Π in a class of graphs 𝒞, if for all 𝐺 ∈ 𝒞   and 𝑆 ⊆ 𝑉 (𝐺) such that |𝑆 | ⩾ 𝜀 |𝑉 (𝐺)| , we have |A(𝐺) ∩ 𝑆 | ⩽ 𝛼 · OPTΠ (𝐺, 𝑁 𝑘 [𝑆]). We say that the 𝑑-local problem Π is 𝜀-weakly uniformizable on 𝒞 if for every integer 𝑑 > 0 and 𝑟 and any real 𝛼, there exists some integers 𝑘, 𝑟 ′ and real 𝛽 such that for every 𝑟 -round 𝛼-approximation A of Π on 𝒞 in constant time, there exists some 𝑟 ′ -round LOCAL algorithm B that is a 𝜀-weakly 𝑘-uniform 𝛽-approximation of Π on 𝒞 in constant time. The function (𝑟, 𝛼) ↦→ (𝑘, 𝛽) is called the (weak) binding function. It is a corollary of the proof of Proposition C.7 that any cuttable problem is weakly uniformizable, in the LOCAL model this time (see Corollary C.10). Therefore, we can use Lemma C.12 to only work on color classes of linear size (which preserves the polynomial-ness of identifiers), and prove the following. 1 Theorem A.1 (Meta-Theorem II). Let 𝑑, 𝑘 be integers 𝛼 > 0 a real, A be a 𝑑+1 -weakly 𝑘-uniform 𝛼approximation LOCAL algorithm for a 𝜌-local problem Π in a class of graphs 𝒞 with round complexity 𝑟 , where 𝒞 is hereditary and stable by disjoint union. Let 𝒟 be a graph class of asymptotic dimension 𝑑 with 𝑑-dimensional control function 𝑓 , that is 𝑇 -locally-𝒞 for 𝑇 = 𝑓 (6𝑘 +6𝜌) +4𝑘 +4𝜌 +max {𝑘 + 𝜌, 𝑟 }. Then A is a 𝑘-uniform 𝛼 (𝑑 + 1)-approximation algorithm on 𝒟.

The proof of this can be found in Section C.11. When the error set is not empty, we require further assumptions. For a discussion on why those assumptions are required, we refer to Section B.4 A problem Π is called 𝜔-paddable if for any integer 𝑁 , there exists some 𝐺 ∈ 𝒞 on at least 𝑁 vertices such that OPTΠ (𝐺) ⩽ 𝜔. We also add a small property that the problem needs to satisfy: a 𝑑-local problem Π is dense in 𝒞 if there exists some unbounded function 𝑔 that for any 𝐺 ∈ 𝒞 of diameter 𝐷, we have OPTΠ (𝐺) ⩾ 𝛽 · 𝐷. We require that24 lim inf 𝑓 = +∞. This essentially mean that there are no large (in diameter) portion of the graph with no vertices of the solution; every vertex is close to a vertex of the solution. Under the both additional assumptions of paddability and density, we can prove an analogue of Meta-Theorem II. See Meta-Theorem III for the full statement. Summary Table of the Results. Here is a simplified table of the assumptions necessary to apply our meta-theorem that transform a constant-round constant-factor approximation algorithm A on the class 𝒞 to another constant-round constant-factor approximation algorithm on the class 𝒟. 24 It is possible to get rid of this property if one adds that the graphs in the definition of 𝜔-paddable also have bounded

diameter. Then, the rough idea is that, in the proof of Meta-Theorem III, the algorithm will be able to compute the optimal b of the proof. Then one gets Eq. (6) without the 𝜔 term. solution on the graph 𝐺

Meta-Theorems for Cuttable Distributed Problems

15

We assume that 𝒞 is hereditary and stable by disjoint union, and that 𝒟 is of bounded asymptotic dimension.

A does not assume polynomial IDs

A assumes polynomial IDs

𝑇 -error set is empty (𝒟 is locally-𝒞) Π is cuttable

𝑇 -error set is not empty (𝒟 is locally nice) Π is cuttable and additive

(Meta-Theorem I and Proposition C.7) Π is cuttable

(Meta-Theorem I and Proposition C.7) Π is cuttable, additive, paddable and dense25

(Meta-Theorem II and Corollary C.10)

(Meta-Theorem III and Corollary C.10)

Table 1. Simplified table of the assumptions necessary to apply Meta-Theorem I, Meta-Theorem II and Meta-Theorem III, along with their references.

B B.1

Discussions Definitions for Locally Verifiable Problems

Let us define 𝜌-local verifiable problems in more detail. Let 𝐺 be a graph with a set Σin of input labels on vertices or edges, which includes a unique identifier for each vertex. If 𝑣 ∈ 𝑉 (𝐺), A is a LOCAL algorithm, and 𝑋 is a set of vertices of 𝐺, we use A(𝐺, 𝑋, 𝑣) to represent the output of vertex 𝑣 when A is run on 𝐺 with input labels Σin ⊔ 𝑋 (the local inputs form an encoding of 𝑋 , i.e. every vertex knows if it is contained or not in 𝑋 ). A simple graph problem Π is 𝜌-local if there exists some LOCAL algorithm R which runs in 𝜌 rounds such that for all subsets of vertices 𝑋 , the following holds: • if 𝑋 is a feasible solution of the problem Π on (𝐺, Σin ), then for all vertices 𝑣 of 𝐺, we have A(𝐺, 𝑋, 𝑣) = 1, or • if 𝑋 is not a feasible solution of the problem Π on (𝐺, Σin ), then there exists 𝑣 ∈ 𝑉 (𝐺) such that A(𝐺, 𝑋, 𝑣) = 0. B.2

Why cutability seems unavoidable

Cutability is not a trivial property. Consider the following very artificial problems: we want to output a set (as small as possible) which contains every vertex of degree 0 or 1 in the graph. Of course, this problem admits a trivial 1-round algorithm: take all vertices of degree 0 or 1. However, our goal is to be able to use algorithms in a black-box manner. Instead, we consider the 1-round algorithm A that outputs every vertex of degree not equal to 2. Take 𝒞 the class of forests, on which A is a 2-approximation. This is because there are at least as many leaves as vertices of degree 3 or more. Now, let 𝒟 be the closure (under subgraphs) of 𝑞-subdivisions of ladders26 , where 𝑞 is as large as we like and a ladder is the Cartesian product of an edge and an arbitrarily long path. Clearly, 25 It is possible to remove the dense condition, at the expense of making the paddable condition stricter. See Section A. 26 The 𝑞-subdivision of a graph 𝐺 is a copy of 𝐺 where every edge is replaced by a path with 𝑞 inner vertices.

16

Marthe Bonamy, Avinandan Das, Cyril Gavoille, Timothé Picavet, Jukka Suomela, and Alexandra Wesolek

every graph in 𝒟 is 𝑞-locally in 𝒞. Additionally 𝒟 has asymptotic dimension 1, (one can check that they are 𝐾4 -minor-free, and so have bounded treewidth hence asymptotic dimension 1 [BBE+ 24]). However, A fails catastrophically on 𝒟. Indeed, there are graphs in 𝒟 that do not have any leaves or isolated vertices (one can just take the 𝑞-subdivision of a ladder), so that the best solution on this graph is empty. Of course, in this very specific scenario there does exist an alternative algorithm which gives a 1-approx in forests and actually works in 𝒟. However, the point is to avoid modifying the black-box A. More generally, such degree-based problems seem to have uncontrollable behavior across local-global boundaries: in 𝒞 the algorithm can afford to take more vertices than necessary because of the existence of some other vertices (such as the large amount of leaves in the case of forests), whereas in 𝒟 these vertices do not exist. B.3

Cutability of Distance-Exactly-𝑑 Dominating Set

In some graph classes such as planar graphs and minor-free classes, Proposition C.6 can be extended to Minimum Distance-Exactly-𝑑 Dominating Set. Given a graph 𝐺 and 𝑑 a positive integer, a subset of vertices 𝐷 is a called a distance-exactly-𝑑 dominating set of 𝐺 if every vertex 𝑣 of 𝑉 (𝐺) \ 𝐷 is at distance exactly 𝑑 from some vertex in 𝐷. In the Minimum Distance-Exactly-𝑑 Dominating Set problem, one asks for distance-exactly-𝑑 dominating set of minimum size. In graph classes that are closed under the addition of leaves to the graphs, Distance-(⩽ 𝑑) Dominating Set is cuttable with parameter 𝑑. To give a rough intuition, in these classes, one can attach a path of length 𝑑 − 1 to a vertex 𝑣, put 𝑣 and all vertices in the path to the dominating set, and thus simulate a distance-(⩽𝑑) dominating set that way. B.4

On the additional assumptions of the Meta-Theorem for paddable problems

In the statement of Meta-Theorem III, we require problems that are paddable, i.e., we want to exclude graph classes that admit arbitrarily large graphs whose difficulty is concentrated in a bounded-diameter region with bounded optimum. Otherwise, a padding trick can inflate instance size (hence identifier ranges) without increasing hardness. One cannot hope for a version of MetaTheorem III with non-empty error sets and for problems without this property. Here is the scenario we want to avoid. One could take any approximation algorithm on a class of graph 𝒞, and √ construct a class 𝒟 where graphs of size 𝑛 are formed by taking a graph of 𝒞 of size at most 𝑛 (or 𝑛𝑐 for √ some 0 < 𝑐 < 1), and attaching somewhere an error set 𝑋 of size at least 𝑛 − 𝑛, which has small radius and small (bounded) optimum solution. Then, this version of Meta-Theorem III would give a good approximation on this class 𝒟. However, solving the problem Π efficiently on 𝒟 would require solving it on 𝒞, as the error set is of small radius and has a small optimum solution. Put in a nutshell, there is roughly a reduction from the class 𝒟 to the class 𝒞. However, as the error set is large in size, √ one could attribute very large identifiers to the portion of the graph in 𝒞: setting |𝑋 | ⩾ 𝑛 − 𝑛 can artificially inflate the identifiers by a square (and one can get a polynomial with power 𝐶 by choosing |𝑋 | ⩾ 𝑛 1/𝐶 ). If the algorithm does not need the polynomial identifiers, everything still works. If it is not the case however, we have transformed an easy instance to another easy instance where identifiers are larger. This is not possible if the algorithm truly needs the polynomial identifiers, i.e., if the approximation guarantee depends on the vertex identifiers.27

27 For these reasons, this might hint towards considering the size of the largest identifier as complexity parameter of its own,

just like the size of the graph [BBK+ 26].

Meta-Theorems for Cuttable Distributed Problems

17

Thus, we require 𝒞 to be paddable or 𝒟 to be not paddable. We prove the result for the case where 𝒞 is paddable only, as the proof is similar for the other case. 28 C C.1

Proofs Approximation for planar graphs

Proposition 3.1. There is a 205-approximation LOCAL algorithm A for Minimum Dominating Set in planar graphs with round complexity 6. 1 3 2 10 19 ...

17 18

15 16

9

11 14

4

12

5

7 8

6

13

Fig. 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 disjoint subsets 𝐴, 𝐵, 𝐶 of 𝑉 (𝐺) such that 𝐺 = 𝐺 [𝐴 ∪ 𝐶] ∪ 𝐺 [𝐵 ∪ 𝐶], that is, 𝐶 separates 𝐴 from 𝐵 (see Figure 3). If 𝐺 [𝐵 ∪ 𝐶] is in the fourth neighbourhood of 𝑢 ∈ 𝐵 ∪𝐶, the value of 𝐷𝑢 ∩ 𝐵 is completely determined by 𝐷𝑢 ∩𝐶. In other words, there is a unique best way to extend 𝐷𝑢 ∩𝐶 to 𝐵. Therefore, for such vertices 𝑢, there are at most 2 |𝐶 | · 𝑀𝐷𝑆 (𝐺, 𝐵 ∪𝐶) different candidates for 𝑑 (𝑢). We now discuss how to use that observation to reach the desired conclusion. We associate to each vertex 𝑢 ∈ 𝑉 \ 𝑌 an arbitrary vertex 𝑦𝑢 ∈ 𝑌 ∩ 𝑁 (𝑢). We consider the plane multigraph 𝐻 obtained from an arbitrary planar embedding of 𝐺 by contracting every edge 𝑢𝑦𝑢 for 𝑢 ∈ 𝑉 \ 𝑌 , but keeping any resulting loop or multiple edge. Note that 𝑉 (𝐻 ) = 𝑌 by construction. Let 𝐻 ′ be the plane multigraph obtained from 𝐻 by iteratively deleting any edge incident to a face bounded by one edge (i.e. a loop) or to two faces bounded by two edges (i.e. there is a multiedge of multiplicity 3), see Figure 4. In particular, 𝐻 ′ may contain loops and multiple edges, but in the embedding they separate different parts of 𝑉 (𝐻 ′ ) or, in the case of multiple edges, are incident on at least one side to a face of size at least 3. We observe that by Euler’s formula, there are fewer than 2 · 3|𝑉 (𝐻 ′ )| = 6|𝑌 | edges in 𝐻 ′ . To every edge 𝑒 of 𝐻 or 𝐻 ′ we associate an edge 𝑒𝐺 of 𝐺 such that 𝑒𝐺 turns into 𝑒 in the contraction process. We let 𝑍 be the subset of vertices of 𝑉 (𝐺) \ 𝑌 which are an endpoint of 𝑒𝐺 28 If we require the algorithm to have knowledge the size of the graph, we can have Meta-Theorem III with this additional

property. However, to achieve this, we need to change the definition of paddable: we now request, for any 𝑛, a graph of size 𝑛 (instead of size ⩾ 𝑛) with the desired properties.

18

Marthe Bonamy, Avinandan Das, Cyril Gavoille, Timothé Picavet, Jukka Suomela, and Alexandra Wesolek

𝐶 𝐵 𝐴 𝑢

Fig. 3. The depiction of 𝐴, 𝐵, 𝐶 in the proof of the key observation.

𝑑2

𝑑4 𝑑3

𝑦2

𝑑9

𝑑1

𝑦1

𝑦3 𝑑5

𝑑6 𝑦4 𝑑8

𝑦2

𝑦1

𝑦3

𝑦4

𝐻 (𝐺)

𝑦2

𝐺

𝑦1

𝑦3

𝑦4

𝐻 ′ (𝐺)

𝑑7

Fig. 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 a face of size 2 in 𝐻 ′ There cannot be any other case, as if the first case does not apply then 𝑣 has degree at least 2, so is adjacent to some vertex 𝑤 such that 𝑤 is not a neighbour of 𝑦𝑢 . But then 𝑤 gets contracted to a vertex 𝑠 ≠ 𝑦𝑢 when creating 𝐻 . Note that 𝑣𝑤 does not get contracted and let 𝑒 be the edge in 𝐻 such that 𝑒𝐺 = 𝑣𝑤. But since 𝑣 is not in 𝑍 , the edge 𝑒 gets deleted when creating 𝐻 ′ , i.e. 𝑒 is in between two parallel edges to 𝑒 and we are in the second case. We now assume 𝑤 is a vertex such that 𝑑 (𝑤) = 𝑣. If the first case applies then any neighbour of 𝑣 is also a neighbour of 𝑦 𝑣 , in particular, the distance of a vertex 𝑤 ≠ 𝑣 to 𝑣 is the same as to 𝑦 𝑣 . However, either 𝑦 𝑣 has strictly more neighbours than 𝑣, or 𝑦 𝑣 has a smaller label than 𝑣, as 𝑦 𝑣 ∈ 𝑌 , hence 𝑤 would prefer 𝑦 𝑣 over 𝑣. We analyse now the second case, which is slightly more interesting. Let 𝑒𝐺 be incident to 𝑥 1, 𝑥 2 and 𝑒𝐺′ to 𝑤 1, 𝑤 2 , where for each 𝑖, either 𝑑 (𝑥𝑖 ) = 𝑦𝑖 or 𝑥𝑖 = 𝑦𝑖 and similarly for 𝑤𝑖 and without loss of generality we assume 𝑦𝑢 = 𝑦1 . For a depiction, see Figure 5. Note that 𝐶 = {𝑥 1, 𝑥 2, 𝑦1, 𝑦2, 𝑤 1, 𝑤 2 } separates 𝑢 from the rest of 𝑉 (𝐻 ′ ), and that vertices involved in some edge inside 𝑓 in 𝐻 are all

Meta-Theorems for Cuttable Distributed Problems

𝑦2

19

𝑥1

𝑥2 𝑢1

𝐺 𝑤1

𝑤2

𝑦1

Fig. 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 26 choices for 𝐷𝑢 and 26 · 2 choices for 𝑑 (𝑢) if 𝑑 (𝑢) ∉ 𝑌 ∪ 𝑍 . This is because not more than 2 vertices from the set contained in the cycle 𝑦2𝑥 1𝑤 1𝑦1𝑤 2𝑥 2𝑦2 can be chosen as otherwise 𝑦1, 𝑦2 would be a better choice. We can note that in the case where both 𝑦1 and 𝑦2 get selected in 𝐷𝑢 there is no extra vertex to add as all of the inside is dominated and when one of 𝑦1 or 𝑦2 is chosen, then there is at most one vertex picked on the inside, otherwise 𝑦1, 𝑦2 would be a better choice. Therefore, we reduce the number of choices to 1 · 24 · 2 + 2 · 24 · 1 = 64. Since there are at most 3|𝑌 | options for 𝑓 , this adds up to 192|𝑌 |. All together, we get 13|𝑌 | for the set 𝑌 or the set 𝑍 being chosen, and 192|𝑌 | for the choices of the second case of vertices not in 𝑍 or 𝑌 being chosen. This sums up to 205|𝑌 |, as claimed. □ C.2

Meta-theorem for the LOCAL model with no polynomial identifiers requirement

Theorem 4.2 (Meta-Theorem I). Let A be a 𝑘-uniform 𝛼-approximation LOCAL algorithm that does not require polynomial identifiers, for an additive 𝜌-local problem Π in a class of graphs 𝒞 with round complexity 𝑟 , where 𝒞 is hereditary and stable by disjoint union. Let 𝒟 be a graph class of asymptotic dimension 𝑑 with 𝑑-dimensional control function 𝑓 that is 𝑇 -locally 𝛿-nice w.r.t. 𝒞 and Π, where 𝑇 = 𝑓 (2𝑘 + 2𝜌) + max {𝑘 + 𝜌, 𝑟 }. Then, there exists a max{𝑘, 𝜌 }-uniform (𝛼 (𝑑 + 1) + 1)approximation algorithm B on 𝒟 with round complexity 𝑇 + 𝛿 + 2. Furthermore, if 𝒟 is 𝑇 -locally 𝒞, the approximation ratio is 𝛼 (𝑑 + 1) and the additivity condition can be dropped. This proof is essentially a simplified proof of Meta-Theorem III. However, we include it for completeness. Proof. Let 𝐺 ∈ 𝒟. As 𝒟 has 𝑑-dimensional control function 𝑓 , then 𝐺 2𝑘+2𝜌 admits a (𝑑 + 1)coloring 𝑓 (2𝑘 + 2𝜌)-bounded in 𝐺. Fix such a coloring, and, for each 𝑖 ∈ {0, 1, . . . , 𝑑 }, let 𝐶𝑖 be the set of color-𝑖 vertices in 𝐺 2𝑘+2𝜌 (and also in 𝐺). We denote by ℭ𝑖 the set of (2𝑘 + 2𝜌)-components of 𝐶𝑖 (i.e. connected components of 𝐺 2𝑘+2𝜌 [𝐶𝑖 ]). So, by definition, all components of ℭ𝑖 have weak diameter in 𝐺 at most 𝑓 (2𝑘 + 2𝜌), and are pairwise at distance at least 2𝑘 + 2𝜌 + 1 in 𝐺 (because distinct components of ℭ𝑖 cannot be adjacent in 𝐺 2𝑘+2𝜌 ). We describe the Algorithm B we want to use in Algorithm 3, which is very similar to Algorithm 2. We run Algorithm B on 𝐺. It is easy to check that B(𝐺) is a valid solution for 𝐺, because Π is additive. By definition, |B(𝐺)| ⩽ |𝑆 | + |𝑆 ′ |, where 𝑆 = A(𝐺) \ 𝑋 (Step 3) and 𝑆 ′ is a brute-forced set of minimum size satisfying the constraints of vertices of 𝐺 not satisfied (Step 4). Note that every vertex not in 𝑁 𝜌 [𝑋 ] is satisfied by 𝑆, so 𝑆 ′ ⊆ 𝑁 2𝜌 [𝑋 ]. Clearly, |𝑆 ′ | ⩽ OPTΠ (𝐺), and |𝑆 ′ | = 0 if there

20

Marthe Bonamy, Avinandan Das, Cyril Gavoille, Timothé Picavet, Jukka Suomela, and Alexandra Wesolek

Algorithm 3 Generic algorithm B from Meta-Theorem I. Require: An 𝜀-weakly 𝑘-uniform 𝛼-approximate LOCAL algorithm A for Π in 𝒞 with round complexity 𝑟 , a graph classes 𝒞 and 𝒟 with properties of the statement of Meta-Theorem III, the 𝑑-dimensional control function 𝑓 of 𝒟 and 𝐺 ∈ 𝒟 with 𝑇 -errors 𝑋 where 𝑇 = 𝑓 (2𝑘 + 2𝜌) + max {𝑘 + 𝜌, 𝑟 }. Ensure: A solution 𝑆 for the graph 𝐺 to the problem Π with the guarantee that |𝑆 | ⩽ (𝛼 (𝑑 + 1) + 1) · OPTΠ (𝐺). 1: 𝑆 ← ∅ 2: Each vertex 𝑢 computes 𝐺 [𝑁 𝑇 [𝑢]] and checks whether it belongs to 𝒞; as a consequence, it decides whether it belongs to 𝑋 . 3: Each vertex 𝑢 runs A for 𝑟 rounds, and gets added to 𝑆 only if 𝑢 ∈ A(𝐺) \ 𝑋 . 4: 𝑆 ← 𝑆 ∪𝑆 ′ , where 𝑆 ′ is a brute-forced minimum set of 𝐺 that satisfies the constraints of vertices that are non-satisfied.

is no 𝑇 -errors (𝑋 = ∅). Moreover, by definition of the coloring, |A(𝐺) \ 𝑋 | = In other words, |B(𝐺)| ⩽

𝑑 ∑︁ 𝑖=0

 |(A(𝐺) ∩ 𝐶𝑖 ) \ 𝑋 | +

0 OPTΠ (𝐺)

Í𝑑

𝑖=0 |(A(𝐺) ∩ 𝐶𝑖 ) \ 𝑋 |.

if 𝑋 = ∅ otherwise

(1)

To upper bound the term |(A(𝐺) ∩ 𝐶𝑖 ) \ 𝑋 |, consider some color 𝑖 ∈ {0, 1, . . . , 𝑑 } and some component 𝐶 ∈ ℭ𝑖 such that 𝐶 ⊈ 𝑋 . Consider some 𝑣𝐶 ∈ 𝐶 \ 𝑋 , and denote 𝐺𝐶 = 𝐺 [𝑁 𝑇 [𝑣𝐶 ]]. Note that, by definition of 𝑋 and as 𝑣 ∉ 𝑋 , we have 𝐺𝐶 ∈ 𝒞. Moreover, let ℭ𝑖′ = {𝐶 ∈ ℭ𝑖 | 𝐶 ⊈ 𝑋 } and let Ð 𝐺 ′ = 𝐺 [ 𝐶 ∈ℭ𝑖′ 𝑁 𝑇 [𝑣𝐶 ]] be the union of the 𝐺𝐶 ’s for 𝐶 ∈ ℭ𝑖 such that 𝐶 ⊈ 𝑋 . Along the proof, we will use several times the following fact: Fact C.1. For any graph 𝐻 and 𝑊 ⊆ 𝑉 (𝐻 ), to satisfy the constraints of vertices of 𝑊 in 𝐻 , it is enough to select vertices taken from 𝑁 𝜌 [𝑊 ]. In the following, to differentiate the neighborhoods in 𝐺 and in 𝐺𝐶 or 𝐺 ′ , we write them using either 𝑁𝐺 , 𝑁𝐺𝐶 , or 𝑁𝐺 ′ notations. Notice that, for each non-negative integer 𝑡 ⩽ max {𝑘 + 𝜌, 𝑟 }, we have 𝐺 [𝑁𝐺𝑡 [𝐶]] ⊆ 𝐺𝐶 . This is because 𝐶 has weak diameter in 𝐺 at most 𝑓 (2𝑘 + 2𝜌) and thus 𝐺 [𝑁𝐺𝑡 [𝐶]] has weak diameter in 𝐺 at most 𝑓 (2𝑘 + 2𝜌) + 𝑡 ⩽ 𝑇 , by the choice of 𝑇 . Moreover, as 𝒞 is hereditary, we have that 𝐺 [𝑁𝐺𝑡 [𝐶]] ∈ 𝒞. As 𝐺 [𝑁𝐺𝑡 [𝐶]] ⊆ 𝐺𝐶 , vertices in 𝐶 have the same distance 𝑡-neighborhood in 𝐺 and 𝐺𝐶 . In particÐ Ð ular, 𝐺 [𝑁𝐺𝑡 [𝐶]] = 𝐺𝐶 [𝑁𝐺𝑡 𝐶 [𝐶]] and 𝐺 [𝑁𝐺𝑡 [ ℭ𝑖′ ]] = 𝐺 ′ [𝑁𝐺𝑡 ′ [ ℭ𝑖′ ]]. From Fact C.1, any minimum set of vertices of 𝐺 that satisfies the constraints of 𝑁𝐺𝑘 [𝐶] is contained in 𝐺 [𝑁𝐺 [𝐶]], and similarly if we replace 𝐺 by 𝐺𝐶 . It follows that OPTΠ (𝐺, 𝑁𝐺𝑘 [𝐶]) = OPTΠ (𝐺𝐶 , 𝑁𝐺𝑘 𝐶 [𝐶]). Recall that any two 𝑘+𝜌

connected components 𝐶, 𝐶 ′ ∈ ℭ𝑖 are at distance in 𝐺 at least 2𝑘 + 2𝜌 + 1. So 𝐺 [𝑁𝐺 [𝐶]] and 𝑘+𝜌 𝐺 [𝑁𝐺 [𝐶 ′ ]] are disjoint subgraphs, and, as to satisfy all constraints of vertices in 𝑉 (𝐺), one needs to satisfy constraints of vertices in 𝑁𝐺𝑘 [𝐶] and 𝑁𝐺𝑘 [𝐶 ′ ], by disjunction of these sets and by Fact C.1, we have by summing over all 𝐶 ∈ ℭ𝑖 that  hØ i   hØ i  OPTΠ 𝐺, 𝑁𝐺𝑘 ℭ𝑖′ = OPTΠ 𝐺 ′, 𝑁𝐺𝑘 ′ ℭ𝑖′ . 𝑘+𝜌

Meta-Theorems for Cuttable Distributed Problems

21

Moreover, because 𝒞 is stable by disjoint union and that 𝐺 [𝑁𝐺𝑡 [𝐶]] ∈ 𝒞 for every 𝐶 ∈ ℭ𝑖′ , we get Ð 𝐺 [𝑁𝐺𝑡 [ ℭ𝑖′ ]] ∈ 𝒞. Therefore, as A is a 𝑘-uniform 𝛼-approximation on 𝒞, we get  hØ i   hØ i  Ø A(𝐺 ′ ) ∩ ℭ𝑖′ ⩽ 𝛼 · OPTΠ 𝐺 ′, 𝑁𝐺𝑘 ′ ℭ𝑖′ = OPTΠ 𝐺, 𝑁𝐺𝑘 ℭ𝑖′ . Ð Ð Since 𝐺 [𝑁𝐺𝑟 [ ℭ𝑖′ ]] = 𝐺 ′ [𝑁𝐺𝑟 ′ [ ℭ𝑖′ ]], Algorithm A, which runs in 𝑟 rounds, returns the same Ð Ð Ð vertex set in 𝐺 and 𝐺 ′ for vertices in ℭ𝑖′ . Therefore, A(𝐺) ∩ ℭ𝑖′ = A(𝐺 ′ ) ∩ ℭ𝑖′ . Combining with the previous inequality, we get A(𝐺) ∩

Ø

 hØ i  ℭ𝑖′ ⩽ 𝛼 · OPTΠ 𝐺, 𝑁𝐺𝑘 ℭ𝑖′ ⩽ 𝛼 · OPTΠ (𝐺, 𝑉 (𝐺)) = 𝛼 · OPTΠ (𝐺) .

We remark that |(A(𝐺) ∩ 𝐶) \ 𝑋 | = 0 if 𝐶 ⊆ 𝑋 . Because all vertices in 𝐶𝑖 but not in 𝑋 are in some 𝐶 ∈ ℭ𝑖′ , we have |(A(𝐺) ∩ 𝐶𝑖 ) \ 𝑋 | ⩽ A(𝐺) ∩

Ø

ℭ𝑖′ ⩽ 𝛼 · OPTΠ (𝐺) .

(2)

Putting Eq. (2) in Eq. (1), we get that Algorithm B is an (𝛼 (𝑑 + 1) + 1)-approximation, and even an 𝛼 (𝑑 + 1)-approximation if 𝑋 = ∅. To see that B is also a 𝑘-uniform approximation, it is sufficient to see that, for any 𝑊 ⊆ 𝑉 (𝐺), the bound obtained is |B(𝐺) ∩ 𝑊 | ⩽ 𝛼 (𝑑 + 1) · OPTΠ (𝐺, 𝑁𝐺𝑘 [𝑊 ]) + OPTΠ (𝐺, 𝑁𝐺 [𝑊 ]) where the first two terms are due to running A and the last term is due to running the brute-force. Indeed, if 𝜌 the brute-force computed a set whose intersection with 𝑊 was smaller than OPTΠ (𝐺, 𝑁𝐺 [𝑊 ]), we 𝜌 could replace it by the minimum size set satisfying the constraints of the vertices in 𝑁𝐺 [𝑊 ] and obtain a smaller set, a contradiction. This proves that B is a max{𝑘, 𝜌 }-uniform with an approximate ratio 𝛼 (𝑑 + 1) + 1 (or 𝛼 (𝑑 + 1) if 𝑋 = ∅, as the brute-force is not required in that case). Now, let us prove that Algorithm B has the desired round complexity. • Computing 𝑋 in Step 2 takes 𝑇 + 1 rounds. • Running A in Step 3 takes 𝑟 rounds. • For Step 4, consider the set 𝑆 computed by B at Step 3, before the brute-force. Observe that 𝜌 the vertices in the set 𝑊 = 𝑉 (𝐺) \ 𝑁𝐺 [𝑋 ] are satisfied by 𝑆. This is because vertices of 𝑊 𝜌 are at distance at least 𝜌 + 1 from 𝑋 and thus vertices of 𝑁𝐺 [𝑊 ] cannot be in 𝑋 . Thus, A 𝜌 applies to all vertices of 𝑁𝐺 [𝑊 ], and so 𝑊 is indeed satisfied by 𝑆 (Fact C.1). Therefore, 𝜌 2𝜌 to satisfy 𝑁𝐺 [𝑋 ] it is enough to select a set 𝑆 ′ from 𝑁𝐺 [𝑋 ] (Fact C.1) as done in Step 4. 2𝜌 By assumption, the connected components of 𝑁𝐺 [𝑋 ] have weak diameter in 𝐺 at most 𝛿 (obviously, if 𝑋 = ∅ then 𝛿 = 0). Therefore, the brute-force (Step 5) will take at most 𝛿 + 1 rounds. Naively, Steps 2 and 3 together take (𝑇 + 1) + 𝑟 rounds. As Algorithm A is not guaranteed to work when executed on vertices of 𝑋 , Step 3 must be run only after Step 2. However, both steps can be run in parallel as follows. We run A for 𝑟 rounds exactly and stop it just after (since its running time on a vertex of 𝑋 could result into more than 𝑟 rounds). Then, the decision to add 𝑢 in 𝑆 (if selected by A) is delayed for the next 𝑇 + 1 − 𝑟 rounds (this is non-negative from the choice of 𝑇 ). In parallel, 𝐺 [𝑁 𝑇 [𝑢]] is computed and is checked to be in 𝒞 or not after 𝑇 + 1 rounds. So, after max {𝑟,𝑇 + 1} = 𝑇 + 1 rounds, set 𝑆 in Step 3 has been completed. Step 4 takes 𝛿 + 1 steps, so that the total round complexity of B is 𝑇 + 𝛿 + 2, completing the proof. □

22

Marthe Bonamy, Avinandan Das, Cyril Gavoille, Timothé Picavet, Jukka Suomela, and Alexandra Wesolek

C.3

Minimum Dominating Set is uniformizable

Proposition C.2. Let 𝒞 be a hereditary class of unbounded degree29 and that is closed by disjoint union. Then, the Minimum Dominating Set problem is uniformizable in the LOCAL model with binding function (𝑟, 𝛼) ↦→ (𝑟 + 1, 𝛼 + 𝜀) for any real 𝜀 > 0. Proof. We first prove this statement in the LOCAL model with 𝜀 = 0. Assume for sake of contradiction that there exists integers 𝑑, 𝑟 and a real 𝛼 such that for all integers 𝑘 and real 𝛽, there exists an 𝑟 -round 𝛼-approximation A of Π in constant time on the hereditary graph class 𝒞 such that A is not 𝑘-uniform with 𝛽-approximation of Π in constant time. Here, we will take 𝑘 = 𝑟 + 1 and 𝛽 = 𝛼. By the definition of uniformity, this means that there exists some subset 𝑆 of vertices for which: |A(𝐺) ∩ 𝑆 | > 𝛼 · MDS(𝐺, 𝑁 𝑘 [𝑆]). Let us cut 𝐺 around 𝑆: set 𝐺 ′ := 𝐺 [𝑁 𝑘 [𝑆] ∪ 𝑋 ] where 𝑋 ⊆ 𝑁 𝑘+1 [𝑆] is a minimum dominating set of 𝑁 𝑘 [𝑆] in 𝐺. We keep the same identifiers in 𝐺 ′ as in 𝐺. We first bound the size of the minimum dominating set of 𝐺 ′ . Claim C.3. MDS(𝐺 ′ ) ⩽ MDS(𝐺, 𝑁 𝑘 [𝑆]). Proof of claim. By definition of 𝑋 , it follows that |𝑋 | = MDS(𝐺, 𝑁 𝑘 [𝑆]). 𝑋 is also a dominating set of 𝐺 ′ , because each of its vertices is either in 𝑋 or in 𝑁 𝑘 [𝑆], and that in the second case, it is dominated by some vertex of 𝑋 by definition of 𝑋 . Therefore, MDS(𝐺 ′ ) ⩽ |𝑋 | = MDS(𝐺, 𝑁 𝑘 [𝑆]). ⋄ As our goal is to get a contradiction on 𝐺 ′ ∈ 𝒞 30 instead of 𝐺, we prove the following. Claim C.4. On 𝑆, algorithm A returns the same set in 𝐺 and in 𝐺 ′ . This will prove that |A(𝐺) ∩ 𝑆 | = |A(𝐺 ′ ) ∩ 𝑆 |. Proof of claim. A is an 𝑟 -round algorithm. Therefore, vertices in 𝑆 only see vertices and edges in 𝐺 [𝑁 𝑟 [𝑆]], and edges between vertices of 𝑁 𝑟 (𝑆) and vertices of 𝑁 𝑟 +1 (𝑆) 31 . All of those are the ⋄ same in 𝐺 and 𝐺 ′ , therefore A(𝐺) ∩ 𝑆 = A(𝐺 ′ ) ∩ 𝑆, as wanted. By Claim C.4, |A(𝐺 ′ )| ⩾ |A(𝐺 ′ ) ∩ 𝑆 | = |𝐴(𝐺) ∩ 𝑆 | > 𝛼 MDS(𝐺, 𝑁 𝑘 [𝑆]). By Claim C.3, we have 𝛼 MDS(𝐺, 𝑁 𝑘 [𝑆]) ⩾ 𝛼 · MDS(𝐺 ′ ). It follows that |A(𝐺 ′ )| ⩾ 𝛼 · MDS(𝐺 ′ ), a contradiction as 𝐺 ′ ∈ 𝒞 and A is an 𝛼-approximation on 𝒞. Let us now adapt this proof for the LOCAL model, for 𝜀 > 0. For now, by taking 𝛾 = 𝛼 + 𝜀, we have proved |A(𝐺 ′ )| ⩾ (𝛼 + 𝜀) · MDS(𝐺 ′ ). The only thing we need to take care of is that nodes in 𝐺 have identifiers that are bounded by a polynomial of |𝑉 (𝐺 ′ )|. Instead of changing the identifiers in 𝐺 ′ without impacting the output of A, which is tricky, we consider a bigger graph. Let 𝑁 be the biggest identifier in 𝐺 ′ . 𝒞 is a hereditary graph class of unbounded degree, so there exists a graph 𝐻 ∈ 𝒞 and a vertex 𝑣 of 𝐻 with degree at least 𝑁 .32 Take 𝐻 ′ = 𝐻 [𝑁𝐻 [𝑣]] and give the vertices identifiers in [𝑁 + 1, 2𝑁 ]. Let 𝐺 ′′ = 𝐺 ′ ⊔ 𝐻 ′ . 29 For a graph class in which every graph has maximum degree Δ, the LOCAL algorithm that includes all nodes is a

Δ + 1-approximation. This implies that the bounded-degree case is less interesting than the unbounded-degree one, which is therefore the focus of our study. 30 because 𝒞 is hereditary 31 The definition of an 𝑟 -round LOCAL algorithm running on vertex 𝑣 includes edges at distance 𝑟 + 1 of 𝑣 but not vertices at distance 𝑟 + 1 of 𝑣 in 𝐺. 32 Here, if the algorithm requires access to 𝑛 (the size of the graph), one needs to choose 𝑁 ⩾ 𝑛 and delete neighbors of 𝑣 so that, in the following, we get |𝑉 (𝐺 ′′ ) | = 𝑛.

Meta-Theorems for Cuttable Distributed Problems

23

Clearly, 𝐻 ′ can be dominated by choosing the single vertex 𝑣, i.e. MDS(𝐺 ′′ ) = MDS(𝐺 ′ ) + 1. Furthermore, A(𝐺 ′′ ) = A(𝐺 ′ ) ⊔ A(𝐻 ′ ) and it follows |A(𝐺 ′′ )| ⩾ (𝛼 + 𝜀) · MDS(𝐺 ′ ) + 1 = (𝛼 + 𝜀) · MDS(𝐺 ′′ ) + 1 − (𝛼 + 𝜀). Now, we can apply the same trick as in Proposition D.2. Observe that the diameter of each connected component of the graph 𝐺 ′ is at most 3 MDS(𝐺 ′ ). We construct an algorithm B where each vertex checks whether the diameter 𝐷 of its component is less than 3𝐵, for 𝐵 = (𝛼 − 1)/𝜀. This can be done by collecting its radius-3𝐵 neighborhood in 3𝐵 rounds. If true, the vertex locally brute forces an optimal solution for its component, which it already knows about. If false, the vertex applies the approximate algorithm A. If 𝐷 ⩽ 𝐵, then the algorithm is obviously a good approximation (with approximation ratio 1). Otherwise, 𝐷 > 3𝐵 and it follows that MDS(𝐺 ′ ) > 𝐵. One can verify that |A(𝐺 ′′ )| > 𝛼 · MDS(𝐺 ′′ ), a contradiction, as 𝐺 ′′ ∈ 𝒞. □ C.4

Minimum 𝑘-Tuple Dominating Set is cuttable and additive

Proposition C.5. Minimum 𝑘-Tuple Dominating Set is additive and cuttable with parameter 1. Proof. By definition, the problem is additive. Let us now prove cutability. Let 𝐺 be a graph and 𝑋 ⊆ 𝑉 (𝐺), and let 𝑆 be a 𝑘-Tuple Dominating Set of the set 𝑋 . Set 𝑌 = 𝑋 ∪ 𝑆. 𝑆 is a 𝑘Tuple Dominating Set of 𝐺 [𝑌 ]. Indeed, every vertex of 𝐺 [𝑌 ] that is in 𝑌 \ 𝑆 is in 𝑋 \ 𝑆, and therefore is 𝑘-Tuple Dominated by 𝑆. Thus for Π = Minimum 𝑘-Tuple Dominating Set, we have OPTΠ (𝐺, 𝑋 ) ⩾ OPTΠ (𝐺 [𝑌 ]). □ C.5

Distance-⩽𝑑 Dominating Set is cuttable

Proposition C.6. Distance-(⩽𝑑) Dominating Set is cuttable with parameter 1. Proof. Let Π be the Distance-(⩽𝑑) Dominating Set problem, let 𝐺 be a graph and 𝑋 a subset of vertices. Let 𝐷 be a minimum-size set that is distance-𝑑 dominating for the vertices in 𝑋 , so that |𝐷 | = OPTΠ (𝐺, 𝑋 ). Note that 𝐷 ⊆ 𝑁 𝑑 [𝑋 ]. We are going to construct a set 𝑋 ⊆ 𝑌 ⊆ 𝑁 𝑑 [𝑋 ] such OPTΠ (𝐺 [𝑌 ]) ⩽ OPTΠ (𝐺, 𝑋 ). We do this recursively. Start with 𝑌 := 𝑋 . We maintain the invariant that every vertex of 𝑌 that is not dominated by 𝐷 ∩ 𝑌 in 𝐺 [𝑌 ] is in 𝑋 . This invariant holds trivially for 𝑌 = 𝑋 . While some vertex 𝑣 of 𝑋 is not dominated in 𝐺 [𝑌 ] by 𝐷 ∩ 𝑌 , do the following. Let 𝑦 ∈ 𝐷 be a vertex that dominates 𝑣 in 𝐺, i.e., with the distance to 𝑦 at most 𝑑.Note that here, we do not have necessarily 𝑦 ∉ 𝑌 : it could be the case that 𝑣 is dominated by some 𝑦 ∈ 𝑋 in 𝐺 because of a path with a portion outside 𝑋 . As 𝑦 ∈ 𝐷 ⊆ 𝑁 𝑑 [𝑋 ], there is a path 𝑃 in 𝐺 [𝑁 𝑑 [𝑋 ]] from 𝑣 to 𝑦 with length at most 𝑑. Actually, one can just take the shortest 𝑣𝑦-path. It has length at most 𝑑 and is in 𝑁 𝑑 [𝑣] ⊆ 𝑁 𝑑 [𝑋 ]. Set 𝑌 := 𝑌 ∪ 𝑉 (𝑃). All vertices that are in 𝑃 (including 𝑣) are dominated by 𝑦, and therefore are now dominated in 𝐺 [𝑌 ]. The invariant is thus satisfied. Each time we do this operation, at least one more vertex of 𝑋 is dominated in 𝐺 [𝑌 ]. As 𝑋 is finite, this process terminates and we have constructed a set 𝑌 that is dominated by 𝐷 ∩ 𝑌 in 𝐺 [𝑌 ]. It follows that OPTΠ (𝐺 [𝑌 ]) ⩽ OPTΠ (𝐺, 𝑋 ), and this completes the proof. □ C.6

Cutting implies uniform algorithms in the LOCAL model with no polynomial identifiers requirement

A problem Π is uniformizable on 𝒞 if for all integers 𝑟 and all reals 𝛼, there exists some integers 𝑘 and real 𝛽 such that every 𝑟 -round 𝛼-approximation A of Π on 𝒞 is a 𝑘-uniform 𝛽-approximation of Π on 𝒞. The function (𝑟, 𝛼) ↦→ (𝑘, 𝛽) is called the binding function.

24

Marthe Bonamy, Avinandan Das, Cyril Gavoille, Timothé Picavet, Jukka Suomela, and Alexandra Wesolek

Proposition C.7. Let 𝒞 be a hereditary class that is closed by disjoint union, and let Π be a 𝜌-local problem which is cuttable with parameter 𝛽. Then, Π is uniformizable in the LOCAL model with no polynomial identifiers requirement with binding function (𝑟, 𝛼) ↦→ (𝑟 + 1, 𝛼 · 𝛽). Proof. Assume for sake of contradiction that there exist an integer 𝑟 and a real 𝛼 such that for all integers 𝑘, 𝑟 ′ and real 𝛾, there exists an 𝑟 -round 𝛼-approximation A of Π on the hereditary graph class 𝒞 but no 𝑟 ′ -round 𝑘-uniform 𝛾-approximation algorithm B for Π on 𝒞. Here, we take 𝑘 = 𝑟 + 1, 𝛾 = 𝛼 · 𝛽, 𝑟 ′ = 𝑟 and B = A, i.e. suppose A is not a 𝑘-uniform 𝛾-approximation of Π. By the definition of uniformity, this means that there exists some subset 𝑆 of vertices for which: |A(𝐺) ∩ 𝑆 | > 𝛼𝛽 · OPTΠ (𝐺, 𝑁 𝑘 [𝑆]). As Π is cuttable with the particular case 𝑋 = 𝑁 𝑘 [𝑆], there exists a set 𝑌 such that OPTΠ (𝐺 [𝑌 ]) ⩽ 𝛽 · OPTΠ (𝐺, 𝑁 𝑘 [𝑆]). We now study the graph 𝐺 ′ := 𝐺 [𝑌 ], with the same identifiers as in 𝐺. We prove the following. Claim C.8. We have A(𝐺) ∩ 𝑆 = A(𝐺 ′ ) ∩ 𝑆. Proof of claim. This is the same proof as in Claim C.4, except with a set 𝑌 instead. As A is an 𝑟 -round algorithm, vertices in 𝑆 only see vertices and edges in 𝐺 [𝑁 𝑟 [𝑆]], and edges between vertices of 𝑁 𝑟 (𝑆) and vertices of 𝑁 𝑟 +1 (𝑆). Those are the same in 𝐺 and 𝐺 ′ as 𝑁 𝑟 +1 [𝑆] = 𝑁 𝑘 [𝑆] ⊆ 𝑌 , and so we have A(𝐺) ∩ 𝑆 = A(𝐺 ′ ) ∩ 𝑆, as wanted. ⋄ By Claim C.8, |A(𝐺 ′ )| ⩾ |A(𝐺 ′ ) ∩ 𝑆 | = |𝐴(𝐺) ∩ 𝑆 | > 𝛼𝛽 · OPTΠ (𝐺, 𝑁 𝑘 [𝑆]). By the cutability, we have OPTΠ (𝐺 ′ ) ⩽ 𝛽 · OPTΠ (𝐺, 𝑁 𝑘 [𝑆]). It follows that |A(𝐺 ′ )| > 𝛼 · OPTΠ (𝐺 ′ ), a contradiction as 𝐺 ′ ∈ 𝒞 and A is an 𝛼-approximation on 𝒞. □ C.7

The algorithm of Heydt et al. is uniform

Observation C.9. The algorithm described in [HKOdM+ 25, Theorem 2.3] is a 𝑘 (𝜀)-uniform (11 + 𝜀)-approximation LOCAL algorithm for Minimum Dominating Set in planar graphs with round complexity 𝐶 (𝜀), for every 𝜀 > 0, and for some functions 𝐶 and 𝑘. Proof. Let us consider the algorithm described in [HKOdM+ 25, Theorem 2.3]. It has a number of rounds bounded by a function of 𝜀, and does not need polynomial identifiers so Observation C.9 follows by Proposition C.2. □ For the interested reader, here is a more detailed analysis of the running time of the algorithm. It returns a solution 𝐷 1 ∪𝐷 2 ∪𝐷 31 ∪𝐷 32 . 𝐷 1 can be computed in two rounds, 𝐷 2 in two additional rounds, and 𝐷 31 in one more additional round. The set 𝐷 32 can be computed in time 𝑂 (log Δ/log(1 + 𝜀)) where Δ = 4∇1 · (4∇1 + 2∇1 ) (Δ𝑅 + 1)/𝜀 with (with the particular case of planar graphs) ∇1 < 3 and Δ𝑅 = 𝜅 𝑠 −1 (𝑡 + 𝑠 − 1 + (𝑠 − 1)𝜅 3 ) with 𝜅 = max{2∇0, 2∇}. Again, for planar graphs, ∇0 < 3 and ∇ ⩽ 2 so 𝜅 ⩽ 6. It follows that Δ𝑅 ⩽ 15732 because 𝑠 = 𝑡 = 3 on planar graphs. So Δ ⩽ 13593312/𝜀 = 𝑂 (1/𝜀) and the running time is 𝑂 (log(1/𝜀)/log(1 + 𝜀/2)) = 𝑂 (log(1/𝜀)/𝜀).

Meta-Theorems for Cuttable Distributed Problems

C.8

25

Cutability implies weakly uniform algorithms

Corollary C.10. Let 𝒞 be a hereditary class closed by disjoint union, and let Π be a 𝜌-local problem which is cuttable with parameter 𝛽. Then, for any real 𝜀 > 0, the problem Π is 𝜀-weakly uniformizable in the LOCAL model with (weak) binding function (𝑟, 𝛼) ↦→ (𝑟 + 1, 𝛼 · 𝛽). Proof. Let us go through the proof of Proposition C.7 one more time. For sake of brevity, we do not copy the whole identical proof, but instead give a summary of the proof. Assume for sake of contradiction that there exists integers 𝑑, 𝑟 and a real 𝛼 such that for all integers 𝑘 and real 𝛾, there exists an 𝑟 -round 𝛼-approximation A of Π in constant time on the hereditary graph class 𝒞 such that A is not 𝜀-weakly 𝑘-uniform with 𝛾-approximation of Π in constant time. Here, we will take 𝑘 = 𝑟 + 1 and 𝛾 = 𝛼 · 𝛽. By the definition of weak uniformity, this means that there exists some subset 𝑆 ⊆ 𝑉 (𝐺) of size at least 𝜀 |𝑉 (𝐺)| for which: |A(𝐺) ∩ 𝑆 | > 𝛼𝛽 · OPTΠ (𝐺, 𝑁 𝑘 [𝑆]) . We have showed there exists a set 𝑌 such that 𝛽 · OPTΠ (𝐺, 𝑁 𝑘 [𝑆]) ⩾ OPTΠ (𝐺 [𝑌 ]). Let 𝐺 ′ := 𝐺 [𝑌 ]. We keep the same identifiers in 𝐺 ′ as in 𝐺. We have showed that |A(𝐺 ′ )| ⩾ 𝛼 · OPTΠ (𝐺 ′ ), which would be a contradiction with the fact that 𝛼-approximation on 𝒞, if A was an algorithm in the LOCAL model with no polynomial identifiers requirement. For this to be a contradiction in the LOCAL model, we have to show that the IDs in 𝐺 ′ are also polynomial in |𝑉 (𝐺 ′ )|. Now, we just use the additional property that 𝑆 has large size. All the identifiers in 𝐺 ′ are polynomial in |𝑉 (𝐺)|, say smaller than 𝐷 · |𝑉 (𝐺)|𝑐 for some real 𝑐 > 0. As |𝑉 (𝐺 ′ )| ⩾ |𝑆 | ⩾ 𝜀 · |𝑉 (𝐺)|, the identifier in 𝐺 ′ are smaller than 𝐷 · |𝑉 (𝐺 ′ )|𝑐 /𝜀 𝑐 , which is still polynomial. This finishes the proof. □ C.9

Bounded Euler genus graphs are locally nice

Proposition C.11. Let Π be a 𝜌-local problem. Then, for any 𝑔 ⩾ 1, the class of Euler genus-𝑔 graphs is 𝑇 -locally 𝛿-nice w.r.t. planar graphs and Π, where 𝛿 < 𝑔 · (2𝑇 + 4𝜌 + 1). Proof. To derive a contradiction, consider a connected component 𝐻 of 𝐺 [𝑁 2𝜌 [𝑋 ]], and assume that 𝐻 has weak diameter 𝛿 ⩾ 𝑔 · (2𝑇 + 4𝜌 + 1) in 𝐺. As 𝑔 ⩾ 1, 𝑋 and 𝐻 are not empty, and 𝐻 is not planar. So, 𝐻 must contain some path 𝑃 such that the distance in 𝐺 between its endpoints, say 𝑠 to 𝑡, is 𝛿. In particular, for each 𝑑 ∈ {0, 1, . . . , 𝛿 }, there must exist a vertex of 𝑃 that is at distance exactly 𝑑 in 𝐺 from 𝑠. This is because the distance in 𝐺 from 𝑠, when moving along an edge of 𝑃, is a function that can vary by at most one unit, and this distance goes from 0 (at 𝑠) to 𝛿 (at 𝑡). For every 𝑖 ∈ {0, 1, . . . , 𝑔}, let 𝑢𝑖 be any vertex of 𝑃 at distance exactly 𝑑𝑖 = 𝑖 · (2𝑇 + 4𝜌 + 1) in 𝐺 from 𝑠. So 𝑢 0 = 𝑠, 𝑢𝑔 = 𝑡, and all the 𝑢𝑖 ’s exist in 𝑃 (so in 𝐻 ) since 𝑑𝑖 ∈ {0, 1, . . . , 𝛿 }. By definition of 𝐻 , each 𝑢𝑖 intersects 𝑁 2𝜌 [𝑋 ]. So, for each 𝑢𝑖 one can select a vertex 𝑥𝑖 ∈ 𝑋 at distance in 𝐺 at most 2𝜌 from 𝑢𝑖 . By the triangle inequality, for all 0 ⩽ 𝑖 < 𝑗 ⩽ 𝑔, 𝑥𝑖 and 𝑥 𝑗 are at distance in 𝐺 at least (𝑑 𝑗 − 2𝜌) − (𝑑𝑖 + 2𝜌) = ( 𝑗 − 𝑖) · (2𝑇 + 4𝜌 + 1) − 4𝜌 ⩾ 2𝑇 + 1. It follows that 𝑁 𝑇 [𝑥𝑖 ] and 𝑁 𝑇 [𝑥 𝑗 ] are disjoint. By definition of 𝑋 and 𝐻 , the subgraphs 𝐺 [𝑁 𝑇 [𝑥𝑖 ]]’s are not planar, thus of Euler genus ⩾ 1. By additivity of the Euler genera33 of these 𝑔 + 1 pairwise disjoint subgraphs of 𝐺 (cf. [MT01, Theorem 4.4.3]), we get a contradiction that 𝐺 has Euler genus 𝑔. Thus 𝛿 < 𝑔 · (2𝑇 + 4𝜌 + 1) as claimed. □ 33 The plural of genus.

26

Marthe Bonamy, Avinandan Das, Cyril Gavoille, Timothé Picavet, Jukka Suomela, and Alexandra Wesolek

C.10

Balanced asymptotic dimension

Lemma C.12. Let 𝒢 be a graph class with asymptotic dimension at most 𝑑 and control function 𝑓 . For every graph 𝐺 ∈ 𝒢 with 𝑛 vertices and every integer 𝑟 ⩾ 1, there exists a cover 𝐶 0, 𝐶 1, . . . , 𝐶𝑑 of 𝑉 (𝐺) such that • every 𝑟 -component of each 𝐶𝑖 has weak diameter in 𝐺 at most 𝑓 (3𝑟 ) + 2𝑟 , and  𝑛  • for every 𝑖 ∈ {0, . . . , 𝑑 } we have |𝐶𝑖 | ⩾ 𝑑+1 .  𝑛  and 𝑟 be any integer. By Proposition 2.1 applied to scale 3𝑟 , there exists a Proof. Let 𝑞 := 𝑑+1 (𝑑 + 1)-coloring of 𝐺 3𝑟 whose monochromatic components have weak diameter at most 𝑓 (3𝑟 ) (as they have weak diameter 𝑓 (3𝑟 ) in 𝐺 3𝑟 ) in 𝐺. Let 𝐶 0, 𝐶 1, . . . , 𝐶𝑑 be the corresponding color classes, with |𝐶 0 | ⩽ |𝐶 1 | ⩽ · · · ⩽ |𝐶𝑑 | without loss of generality. They form a cover of 𝑉 (𝐺), and every 3𝑟 -component of each 𝐶𝑖 has weak diameter at most 𝑓 (3𝑟 ) in 𝐺. We construct sets 𝐶 0′ , . . . , 𝐶𝑑′ by proving the following by induction of 𝑖. For every 𝑖, there exists sets 𝐶 0′ , . . . , 𝐶𝑖′−1 such that (I1) for every 𝑗 ⩽ 𝑖, we have |𝐶 ′𝑗 | ⩾ 𝑞, and if |𝐶 ′𝑗 | > 𝑞 then 𝐶 ′𝑗 = 𝐶 𝑗 , (I2) every 𝑟 -component of each 𝐶 ′𝑗 (for 𝑗 ⩽ 𝑖) has weak diameter at most 𝑓 (3𝑟 ) + 2𝑟 in 𝐺, and Ø Ø (I3) 𝐶 ′𝑗 ⊇ 𝐶𝑗 . 𝑗⩽𝑖

𝑗⩽𝑖

Note that (I3) says that the sets 𝐶 0′ , . . . , 𝐶𝑖′ cover at least every vertex of 𝐶 0, . . . , 𝐶𝑖 . For 𝑖 = 0 these conditions are trivially satisfied. Assume the conditions hold for some 𝑖 ∈ {0, . . . , 𝑑 }. Let 𝐴 := 𝑁 𝑟 [𝐶𝑖 ] \ 𝐶𝑖 and 𝐵 := (𝑉 (𝐺) \ 𝑁 𝑟 [𝐶𝑖 ]) \ 𝐶𝑖 , such that 𝐴 ⊔ 𝐵 = 𝑉 (𝐺) \ 𝐶𝑖 . Intuitively, we will try to add vertices to 𝑈 from 𝐴 whenever possible (these are within distance 𝑟 of the original 𝐶𝑖 ), and otherwise take vertices from 𝐵 (which are farther from 𝐶𝑖 ). If |𝐶𝑖 | ⩾ 𝑞, then take 𝐶 ′𝑗 = 𝐶 𝑗 for all 𝑗 ⩾ 𝑖. (I1) is satisfied because 𝑞 ⩽ |𝐶𝑖 | ⩽ · · · ⩽ |𝐶𝑑 |. (I2) is satisfied because the 𝐶𝑖 ’s have all weak diameter at most 𝑓 (3𝑟 ), and (I3) is trivially satisfied. So assume |𝐶𝑖 | < 𝑞 and let 𝑠 := 𝑞 − |𝐶𝑖 | > 0 be the number of new vertices we must add to 𝐶𝑖 to reach size 𝑞. There are two possibilities. • Case 1: |𝐴| ⩾ 𝑠. Choose an arbitrary set 𝑋 ⊆ 𝐴 of size 𝑠 and let 𝐶𝑖′ := 𝐶𝑖 ∪ 𝑋 ; this satisfies (I1) and (I3). Let us prove (I2). Let 𝑥, 𝑥 ′ ∈ 𝐴 be two vertices in the same 𝑟 -component of 𝐶𝑖′ . As 𝐶𝑖′ ⊆ 𝑁 𝑟 [𝐶𝑖 ], there exist 𝑦, 𝑦 ′ ∈ 𝐶𝑖 such that 𝑑 (𝑥, 𝑦), 𝑑 (𝑥 ′, 𝑦 ′ ) ⩽ 𝑟 . We first prove that 𝑦 and 𝑦 ′ are in the same 3𝑟 -component of 𝐶𝑖 . Because 𝑥 and 𝑥 ′ are in the same 𝑟 -component of 𝐶𝑖′ , exists a sequence 𝑥 = 𝑥 1, 𝑥 2, . . . , 𝑥𝑡 = 𝑥 ′ in 𝐶𝑖′ with 𝑑 (𝑥 𝑗 , 𝑥 𝑗+1 ) ⩽ 𝑟 for all 𝑗. As 𝐶𝑖′ ⊆ 𝑁 𝑟 [𝐶𝑖 ], we can choose, for each 𝑗, some 𝑦 𝑗 ∈ 𝐶𝑖 such that 𝑑 (𝑥 𝑗 , 𝑦 𝑗 ) ⩽ 𝑟 . Without loss of generality, choose 𝑦1 := 𝑦 and 𝑦𝑡 := 𝑦 ′ . Then for any 𝑗, we have that 𝑑 (𝑦 𝑗 , 𝑦 𝑗+1 ) ⩽ 𝑑 (𝑦 𝑗 , 𝑥 𝑗 ) + 𝑑 (𝑥 𝑗 , 𝑥 𝑗+1 ) + 𝑑 (𝑥 𝑗+1, 𝑦 𝑗+1 ) ⩽ 3𝑟, and so 𝑦 and 𝑦 ′ are in the same 3𝑟 -component of 𝐶𝑖 , which means that 𝑑 (𝑦, 𝑦 ′ ) ⩽ 𝑓 (3𝑟 ). Hence 𝑑 (𝑥, 𝑥 ′ ) ⩽ 𝑑 (𝑥, 𝑦) + 𝑑 (𝑦, 𝑦 ′ ) + 𝑑 (𝑦 ′, 𝑥 ′ ) ⩽ 𝑟 + 𝑓 (3𝑟 ) + 𝑟 = 𝑓 (3𝑟 ) + 2𝑟, as required. This proves (I2).

Meta-Theorems for Cuttable Distributed Problems

27

• Case 2: |𝐴| < 𝑠. Then by definition of 𝐵, |𝐵| ⩾ |𝑉 (𝐺)| − |𝐴| − |𝐶𝑖 | ⩾ 𝑛 − 𝑠 + 1 − |𝐶𝑖 | = 𝑛 − 𝑞 + 1. As the sets 𝐶 𝑗 for 𝑗 ≠ 𝑖 cover 𝐵, there exists some 𝑗 ≠ 𝑖 such that |𝐶 𝑗 ∩ 𝐵| ⩾ (𝑛 −𝑞 + 1)/𝑑 ⩾ 𝑞. Choose an arbitrary set 𝑋 ⊆ 𝐶 𝑗 ∩ 𝐵 of size 𝑠 and let 𝐶𝑖′ := 𝐶𝑖 ∪ 𝑋 ; this satisfies (I1) and (I3). (I2) is true all 𝑟 -components of 𝐶𝑖′ are either 𝑟 -components of 𝐶𝑖 (so they have diameter at most 𝑓 (3𝑟 )) or are subsets of 𝑟 -components of 𝐶 𝑗 (and the same diameter bound applies). Ð In both cases we have constructed sets 𝐶𝑖′ that satisfies (I1), (I2) and (I3). By (I3), 𝑑𝑖=0 𝐶𝑖′ = Ð𝑑 ′ 𝑖=0 𝐶𝑖 = 𝑉 (𝐺), so the 𝐶𝑖 form a cover. (I1) and (I2) prove the two wanted conditions on the cover. This finishes the proof. □ C.11

Meta-theorem for non-paddable problems with empty error set

1 Theorem A.1 (Meta-Theorem II). Let 𝑑, 𝑘 be integers 𝛼 > 0 a real, A be a 𝑑+1 -weakly 𝑘-uniform 𝛼approximation LOCAL algorithm for a 𝜌-local problem Π in a class of graphs 𝒞 with round complexity 𝑟 , where 𝒞 is hereditary and stable by disjoint union. Let 𝒟 be a graph class of asymptotic dimension 𝑑 with 𝑑-dimensional control function 𝑓 , that is 𝑇 -locally-𝒞 for 𝑇 = 𝑓 (6𝑘 +6𝜌) +4𝑘 +4𝜌 +max {𝑘 + 𝜌, 𝑟 }. Then A is a 𝑘-uniform 𝛼 (𝑑 + 1)-approximation algorithm on 𝒟.

Proof. Let 𝐺 ∈ 𝒟 and set ℓ := 𝑓 (6𝑘 + 6𝜌) + 4𝑘 + 4𝜌. As 𝒟 has 𝑑-dimensional control function 2𝑘+2𝜌 admits a (𝑑 + 1)-coloring ℓ-bounded in 𝐺 where 𝑓 , then by Lemma C.12, one can assume  𝑛  𝐺 every color class has size at least 𝑑+1 . Fix such a coloring, and, for each 𝑖 ∈ {0, 1, . . . , 𝑑 }, let 𝐶𝑖  𝑛  be the set of color-𝑖 vertices in 𝐺 2𝑘+2𝜌 (and also in 𝐺), so that |𝐶𝑖 | ⩾ 𝑑+1 . We denote by ℭ𝑖 the set of (2𝑘 + 2𝜌)-components of 𝐶𝑖 (i.e. connected components of 𝐺 2𝑘+2𝜌 [𝐶𝑖 ]). So, by definition, all components of ℭ𝑖 have weak diameter in 𝐺 at most ℓ, and are pairwise at distance at least 2𝑘 + 2𝜌 + 1 in 𝐺 (because distinct components of ℭ𝑖 cannot be adjacent in 𝐺 2𝑘+2𝜌 ). We run Algorithm A on 𝐺. It is easy to check that A(𝐺) is a valid solution for 𝐺, because 𝒟 is 𝑇 -locally-𝒞. By definition of the coloring, |A(𝐺)| =

𝑑 ∑︁

(3)

|A(𝐺) ∩ 𝐶𝑖 | .

𝑖=0

To upper bound the term |A(𝐺) ∩ 𝐶𝑖 |, consider some color 𝑖 ∈ {0, 1, . . . , 𝑑 } and some component 𝐶 ∈ ℭ𝑖 . Consider some 𝑣𝐶Ð∈ 𝐶, and denote 𝐺𝐶 = 𝐺 [𝑁 𝑇 [𝑣𝐶 ]]. Note that as 𝒟 is 𝑇 -locally-𝒞, we have 𝐺𝐶 ∈ 𝒞. Let 𝐺 ′ = 𝐺 [ 𝐶 ∈ℭ𝑖 𝑁 𝑇 [𝑣𝐶 ]] be the union of the 𝐺𝐶 ’s for 𝐶 ∈ ℭ𝑖 . Along the proof, we will use several times the following fact: Fact C.1. For any graph 𝐻 and 𝑊 ⊆ 𝑉 (𝐻 ), to satisfy the constraints of vertices of 𝑊 in 𝐻 , it is enough to select vertices taken from 𝑁 𝜌 [𝑊 ]. In the following, to differentiate the neighborhoods in 𝐺 and in 𝐺𝐶 or 𝐺 ′ , we write them using either 𝑁𝐺 , 𝑁𝐺𝐶 , or 𝑁𝐺 ′ notations. Notice that, for each non-negative integer 𝑡 ⩽ max {𝑘 + 𝜌, 𝑟 }, we have 𝐺 [𝑁𝐺𝑡 [𝐶]] ⊆ 𝐺𝐶 . This is because 𝐶 has weak diameter in 𝐺 at most ℓ = 𝑓 (6𝑘 + 6𝜌) + 4𝑘 + 4𝜌 and thus 𝐺 [𝑁𝐺𝑡 [𝐶]] has weak diameter in 𝐺 at most 𝑓 (6𝑘 + 6𝜌) + 4𝑘 + 4𝜌 + 𝑡 ⩽ 𝑇 , by the choice of 𝑇 . Moreover, as 𝒞 is hereditary, we have that 𝐺 [𝑁𝐺𝑡 [𝐶]] ∈ 𝒞. As 𝐺 [𝑁𝐺𝑡 [𝐶]] ⊆ 𝐺𝐶 , vertices in 𝐶 have the same distance 𝑡-neighborhood in 𝐺 and 𝐺𝐶 . In particular, 𝐺 [𝑁𝐺𝑡 [𝐶]] = 𝐺𝐶 [𝑁𝐺𝑡 𝐶 [𝐶]] and 𝐺 [𝑁𝐺𝑡 [𝐶𝑖 ]] = 𝐺 ′ [𝑁𝐺𝑡 ′ [𝐶𝑖 ]]. From Fact C.1, any minimum set of vertices of 𝐺 that satisfies the constraints of 𝑁𝐺𝑘 [𝐶] is contained in 𝐺 [𝑁𝐺

𝑘+𝜌

[𝐶]], and similarly

28

Marthe Bonamy, Avinandan Das, Cyril Gavoille, Timothé Picavet, Jukka Suomela, and Alexandra Wesolek

if we replace 𝐺 by 𝐺𝐶 . It follows that OPTΠ (𝐺, 𝑁𝐺𝑘 [𝐶]) = OPTΠ (𝐺𝐶 , 𝑁𝐺𝑘 𝐶 [𝐶]). Recall that any two connected components 𝐶, 𝐶 ′ ∈ ℭ𝑖 are at distance in 𝐺 at least 2𝑘 + 2𝜌 + 1. So 𝐺 [𝑁𝐺 [𝐶]] and 𝑘+𝜌 𝐺 [𝑁𝐺 [𝐶 ′ ]] are disjoint subgraphs, and, as to satisfy all constraints of vertices in 𝑉 (𝐺), one needs to satisfy constraints of vertices in 𝑁𝐺𝑘 [𝐶] and 𝑁𝐺𝑘 [𝐶 ′ ], by disjunction of these sets and by Fact C.1, we have by summing over all 𝐶 ∈ ℭ𝑖 that 𝑘+𝜌

OPTΠ (𝐺, 𝑁𝐺𝑘 [𝐶𝑖 ]) = OPTΠ (𝐺 ′, 𝑁𝐺𝑘 ′ [𝐶𝑖 ]). Moreover, because 𝒞 is stable by disjoint union and that 𝐺 [𝑁𝐺𝑡 [𝐶]] ∈ 𝒞 for every 𝐶 ∈ ℭ𝑖′ , we get 1 𝐺 [𝑁𝐺𝑡 [𝐶𝑖 ]] ∈ 𝒞. As Algorithm A is a 𝑑+1 -weakly 𝑘-uniform 𝛼-approximation on 𝒞, that 𝐺 ′ ∈ 𝒞  |𝑉 (𝐺 ) |   |𝑉 (𝐺 ′ ) |  and that |𝐶𝑖 | ⩾ 𝑑+1 ⩾ (and therefore 𝐺 ′ indeed has polynomial identifiers), we get 𝑑+1 by definition of weak uniformity that |A(𝐺 ′ ) ∩ 𝐶𝑖 | ⩽ 𝛼 · OPTΠ (𝐺 ′, 𝑁𝐺𝑘 ′ [𝐶𝑖 ]) = 𝛼 · OPTΠ (𝐺, 𝑁𝐺𝑘 [𝐶𝑖 ]) . Since 𝐺 [𝑁𝐺𝑟 [𝐶𝑖 ]] = 𝐺 ′ [𝑁𝐺𝑟 ′ [𝐶𝑖 ]], Algorithm A, which runs in 𝑟 rounds, returns the same vertex set in 𝐺 and 𝐺 ′ for vertices in 𝐶𝑖 . Therefore, |A(𝐺) ∩ 𝐶𝑖 | = |A(𝐺 ′ ) ∩ 𝐶𝑖 |. Combining with the previous inequality, we get |A(𝐺) ∩ 𝐶𝑖 | ⩽ 𝛼 · OPTΠ (𝐺, 𝑁𝐺𝑘 [𝐶𝑖 ]) ⩽ 𝛼 · OPTΠ (𝐺, 𝑉 (𝐺)) = 𝛼 · OPTΠ (𝐺) . Putting Eq. (4) in Eq. (3), we get that Algorithm A is an 𝛼 (𝑑 + 1)-approximation on 𝒟. C.12

(4) □

Meta-theorem for paddable problems with non-empty error set

Theorem C.13 (Meta-Theorem III). Let 𝑑, 𝑘 be integers 𝛼 > 0 a real, A be a 𝜀-weakly 34 𝑘-uniform 𝛼-approximation LOCAL algorithm for an additive 𝜌-local problem Π in a class of graphs 𝒞 with round complexity 𝑟 , where 𝒞 is hereditary, stable by disjoint union, and 𝑂 (1)-paddable for Π. Let 𝒟 be a graph class of asymptotic dimension 𝑑 with 𝑑-dimensional control function 𝑓 such that Π is dense in 𝒟, and such that 𝒟 is 𝑇 -locally 𝛿-nice w.r.t. 𝒞 and Π, where 𝑇 = 𝑓 (2𝑘 +2𝜌) +max {𝑘 + 𝜌, 𝑟 }. Then there exists a function 𝑔 such that for any 𝜂 > 0, there exists a max{𝑘, 𝜌 }-uniform (𝛼 (𝑑 +1) +1+𝜂)-approximation algorithm B on 𝒟 with round complexity max{𝑇 + 𝛿 + 2, 𝑔(𝜂)}. Proof. Let 𝐺 ∈ 𝒟 and 𝑋 be the set of 𝑇 -errors of 𝐺 with respect to 𝒞. As 𝒟 has 𝑑-dimensional control function 𝑓 , then 𝐺 2𝑘+2𝜌 admits a (𝑑 + 1)-coloring 𝑓 (2𝑘 + 2𝜌)-bounded in 𝐺. Fix such a coloring, and, for each 𝑖 ∈ {0, 1, . . . , 𝑑 }, let 𝐶𝑖 be the set of color-𝑖 vertices in 𝐺 2𝑘+2𝜌 (and also in 𝐺). We denote by ℭ𝑖 the set of (2𝑘 + 2𝜌)-components of 𝐶𝑖 (i.e. connected components of 𝐺 2𝑘+2𝜌 [𝐶𝑖 ]). So, by definition, all components of ℭ𝑖 have weak diameter in 𝐺 at most 𝑓 (2𝑘 +2𝜌), and are pairwise at distance at least 2𝑘 + 2𝜌 + 1 in 𝐺 (because distinct components of ℭ𝑖 cannot be adjacent in 𝐺 2𝑘+2𝜌 ). We describe the Algorithm B we want to use in Algorithm 4, which is very similar to Algorithm 2. We run Algorithm B on 𝐺. It is easy to check that B(𝐺) is a valid solution for 𝐺, because Π is additive. By definition, |B(𝐺)| ⩽ |𝑆 | + |𝑆 ′ |, where 𝑆 = A(𝐺) \ 𝑋 (Step 4) and 𝑆 ′ is a brute-forced set of minimum size satisfying the constraints of vertices of 𝐺 not satisfied (Step 5). Note that every vertex not in 𝑁 𝜌 [𝑋 ] is satisfied by 𝑆, so 𝑆 ′ ⊆ 𝑁 2𝜌 [𝑋 ]. Clearly, |𝑆 ′ | ⩽ OPTΠ (𝐺), and |𝑆 ′ | = 0 if there 34 Note that, for the proof, we could also prove as a preliminary that weakly uniform and paddable implies uniform. However,

for sake of brevity, we prove everything directly in the proof.

Meta-Theorems for Cuttable Distributed Problems

29

Algorithm 4 Generic algorithm B from Meta-Theorem III. Require: An 𝜀-weakly 𝑘-uniform 𝛼-approximate LOCAL algorithm A for Π in 𝒞 with round complexity 𝑟 , a graph classes 𝒞 and 𝒟 with properties of the statement of Meta-Theorem III, the 𝑑-dimensional control function 𝑓 of 𝒟 and 𝐺 ∈ 𝒟 with 𝑇 -errors 𝑋 where 𝑇 = 𝑓 (2𝑘 + 2𝜌) + max {𝑘 + 𝜌, 𝑟 }. Ensure: A solution 𝑆 for the graph 𝐺 to the problem Π with the guarantee that |𝑆 | ⩽ (𝛼 (𝑑 + 1) + 1) · OPTΠ (𝐺). 1: Let 𝐵 be such that any graph 𝐺 of 𝒟 with diam(𝐺) ⩾ 𝐵 has OPTΠ (𝐺) ⩾ 𝛼 (𝑑 + 1)𝜔/𝜂. If diam(𝐺) < 𝐵, brute-force an optimal solution. ⊲ 𝐵 exists as Π is dense in 𝒟. 2: 𝑆 ← ∅ 3: Each vertex 𝑢 computes 𝐺 [𝑁 𝑇 [𝑢]] and checks whether it belongs to 𝒞; as a consequence, it decides whether it belongs to 𝑋 . 4: Each vertex 𝑢 runs A for 𝑟 rounds, and gets added to 𝑆 only if 𝑢 ∈ A(𝐺) \ 𝑋 . 5: 𝑆 ← 𝑆 ∪𝑆 ′ , where 𝑆 ′ is a brute-forced minimum set of 𝐺 that satisfies the constraints of vertices that are non-satisfied. Í is no 𝑇 -errors (𝑋 = ∅). Moreover, by definition of the coloring, |A(𝐺) \ 𝑋 | = 𝑑𝑖=0 |(A(𝐺) ∩ 𝐶𝑖 ) \ 𝑋 |. In other words,  𝑑 ∑︁ 0 if 𝑋 = ∅ |B(𝐺)| ⩽ |(A(𝐺) ∩ 𝐶𝑖 ) \ 𝑋 | + (5) OPTΠ (𝐺) otherwise 𝑖=0

To upper bound the term |(A(𝐺) ∩ 𝐶𝑖 ) \ 𝑋 |, consider some color 𝑖 ∈ {0, 1, . . . , 𝑑 } and some component 𝐶 ∈ ℭ𝑖 such that 𝐶 ⊈ 𝑋 . Consider some 𝑣𝐶 ∈ 𝐶 \ 𝑋 , and denote 𝐺𝐶 = 𝐺 [𝑁 𝑇 [𝑣𝐶 ]]. Note that, by definition of 𝑋 and as 𝑣 ∉ 𝑋 , we have 𝐺𝐶 ∈ 𝒞. Moreover, let ℭ𝑖′ = {𝐶 ∈ ℭ𝑖 | 𝐶 ⊈ 𝑋 } and let Ð 𝐺 ′ = 𝐺 [ 𝐶 ∈ℭ𝑖′ 𝑁 𝑇 [𝑣𝐶 ]] be the union of the 𝐺𝐶 ’s for 𝐶 ∈ ℭ𝑖 such that 𝐶 ⊈ 𝑋 . Along the proof, we will use several times the following fact: Fact C.1. For any graph 𝐻 and 𝑊 ⊆ 𝑉 (𝐻 ), to satisfy the constraints of vertices of 𝑊 in 𝐻 , it is enough to select vertices taken from 𝑁 𝜌 [𝑊 ]. In the following, to differentiate the neighborhoods in 𝐺 and in 𝐺𝐶 or 𝐺 ′ , we write them using either 𝑁𝐺 , 𝑁𝐺𝐶 , or 𝑁𝐺 ′ notations. Notice that, for each non-negative integer 𝑡 ⩽ max {𝑘 + 𝜌, 𝑟 }, we have 𝐺 [𝑁𝐺𝑡 [𝐶]] ⊆ 𝐺𝐶 . This is because 𝐶 has weak diameter in 𝐺 at most 𝑓 (2𝑘 + 2𝜌) and thus 𝐺 [𝑁𝐺𝑡 [𝐶]] has weak diameter in 𝐺 at most 𝑓 (2𝑘 + 2𝜌) + 𝑡 ⩽ 𝑇 , by the choice of 𝑇 . Moreover, as 𝒞 is hereditary, we have that 𝐺 [𝑁𝐺𝑡 [𝐶]] ∈ 𝒞. As 𝐺 [𝑁𝐺𝑡 [𝐶]] ⊆ 𝐺𝐶 , vertices in 𝐶 have the same distance 𝑡-neighborhood in 𝐺 and 𝐺𝐶 . In particÐ Ð ular, 𝐺 [𝑁𝐺𝑡 [𝐶]] = 𝐺𝐶 [𝑁𝐺𝑡 𝐶 [𝐶]] and 𝐺 [𝑁𝐺𝑡 [ ℭ𝑖′ ]] = 𝐺 ′ [𝑁𝐺𝑡 ′ [ ℭ𝑖′ ]]. From Fact C.1, any minimum set of vertices of 𝐺 that satisfies the constraints of 𝑁𝐺𝑘 [𝐶] is contained in 𝐺 [𝑁𝐺 [𝐶]], and similarly if we replace 𝐺 by 𝐺𝐶 . It follows that OPTΠ (𝐺, 𝑁𝐺𝑘 [𝐶]) = OPTΠ (𝐺𝐶 , 𝑁𝐺𝑘 𝐶 [𝐶]). Recall that any two 𝑘+𝜌

connected components 𝐶, 𝐶 ′ ∈ ℭ𝑖 are at distance in 𝐺 at least 2𝑘 + 2𝜌 + 1. So 𝐺 [𝑁𝐺 [𝐶]] and 𝑘+𝜌 𝐺 [𝑁𝐺 [𝐶 ′ ]] are disjoint subgraphs, and, as to satisfy all constraints of vertices in 𝑉 (𝐺), one needs to satisfy constraints of vertices in 𝑁𝐺𝑘 [𝐶] and 𝑁𝐺𝑘 [𝐶 ′ ], by disjunction of these sets and by Fact C.1, we have by summing over all 𝐶 ∈ ℭ𝑖 that  hØ i   hØ i  OPTΠ 𝐺, 𝑁𝐺𝑘 ℭ𝑖′ = OPTΠ 𝐺 ′, 𝑁𝐺𝑘 ′ ℭ𝑖′ . 𝑘+𝜌

30

Marthe Bonamy, Avinandan Das, Cyril Gavoille, Timothé Picavet, Jukka Suomela, and Alexandra Wesolek

Moreover, because 𝒞 is stable by disjoint union and that 𝐺 [𝑁𝐺𝑡 [𝐶]] ∈ 𝒞 for every 𝐶 ∈ ℭ𝑖′ , we get Ð 𝐺 [𝑁𝐺𝑡 [ ℭ𝑖′ ]] ∈ 𝒞. b with size linear in |𝑉 (𝐺)| so that adding 𝐺 b to any In the following, we will choose a graph 𝐺 ′ b subgraph 𝐻 of 𝐺 will form a graph with size linear in |𝑉 (𝐺 ⊔𝐺)|. This serves two purposes: we are b ⊔𝐻 and we can attribute unique identifiers to 𝐺 b so that the now able to apply weak uniformity on 𝐺 b ⊔ 𝐻 are polynomial (we keep the same identifiers for 𝐻 ). Let 𝑁 := ⌈𝜀 |𝑉 (𝐺)|/(1 − 𝜀)⌉. identifiers of 𝐺 b ∈ 𝒞 on at least 𝑁 vertices such that OPTΠ (𝐺) b ⩽ 𝜔. Let 𝐼 be the By paddability, there exists a graph 𝐺 b largest identifier of 𝐺. We give identifiers to vertices of 𝐺 from the set {𝐼 + 1, 𝐼 + 2, . . . , 𝐼 + |𝑉 (𝐺 ′ )|}. b and let 𝑌 = Ð ℭ ′ ⊔ 𝑉 (𝐺). b The identifiers of vertices in 𝐺 ′′ Let 𝐺 ′′ be the disjoint union of 𝐺 ′ and 𝐺 𝑖 ′′ b has size at least linear in |𝑉 (𝐺)|. Our goal now is to are indeed polynomial in the size of 𝐺 , as 𝐺 Ð apply weak uniformity in 𝐺 ′′ to the set 𝑌 . Note that we only care about A(𝐺 ′ ) ∩ ℭ𝑖′ but need 𝑌 ′′ to apply weak uniformity. We first prove that |𝑌 | ⩾ 𝜀 |𝑉 (𝐺 )|. b ⩾ 𝜀 |𝑉 (𝐺)| b + (1 − 𝜀)|𝑉 (𝐺)| b |𝑌 | ⩾ |𝑉 (𝐺)| b + (1 − 𝜀)𝑁 ⩾ 𝜀 |𝑉 (𝐺)| b + 𝜀 |𝑉 (𝐺)| ⩾ 𝜀 |𝑉 (𝐺 ′′ )| . ⩾ 𝜀 |𝑉 (𝐺)| Therefore, by 𝜀-weak 𝑘-uniformity 𝛼-approximation of A on 𝒞, we get |A(𝐺 ′′ ) ∩ 𝑌 | ⩽ 𝛼 · OPTΠ (𝐺 ′′, 𝑁 𝑘 [𝑌 ]) . Ð ′ b and OPTΠ (𝐺 ′′, 𝑁 𝑘 ′′ [𝑌 ]) = OPTΠ (𝐺) b + We have |A(𝐺 ′′ ) ∩ 𝑌 | = |A(𝐺 ′ ) ∩ ℭ𝑖 | + |A(𝐺)| 𝐺 Ð ′ Ð ′ ′ ′ 𝑘 ′ 𝑘 b and 𝐺 are in disjoint components OPTΠ (𝐺 , 𝑁𝐺 ′ [ ℭ𝑖 ]) ⩽ 𝜔 + OPTΠ (𝐺 , 𝑁𝐺 ′ [ ℭ𝑖 ]) because 𝐺 ′′ b of 𝐺 . Forgetting about the term |A(𝐺)|, it follows that  hØ i  Ø A(𝐺 ′ ) ∩ ℭ𝑖′ ⩽ 𝛼 · 𝜔 + 𝛼 · OPTΠ 𝐺 ′, 𝑁𝐺𝑘 ′ ℭ𝑖′ . (6) Ð Ð Since 𝐺 [𝑁𝐺𝑟 [ ℭ𝑖′ ]] = 𝐺 ′ [𝑁𝐺𝑟 ′ [ ℭ𝑖′ ]], Algorithm A, which runs in 𝑟 rounds, returns the same Ð Ð Ð vertex set in 𝐺 and 𝐺 ′ for vertices in ℭ𝑖′ . Therefore, A(𝐺) ∩ ℭ𝑖′ = A(𝐺 ′ ) ∩ ℭ𝑖′ . Combining with the previous inequality, we get A(𝐺) ∩

Ø

 hØ i  ℭ𝑖′ ⩽ 𝛼 · 𝜔 + 𝛼 · OPTΠ 𝐺, 𝑁𝐺𝑘 ℭ𝑖′ ⩽ 𝛼 · 𝜔 + 𝛼 · OPTΠ (𝐺, 𝑉 (𝐺)) = 𝛼 · 𝜔 + 𝛼 · OPTΠ (𝐺) .

We remark that |(A(𝐺) ∩ 𝐶) \ 𝑋 | = 0 if 𝐶 ⊆ 𝑋 . Because all vertices in 𝐶𝑖 but not in 𝑋 are in some 𝐶 ∈ ℭ𝑖′ , we have |(A(𝐺) ∩ 𝐶𝑖 ) \ 𝑋 | ⩽ A(𝐺) ∩

Ø

ℭ𝑖′ ⩽ 𝛼 · 𝜔 + 𝛼 · OPTΠ (𝐺) .

(7)

Now, we can apply the same trick as in Proposition D.2. As Π is dense in 𝒟, there exists some 𝐵 such that any graph of 𝒟 of diameter at least 𝐵 has optimum value at least 𝛼 (𝑑 +1)𝜔/𝜂. Algorithm B checks (Step 1) whether the diameter 𝐷 of its component is less than 𝐵. This can be done by collecting the radius-𝐵 neighborhood of every vertex in 𝐵 rounds. If true, the vertex locally brute-forces an optimal solution for its component, which it already knows about. If false, the vertex continues the algorithm with Step 2. If 𝐷 < 𝐵, then the algorithm is obviously a good approximation (with approximation ratio 1). Otherwise, 𝐷 ⩾ 𝐵 and it follows that OPTΠ (𝐺) ⩾ 𝛼 (𝑑 + 1)𝜔/𝜂. Putting in Eq. (7) in Eq. (5), we get that Algorithm B is an (𝛼 (𝑑 + 1) + 1 + 𝜂)-approximation, and even an (𝛼 (𝑑 + 1) + 𝜂)-approximation if 𝑋 = ∅.

Meta-Theorems for Cuttable Distributed Problems

31

To see that B is also a 𝑘-uniform approximation, it is sufficient to see that, for any 𝑊 ⊆ 𝑉 (𝐺), the bound obtained is |B(𝐺) ∩ 𝑊 | ⩽ 𝛼 (𝑑 +1)𝜔 +𝛼 (𝑑 +1) ·OPTΠ (𝐺, 𝑁𝐺𝑘 [𝑊 ]) +OPTΠ (𝐺, 𝑁𝐺 [𝑊 ]) where the first two terms are due to running A and the last term is due to running the brute-force. Indeed, 𝜌 if the brute-force computed a set whose intersection with 𝑊 was smaller than OPTΠ (𝐺, 𝑁𝐺 [𝑊 ]), 𝜌 we could replace it by the minimum size set satisfying the constraints of the vertices in 𝑁𝐺 [𝑊 ] and obtain a smaller set, a contradiction. This proves that B is max{𝑘, 𝜌 }-uniform with approximate ratio 𝛼 (𝑑 + 1) + 1 (or 𝛼 (𝑑 + 1) if 𝑋 = ∅, as the brute-force is not required in that case). Now, let us prove that Algorithm B has the desired round complexity. • Step 1 takes 𝐵 = 𝑔(𝜂) rounds for computing if the diameter is small, and no additional round for the brute-force. • Computing 𝑋 in Step 3 takes 𝑇 + 1 rounds. • Running A in Step 4 takes 𝑟 rounds. • For Step 5, consider the set 𝑆 computed by B at Step 4, before the brute-force. Observe that 𝜌 the vertices in the set 𝑊 = 𝑉 (𝐺) \ 𝑁𝐺 [𝑋 ] are satisfied by 𝑆. This is because vertices of 𝑊 𝜌 are at distance at least 𝜌 + 1 from 𝑋 and thus vertices of 𝑁𝐺 [𝑊 ] cannot be in 𝑋 . Thus, A 𝜌 applies to all vertices of 𝑁𝐺 [𝑊 ], and so 𝑊 is indeed satisfied by 𝑆 (Fact C.1). Therefore, 𝜌 2𝜌 to satisfy 𝑁𝐺 [𝑋 ] it is enough to select a set 𝑆 ′ from 𝑁𝐺 [𝑋 ] (Fact C.1) as done in Step 5. 2𝜌 By assumption, the connected components of 𝑁𝐺 [𝑋 ] have weak diameter in 𝐺 at most 𝛿 (obviously, if 𝑋 = ∅ then 𝛿 = 0). Therefore, the brute-force (Step 5) will take at most 𝛿 + 1 rounds. Naively, Steps 3 and 4 together take (𝑇 + 1) + 𝑟 rounds. As Algorithm A is not guaranteed to work when executed on vertices of 𝑋 , Step 4 must be run only after Step 3. However, both steps can be run in parallel as follows. We run A for 𝑟 rounds exactly and stop it just after (since its running time on a vertex of 𝑋 could result into more than 𝑟 rounds). Then, the decision to add 𝑢 in 𝑆 (if selected by A) is delayed for the next 𝑇 + 1 − 𝑟 rounds (this is non-negative from the choice of 𝑇 ). In parallel, 𝐺 [𝑁 𝑇 [𝑢]] is computed and is checked to be in 𝒞 or not after 𝑇 + 1 rounds. So, after max {𝑟,𝑇 + 1} = 𝑇 + 1 rounds, set 𝑆 in Step 4 has been completed. The same trick can be applied for Step 1. Step 5 takes 𝛿 + 1 steps, so that the total round complexity of B is max{𝑇 + 𝛿 + 2, 𝑔(𝜂)}, completing the proof. □ D

Miscellaneous propositions

Proposition D.1. Every graph class 𝒞 including trees has no 0-uniform 𝛼-approximations for Minimum Dominating Set, for every ratio 𝛼 ⩾ 1. Proof. Consider a depth-2 tree 𝑇𝛼 , with 𝛼 + 1 vertices at depth-1, each having 𝛼 2 + 1 neighbors at depth-2. See Fig. 6 for an example. Clearly, MDS(𝑇𝛼 ) = 𝛼 + 1. Moreover, any 𝛼-approximation algorithm A in 𝑇𝛼 has to select all depth-1 vertices. If not, each of the 𝑡 non-selected vertex at depth 1 would force the selection of 𝛼 2 + 1 extra vertices at depth 2, creating by this way a solution with at least (𝛼 +1−𝑡)+𝑡 · (𝛼 2 +1) = 𝛼 · (𝑡𝛼 +1)+1 vertices. For 𝑡 ⩾ 1, this is at least 𝛼 · (𝛼 +1)+1 > 𝛼 ·MDS(𝑇𝛼 ). However, for a subset 𝑆 composed of all depth-1 vertices of 𝑇𝛼 (so with |𝑆 | = 𝛼 + 1), we have on one side |A(𝑇𝛼 ) ∩ 𝑆 | = |𝑆 | = 𝛼 + 1, whereas MDS(𝑇𝛼 , 𝑁 0 [𝑆]) = MDS(𝑇𝛼 , 𝑆) = 1 (considering the root). So |A(𝑇𝛼 ) ∩ 𝑆 | ̸⩽ 𝛼 · MDS(𝑇𝛼 , 𝑁 0 [𝑆]). Therefore, A cannot be 0-uniform in 𝑇𝛼 . □

32

Marthe Bonamy, Avinandan Das, Cyril Gavoille, Timothé Picavet, Jukka Suomela, and Alexandra Wesolek

𝑆

Fig. 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 converted into an (𝛼 + 𝜀)-approximation LOCAL algorithm with round complexity 𝑟 + 𝑂 (𝛽/𝜀). Proof. Observe that the diameter of each connected component of the graph is at most 3 · MDS(𝐺). So, each vertex can check whether the diameter 𝐷 of its component is less than 𝐵, for 𝐵 = 3𝛽/𝜀. This can be done by collecting its radius-𝐵 neighborhood in 𝐵 = 𝑂 (𝛽/𝜀) rounds. If true, the vertex locally brute forces an optimal solution for its component that, which it already knows about. If false, the vertex applies the approximate algorithm. In that case, 𝐵 ⩽ 𝐷 and 𝐷 ⩽ 3 MDS(𝐺), which together imply 𝛽 ⩽ 𝜀 · MDS(𝐺). Thus, the returned set has size at most 𝛼 · MDS(𝐺) + 𝛽 ⩽ (𝛼 + 𝜀) · MDS(𝐺). □ √︁ Proposition D.3. Every 𝑛-vertex graph 𝐺 of Euler genus 𝑔 satisfies ∇1 (𝐺) < 3𝑔/2 + 3. This bound is best possible up to an additive constant, for each 𝑔 ⩾ 0. Proof. By definition, we have ∇1 (𝐺) = max𝐻 {|𝐸 (𝐻 )| /|𝑉 (𝐻 )|}, where 𝐻 is a depth-1 minor. ) |
For every 𝐻 , we have |𝐸 (𝐻 )| /|𝑉 (𝐻 )| < 3𝑔/|𝑉 (𝐻 )| + 3 from Euler’s formula. As |𝐸 (𝐻 )| ⩽ |𝑉 (𝐻 , 2 √︁ ∇1 (𝐺) ⩽ max𝑚∈ [1,𝑛] min {(𝑚 − 1)/2, 3𝑔/𝑚 + 3} < 3𝑔/2 + 3. √︁ The latter inequality holds, because either 3𝑔/𝑚 + 3 < 3𝑔/2 + 3, and we are done, or 3𝑔/𝑚 + 3 ⩾ √︁ √︁ √ √ 3𝑔/2 + 3, which implies 𝑚 ⩽ 6𝑔. In that case (𝑚 − 1)/2 ⩽ ( 6𝑔 )/2 − 1/2 < 3𝑔/2 + 3 as wanted. Consider a graph 𝐺 composed of a clique 𝐾𝑚 with 𝑚 ⩾ 4 and 𝑚 ≠ 7 where each edge is replaced by a path of length three. The graph 𝐺 has same Euler genus as 𝐾𝑚 , which is 𝑔 = ⌈(𝑚 − 3) (𝑚 − 4)/6⌉ (cf. [MT01, Theorem 4.4.5]). Moreover, it has 𝐾𝑚 as depth-1 minor. Thus, ∇1 (𝐺) ⩾ |𝐸 (𝐾𝑚 )| /𝑚 = √︁ (𝑚 − 1)/2 ⩾ 3𝑔/2 + 3/4. The latter inequality holds because, one can check that (𝑚 − 1) 2 ⩾ (𝑚 − 3) (𝑚 − 4) + 9 for all 𝑚 ⩾ 4. 2 Since (𝑚 − 3) (𝑚 − 4) + √︁9 ⩾ 6 ⌈(𝑚 − 3) (𝑚 − 4)/6⌉ + 3 = 6𝑔 + 3, we have (𝑚 − 1) /4 ⩾ (6𝑔 + 3)/4, and thus (𝑚 − 1)/2 ⩾ 3𝑔/2 + 3/4 as claimed. □