arXiv CSopen access

Near-Optimal Distributed 2-Ruling Sets on Graphs with Low Arboricity

Near-Optimal Distributed 2-Ruling Sets on Graphs with Low Arboricity

arXiv:2606.11974v1 [cs.DS] 10 Jun 2026

Malte Baumecker1 , TU Graz – [email protected] Rustam Latypov2 , Aalto University – [email protected] Yannic Maus1 , TU Graz – [email protected] Jara Uitto, Aalto University – [email protected]

Abstract Given a graph G = (V, E), a β-ruling set is a subset of nodes S ⊆ V that is independent, and each node in V is at distance at most β from some node in S. In this paper, we present almost optimal distributed algorithms for finding 2-ruling sets in the classical LOCAL model. Our main contribution is a randomized algorithm that w.h.p. computes a 2-ruling set on any n-node graph with bounded arboricity in O(log log n) rounds. In fact, the algorithm works up to arboricity O(log log n), improves exponentially over the prior state of the art that can be achieved by combining [Barenboim, Elkin, Pettie, Schneider; JACM’16], [Ghaffari; SODA’16], and [Bisht, Kothapalli and Pemmaraju; PODC’14], and nearly matches the lower bound of Ω(log log n/ log log log n) [Balliu, Brandt, Kuhn, Olivetti; FOCS’20]. The domination parameter β = 2 is optimal for algorithms with run√ time logo(1) n: on graphs with arboricity 2, there is a lower bound of Ω( log n) rounds for MIS (i.e., β = 1) [Khoury, Schild; FOCS’25]. Additionally, we obtain improved algorithms for larger arboricity. For general graphs with arboricity α, we present a randomized algorithm that computes a 2-ruling set in 5/8 e O(log α + log5/3 log n) rounds. This improves exponentially over the state of the art for a large range of non-constant arboricity. Our techniques extend beyond distributed computing. We present an O(log log log n)round algorithm in the low-space Massively Parallel Computation (MPC) model that w.h.p. computes a 2-ruling set on any graph with arboricity up to 2poly(log log n) , improving exponentially over the state of the art from [Kothapalli, Pai, Pemmaraju; FSTTCS’20] combined with [Fischer, Giliberti, Grunau; SPAA’23].

1 2

Supported by the Austrian Science Fund (FWF) https://doi.org/10.55776/I6915. Supported by the Research Council of Finland, Grant 334238.

Contents 1 Introduction 1.1 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Technical Overview and Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 2 4 6

2 Preliminaries & Notation

9

3 Randomized 2-Ruling Set for Low Arboricity Graphs 10 3.1 Stage I: Degree Drop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 Many Low-Degree Neighbors . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.1.2 Many High-Degree Neighbors . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Stage II: Shattering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3 Stage III: Deterministic 2-Ruling Set for Small Components . . . . . . . . . . . . . . 16 4 Randomized 2-Ruling Set for Graphs of General Arboricity

18

5 Massively Parallel 2-Ruling Set

20

A Extended Related Work

28

B Example: Successful Nodes are Correlated

30

C Deferred Proofs

31

D Probabilistic Theorems

32

2

1

Introduction

In this paper, we study the problem of finding a β-ruling set in the standard LOCAL and CONGEST models of distributed message-passing. Given a graph G = (V, E), a β-ruling set S ⊆ V is a set of non-adjacent nodes such that every node in G is within at most β hops from S. This is a natural generalization of the extremely well-studied MIS problem, which corresponds to a 1-ruling set. Ruling sets are often faster to compute than MIS and have various applications as subroutines for coloring problems [37], network decomposition [3, 34], and MIS itself [32]. Beyond the applications for other problems, finding ruling sets is a central and well-studied symmetry breaking problem of independent interest [2, 6, 12, 17, 31, 34, 40, 48, 59, 63, 65]. In general graphs, the classic algorithms developed independently by Luby [54] and Alon, Babai, and Itai [1] can be used to find an MIS in O(log n) rounds, where n is the number of nodes. Despite decades p of effort, these algorithms remain the state of the art. For MIS, there is a√classic lower bound of Ω( log n/ log log n) rounds [8, 49], which was very recently improved to Ω( log n) rounds √ [46]. By relaxing the domination to β = 2, sublogarithmic algorithms are known that run in O( log n) rounds when expressed as a function of n only [15, 32, 48]. On the lower bound side, one cannot do better than Ω(log log n/(β log log log n)) [6], leaving an exponential gap between lower and upper bounds, e.g., for β = 2 on general graphs. In this paper, we close this gap on sparse graphs up to triple-logarithmic factors, giving exponentially faster 2-ruling-set algorithms for graphs of low arboricity. Arboricity is a standard measure of sparsity: it corresponds to the number of forests that are needed to partition the edge set. Symmetry-breaking in graphs with bounded arboricity is frequently studied in LOCAL, CONGEST, dynamic models, and various other models of computation [11, 16, 19, 20, 24, 25, 26, 28, 33, 48, 52, 57, 58]. At a high level, our main technical contribution is a fast degree drop procedure. Given a graph of maximum degree ∆, the goal of our procedure is to compute an independent set S so that, after removing all nodes covered by S, the remaining graph has maximum degree significantly smaller than ∆. Given that we require independence of S and the coverage of all high-degree nodes, the probability of including a node u to S necessarily depends on its local graph topology. Hence, short cycles create dependencies on the events that nearby nodes are selected and standard tools such as Chernoff bounds cannot be used to obtain concentration. We control these dependencies using read-k concentration inequalities, building on techniques originally introduced by Pemmaraju and Riaz for faster MIS algorithms on bounded-arboricity graphs [61]. We discuss our approach and its relation to their techniques in Section 1.3. An advantage of our degree drop is that it extends naturally to the memory-restricted low-space Massively Parallel Computation (MPC) model, where ruling sets have also been extensively studied [22, 29, 36, 38, 39, 43, 47]. There, we design an O(log log log n)-round algorithm that is simple, yet improves exponentially on the state of the art. Previously p Known Faster Algorithms in Sparse Graphs via Degree Drop. The lower bounds of Ω( log n/ log log n) for MIS and Ω(log log n/(β log log log n)) for β-ruling sets already hold on trees [6, 8]. Nevertheless, sparse graphs often admit faster algorithms than general graphs. A central reason is that sparsity can be exploited to reduce the maximum degree quickly. A seminal example is the degree-reduction framework for MIS of Barenboim, Elkin, Pettie, and Schneider [12]. For √ √ graphs of arboricity at most α, their tool reduces the maximum degree to α · 2O( log n) in O( log n) rounds. The analysis relies on reasoning about nodes that are mutually 1

at distance at least 3; this separation ensures the needed independence between selected nodes, but it also limits the rate at which the degree can drop. More √ recently, Khoury and Schild improved this type of degree reduction on trees, obtaining an o( log n)-round MIS algorithm and thereby separating trees from general graphs for MIS (in fact they already separate trees from graphs with arboricity two) [45]. Their algorithm is based on a two-stage competition process in which each node survives with subconstant probability. These degree-reduction tools, however, are designed for MIS, and their runtime remains constrained by MIS-type lower bounds. Indeed, even combining the degree reduction of [12] with the ruling-set subsampling of Bisht, Kothapalli, and Pemmaraju [15] and Ghaffari’s efficient algorithm for low-degree graphs [32] yields only a logΩ(1) n-round algorithm for 2-ruling sets on boundedarboricity graphs; see Appendix A for more details. To obtain double-logarithmic runtimes for 2-ruling sets, one needs a faster degree drop.√ On trees, this is possible [13]: roughly speaking, the maximum degree can be reduced from ∆ to ∆ in O(1) rounds, yielding an exponential separation between MIS and 2-ruling sets. The difficulty is that this separation currently relies on the input graph being locally tree-like. The same issue appears in the fast MIS degree-reduction tools above, which rely on the absence of short cycles, or at least on enough local independence induced by distance-3 separation in the analysis. This is an obstacle for bounded-arboricity graphs: although they are globally sparse, they may contain many short cycles. Consequently, existing techniques do not seem to provide the constant-round polynomial degree drop needed to close the exponential gap between upper and lower bounds for 2-ruling sets. Avoiding Dependencies with β ≥ 3. One way to bypass the dependencies created by short cycles is to increase the domination radius. Kothapalli and Pemmaraju [48] show how to sample low-degree subgraphs so that every high-degree node in the original graph is within distance 2 of a sampled node. Computing MIS in these sampled graphs then yields an O(log3 log n)-round algorithm for 3-ruling sets. This approach, however, does not seem to extend to 2-ruling sets. For 2-ruling sets, the sampled nodes would need to cover the immediate neighborhood of every high-degree node, rather than only its distance-2 neighborhood. Sampling sufficient low-degree subgraphs with this stronger coverage property appears difficult. Thus, avoiding dependencies by increasing the domination radius does not resolve the case where β = 2.

1.1

Our Contributions

We consider the setting where a communication network is modeled as a graph G = (V, E), where |V | = n nodes with unbounded computational power communicate over the edges in synchronous message-passing rounds. In the distributed LOCAL model, introduced by Linial [53], message sizes are unbounded, whereas in the CONGEST [60] model messages are bounded by O(log n) bits. In the beginning, each node only knows its neighbors, and upon termination, each node v should know its own output, for example, whether it is part of the ruling set or not. The runtime is measured in the number of rounds. We consider graphs of low arboricity, where the arboricity1 of a graph G is defined as the minimum number of forests into which the edges of G can be partitioned. First, we present a fast algorithm for ruling sets with the best possible domination distance β = 2 for subpolylogarithmic runtime on graphs with low arboricity.

1

Formally, the arboricity of G is defined as α(G) := maxG′ ⊆G,|V (G′ )|≥2

2

 |E(G′ )|  |V (G′ )|−1

.

Figure 1: Distributed algorithms for ruling sets: upper bounds are shown as dots (fill pattern indicates graph class) and lower bounds as grey regions. The horizontal axis represents the domination distance (1-ruling set (MIS), 2-ruling set, and 3-ruling set), and the vertical axis represents the round complexity as a function of n (with ∆ expressed as a polynomial in n). Blue arrows indicate improvements over the prior state of the art: our algorithm is exponentially faster for 2-ruling sets, and polynomially faster for 3-ruling sets while simultaneously achieving the optimal domination distance for subpolylogarithmic runtimes. Our runtime is optimal up to a triple-logarithmic factor. Prior to this work, only trees (arboricity 1) admitted an O(log log n)-round algorithm [13]. Theorem 1. There is an O(log log n)-round CONGEST algorithm that w.h.p. computes a 2-ruling set in graphs with arboricity up to O(log log n). Our algorithm is optimal up to a triple-logarithmic factor and improves exponentially compared to the fastest known 2-ruling set algorithm that can be deduced from published algorithms and runs in O(log1/4 ∆ + poly log log n) rounds [12, 15, 32], see Corollary 28 for details. Prior to our work, the only double-logarithmic–time ruling set algorithm for graphs with arboricity α > 1 achieved an O(log3 log n) runtime and computed a 3-ruling set for graphs of arboricity O(1) [48], see Figure 1. This exponential gap between 3-ruling sets and 2-ruling sets highlights a qualitative increase in difficulty: even modest improvements in the ruling parameter have required substantially higher runtimes. In contrast, compared to the existing 3-ruling set algorithm, our result achieves a polynomially faster runtime while solving the much harder 2-ruling set problem on a broader graph class. Our algorithm runs in the CONGEST model and thus Theorem 1 improves upon the best known CONGEST algorithm for 2-ruling sets that runs in O(log ∆ · (log n)1/2+ϵ + logloglogn n ) rounds [58]. Second, we present an algorithm whose runtime remains sublogarithmic for graphs with any arboricity. 3

5/8 e Theorem 2. There is an O(log α + log5/3 log n)-round LOCAL algorithm to compute a 2-ruling set in graphs with arboricity α w.h.p.

To the best of our knowledge, the best 2-ruling set algorithm for graphs with larger arboricity follows by combining prior work [12, 15, 32] and runs in O(log1/4 ∆ + log α + poly log log n) rounds; see Theorem 27 for details. Finally, we observe that Theorem 2 runs in poly log log n rounds for graphs with arboricity up 8/3 to 2(log log n) . 5/3 e Corollary 3. There is an O(log log n)-round LOCAL algorithm to compute a 2-ruling set in 8/3 (log log n) graphs with arboricity α ≤ 2 w.h.p.

Corollary 3 improves upon the state of the art beyond the log log n arboricity barrier of Theorem 1. In fact, Theorem 2 still improves polynomially on the state of the art 2-ruling set algorithm 4/5 up to arboricity 2(log n) . Massively Parallel Computation. The Massively Parallel Computation (MPC) model [14, 44] is one of the leading theoretical frameworks for large-scale computation, striking a balance between mathematical abstraction and practical relevance. It faithfully captures the behavior of widely deployed data processing frameworks such as Hadoop [66], Spark [67], MapReduce [23], and Dryad [42]. In the low-space variant of the MPC model there are M machines, each with local space S, sublinear in the input size. For graphs, the edges of the input graph G = (V, E) are arbitrarily and equally distributed among the machines, each with local space S = O(nε ) such that ε ∈ (0, 1). Within a round, machines perform all-to-all synchronous communication, and then perform some unbounded computation on local data. The system is fault-free, meaning that nodes never crash and messages never get corrupted. The total space refers to the maximum amount of memory used by the collection of M machines at any point during the algorithm. Ruling sets have been extensively studied in the low-space MPC model in recent years [22, 29, 36, 38, 39, 43, 47]. To the best of our knowledge, for the broad class of graphs with arboricity α ≤ 2poly(log log n) , the current state-of-the-art runtime for 2-ruling set is poly(log log n). While not published, this result follows by combining the algorithm of [47] with the degree reduction by [29]. We improve upon this exponentially with a sharp triple-logarithmic 2-ruling set algorithm, using the same amount of total space. Theorem 4. There is an O(log log log n)-round low-space MPC algorithm that w.h.p. computes a 2-ruling set in graphs with arboricity α ≤ 2poly(log log n) , using O(m + n1+ε ) total space.

1.2

Related Work

We have already covered parts of the related work while presenting our results, but we want to present a more thorough overview. To complement the LOCAL overview given here, we refer to Table 1 for the randomized regime and Table 2 for the deterministic regime in Appendix A. Randomized LOCAL. Ghaffari’s seminal MIS algorithm is still the state of the art for MIS on general graphs and runs in O(log ∆ + poly log log n) rounds [32], which improves on Luby’s O(log n) [1, 54] algorithm for ∆ = no(1) . His algorithm can also be combined with prior work on ruling sets [15] to compute β-ruling sets in O(β log1/β ∆ + poly log log √ n) rounds. Recently, there was progress for MIS and the conjecture of a Θ( log n) complexity for MIS on trees was refuted by Khoury and Schild, as they showed that an MIS can be computed in 4

p ∆ O( log n/ log log∗ n) rounds on trees, and in O( loglog log∗ ∆ + poly(log log n)) rounds on graphs of girth at least 7 [45]. √ Additionally, they gave an Ω(min{log ∆, log n}) lower bound for Maximal Matching, and thus for MIS on line graphs, improving on the previous known lower bounds and showing that MIS on general graphs is strictly p harder than on trees. For general graphs, there has been a series of works started by an Ω(min{ log n/ log log n, log ∆/ log log ∆}) lower bound on line graphs by Kuhn, Moscibroda, and Wattenhofer [49], for which Coupette and Lenzen presented a simple proof [21]. This was followed by multiple works of Balliu, Ghaffari, Kuhn, and Olivetti, with the latest paper extending the lower bound to trees [5, 7, 8]. For graphs of arboricity α, Barenboim, Elkin, Pettie √ and Schneider showed √ that it is possible to compute an MIS in O(log α + log n) rounds [12, 32], √ which results in an O( log n)-round algorithm for graphs with arboricity up to 2O( log n) . For ruling sets, Kothapalli and Pemmaraju showed that one can compute a 2-ruling set in O(log3/4 n) [48] rounds on general graphs. Techniques from that paper, together with [12, 32], yield the current state of the art of O(log1/4 ∆ + O(poly log log n), see Theorem 27 for details on how to combine these works to obtain the claimed runtime. On trees it is possible to compute 2-ruling sets 5/3 e in O(log log n) rounds, and on graphs of girth at least 7 in O(log log n) rounds [13]. For non-constant domination β, Gfeller and Vicari, combined with [12], obtain an O(log log n)ruling set algorithm in O(log log n) rounds plus runtime of MIS on graphs with polylogarithmic degrees [31]. On graphs of girth at least 7, it is possible to compute an O(log log log n)-ruling set in e O(log log n) rounds [13]. The best known lower bound for randomized algorithms for general graphs is Ω(min{β · ∆1/β , log∆ log n}) [5]. 5/3 e Deterministic LOCAL. The state of the art for MIS is the O(log n) algorithm of Ghaffari e and Grunau [34]. In the same paper, they also present a O(log n) round algorithm for O(log log n)ruling sets. √ For graphs of arboricity α Barenboim and Elkin show that an MIS can be computed in O(α · log n + α · log α) [9]. Additionally, for graphs up to arboricity O(log1/2−δ n), δ > 0, they provide a sub-logarithmic algorithm to compute an MIS in O(log / log log n) rounds. For trees, their algorithm is tight due to a lower bound for MIS of Ω( logloglogn n ) by [5]. For β-ruling sets, a series of papers resulted in a lower bound of Ω(min{β∆1/β , log∆ n}) which holds for general graphs [4, 5, 7]. One of the earliest works on ruling sets presented an O(log n)-round algorithm for O(log n)-ruling sets [3]. For constant β the current state of the art algorithm runs in O(∆2/(β+2) + log∗ n) [55].

For ruling set algorithms in the CONGEST model, we refer to [56], and for the congested clique to [18]. Next, we give an overview on prior ruling set algorithms in the context of low-space MPC. For information related to linear-space MPC, refer to [43]. Randomized low-space MPC. For general graphs, the the art for MIS (1√ current state of √ ruling set) is by Ghaffari and Uitto [38], with a runtime of O( log ∆·log log ∆+ log log n). For low arboricity √ graphs, the state of the art for MIS is by Ghaffari, Grunau, and Jin [36], with a runtime of O( log α · log log α + log log n). For 2-ruling set, Kothapalli, Pai, and Pemmaraju [47] developed a O(log1/6 ∆ · log log n)-round algorithm using a technique that they call Sample-and-Gather. They β+1 also extend their result to β-ruling set with a runtime of O(β · log1/(2 −2) ∆ · log log n). Deterministic low-space MPC. Most if not all deterministic algorithms are obtained by derandomizing prior randomized algorithms. Czumaj, Davies, and Parter [22] provided an MIS algorithm with runtime O(log ∆ + log log n) via a graph sparsification technique that derandomizes Luby’s algorithm. Fischer, Giliberti, and Grunau [29] improved upon this for sparse graphs, giving a deterministic O(log α + log log n)-round algorithm for MIS and maximal matching for graphs with 5

arboricity α. Their key technique is a procedure that reduces the maximum degree to poly(α) in O(log log n) rounds. Turning to ruling sets, Giliberti and Parsaeian [39] gave the first deterministic √ ruling set algorithm with sublogarithmic round complexity, computing a 2-ruling set in O( log ∆ · log log ∆ + log log∗ n) rounds. This was later improved, for a certain range of ∆, to O(log1/3 ∆ · log log ∆ + log log n) rounds by Ji, Kothapalli, Pemmaraju, and Singh [43], who also extend their results to β β-ruling set, with a runtime of O(log1/(2 −1) ∆ · log log ∆ + log log n). By incorporating the degree drop technique by [29], they also formulate their result in terms of arboricity α, resulting in a β O(log1/(2 −1) α · log log α + log log n) runtime.

1.3

Technical Overview and Challenges

The basic building block of our results is a variant of the classical MIS algorithm designed by Luby [54] and independently by Alon, Babai, and Itai [1]. In each iteration, each (active) node v draws a value rv ∈ (0, 1) uniformly and independently at random and joins the independent set if and only if v is a local minimum, i.e., rv < minu∈N (v) ru . Then, each node in the 2-hop neighborhood is removed from the graph and considered as covered. In the classical version for MIS, only nodes that are adjacent to the independent set nodes are removed from the graph, and it is shown that in each round, a constant fraction of edges is removed from the graph. We will call one such phase, of first drawing a random number, then letting local minima join, and finally removing the 2-hop neighborhood, a Luby Phase. Overall, this leads to an O(log n)-round algorithm for the MIS, which is still the best known running time for general graphs to this day, for ∆ = nO(1) . In his seminal work [32], Ghaffari presented a more involved algorithm that computes an MIS in O(log ∆ + poly log log n) rounds, improving the state of the art for low degree graphs. Combined with the √ sampling techniques presented in [15], this algorithm carries over to 2-ruling sets and yields an O( log ∆ + poly log log n) algorithm (for general graphs). These results indicate that the main challenge in designing efficient algorithms arises primarily in the high-degree regime. Our main contribution is showing that, on low arboricity graphs, running repeated Luby Phases for 2-ruling set yields a fast degree drop in the unsolved parts of the graph. Lemma 5 (Degree Drop). There is an O(log log ∆)-round algorithm that computes an independent set S, such that G \ (S ∪ N2 (S)) has maximum degree ∆′ ≤ max{(66)8 , log8 n} w.h.p.2 In fact, we show that after O(1) slightly modified Luby Phases, the remaining graph has a maximum degree of ∆3/4 w.h.p. Iterating this procedure yields the lemma above. Our procedure for the fast degree drop is not exactly √ the classical algorithm designed by Luby, but we adapt it by first letting only nodes of degree at ∆ participate in a Luby Phase and then letting all nodes participate in another Luby Phase. This process is then repeated for O(1) rounds to guarantee a w.h.p. coverage of all high degree nodes. Although this two-phase style is not a major change to Luby’s algorithm, it leads to an exponentially better algorithm for the well-studied 2-ruling set 2

For better readability, we did not optimize constants. By repeatedly running our degree drop for more (but still constant) rounds, one can reduce the constants here.

6

problem. This highlights that there is no need for new, complex algorithms when classical ones are yet to be analyzed to their full potential. As mentioned before, the main challenge is to deal with dependencies due to the existence of short cycles. If we were to ignore these dependencies, we see that we could achieve the desired fast degree drop by a straightforward analysis. Analysis Baseline. We consider one Luby Phase, and our goal is to obtain a polynomial degree drop in each iteration. Fix a node v with degree larger than ∆3/4 . For simplicity of this overview, we also assume that the arboricity is constant. First, consider the case where v has√few high-degree neighbors. In particular, v has at least ∆3/4 /2 neighbors with degree √ at most ∆. Any low-degree neighbor becomes a local minimum with probability roughly 1/ ∆. If the events of becoming local minima were independent, at least one of the ∆3/4 /2 low-degree neighbors would be a local minimum with high probability √ 3/4 1 − (1 − 1/ ∆)∆ /2 = 1 − 1/nc , using the assumption ∆ ≥ poly log n. In the second case, v has √ many high-degree neighbors. Suppose that at least half of the neighbors have a degree of at least ∆. We show that in this case, due to small arboricity, node v must have (roughly) ∆1.25 nodes in its 2-hop neighborhood. If the events of becoming local minima were independent, each one of those nodes would be a local minimum with probability roughly 1/∆. Hence, again, at least one of those nodes would become a local minimum with high probability 1.25 1 − (1 − 1/∆)∆ = 1 − 1/nc , and in both cases, node v would be removed from the graph. This simplified view shows that the aforementioned two-phase Luby style would not be required if the events were independent, but we will see that it is necessary for our analysis when the dependencies are present. Dealing with Dependencies via Concentration Inequalities. Unfortunately, in both cases, the events of becoming local minima are anything but independent. In our approach, we deal with the dependencies created by short cycles directly. Pemmaraju and Riaz [61] were the first to use read-k concentration inequalities to analyze the progress of Luby’s algorithm on bounded-arboricity graphs.3 √ Their algorithm computes an MIS in O(poly(α) · log n log log n) rounds. While this is much faster than the classical O(log n) bound in sparse graphs, it is still far from the double-logarithmic runtimes suggested by ruling-set lower bounds. Moreover, the polynomial dependence on α makes the result unsuitable for obtaining a flat O(log log n) runtime even for mildly growing arboricity. Building on the read-k concentration framework introduced by Pemmaraju and Riaz for analyzing Luby-style progress on bounded-arboricity graphs [61], we develop a degree drop analysis tailored to 2-ruling sets. To illustrate the structure of our argument, we first consider the simpler case in which a high-degree node has many low-degree neighbors. For the purpose of √ this overview, assume that the arboricity α is constant and recall that only nodes of degree at most ∆ are active in the Luby phase. Our analysis. Since the graph has arboricity α, it admits an orientation in which every node has at most α outgoing edges. We fix such an orientation purely for the analysis. For every node 3

We thank an anonymous reviewer for pointing us to the work of Pemmaraju and Riaz [61]. An earlier version of this manuscript handled the dependencies in the degree drop analysis by a substantially more involved direct argument. The read-k tool allows us to present the algorithm and its analysis in a much cleaner form, while still obtaining near-optimal bounds for 2-ruling sets on low arboricity graphs. Unfortunately, the framework presented in [61] is missing reasoning in the proof of Theorem 5 why the underlying ranks stay independent after conditioning on nodes’ ranks beating their out-neighbors’ ranks. In particular, ranks can be correlated after this conditioning, see Section B. We show how to resolve this issue in the proof of Lemma 16.

7

<latexit sha1_base64="0mu6Ey0EDNctosPxaMRIyH4JIPo=">AAAC3XicbVHBbtNAEF27FIqBNoUjlxWhUrkEu01DjkXNoYciikjSSraJ1ptxs3S9dnfXJZHlIzfElW/jxK+wdoJUN4y00tObN7NvZqKMM6Vd97dlbzzYfPho67Hz5Omz7Z3W7vOxSnNJYURTnsrLiCjgTMBIM83hMpNAkojDRXR9UuUvbkEqloqhXmQQJuRKsJhRog01aS32Ag1zXTfyT4cfzsKie/Te7R2URcDhBgfqRuoiGADXpCyddfXhoH900v+nJjybESP7uL8s+VIcvu2Wb5z1Xs6k1XY7bh14HXgr0EarOJ/sWmfBNKV5AkJTTpTyPTfTYUGkZpRD6QS5gozQa3IFvoGCJKDCojZb4j3DTHGcSvOExjV7t6IgiVKLJDLKhOiZup+ryP/l/FzH/bBgIss1CFriRuF8+btT/R7nHOsUV1fAUyaBar4wgFDJzACYzogkVJtbmS3facFZBGZCAWWTF/BNz2tXDd4femFRjViZaXgZwFcyzj+DZHHpONX+vfvbXgfjg47X6/Q+ddvHr1eX2EIv0Su0jzz0Dh2jU3SORoiiP9amtW3t2BP7u/3D/rmU2taq5gVqhP3rL2S45Fw=</latexit>

<latexit sha1_base64="Mle9wEuUWe4FiFsC/hm4766FpCs=">AAAC1nicbVFNb9NAEF2bjwbz0RSOXFaESuUS7DYNORY1hx6KKCJJI8UmWm/GzdL12t1dQyLL3BBXfh78GcTaCVLcMNJKT2/ezLyZDVPOlHbd35Z95+69+zuNB87DR4+f7Db3no5UkkkKQ5rwRI5DooAzAUPNNIdxKoHEIYfL8Pq0zF9+AalYIgZ6mUIQkyvBIkaJNtS0Kfd9DQtdNZqcDd6dB3nn+K3bPSxyn8MN9tWN1LnfB65JUTjb6qN+7/i0909NeDonRvb+YFXyKT963SleORtZZ9psuW23CrwNvDVooXVcTPesc3+W0CwGoSknSk08N9VBTqRmlEPh+JmClNBrcgUTAwWJQQV55bLA+4aZ4SiR5gmNK3azIiexUss4NMqY6Lm6nSvJ/+UmmY56Qc5EmmkQtMC1wsVqulNOjzKOdYLL8+MZk0A1XxpAqGRmAUznRBKqzSeZ82604CwEs6GAos4L+KoXlasaPxl4QV6uWJqpeenDZzLKPoJkUeE45f2929feBqPDttdtdz90Wicv1z/RQM/RC3SAPPQGnaAzdIGGiKJf6I+1YzXssf3N/m7/WElta13zDNXC/vkXYUfiEw==</latexit>

→ω

→

↑

!

<latexit sha1_base64="Mle9wEuUWe4FiFsC/hm4766FpCs=">AAAC1nicbVFNb9NAEF2bjwbz0RSOXFaESuUS7DYNORY1hx6KKCJJI8UmWm/GzdL12t1dQyLL3BBXfh78GcTaCVLcMNJKT2/ezLyZDVPOlHbd35Z95+69+zuNB87DR4+f7Db3no5UkkkKQ5rwRI5DooAzAUPNNIdxKoHEIYfL8Pq0zF9+AalYIgZ6mUIQkyvBIkaJNtS0Kfd9DQtdNZqcDd6dB3nn+K3bPSxyn8MN9tWN1LnfB65JUTjb6qN+7/i0909NeDonRvb+YFXyKT963SleORtZZ9psuW23CrwNvDVooXVcTPesc3+W0CwGoSknSk08N9VBTqRmlEPh+JmClNBrcgUTAwWJQQV55bLA+4aZ4SiR5gmNK3azIiexUss4NMqY6Lm6nSvJ/+UmmY56Qc5EmmkQtMC1wsVqulNOjzKOdYLL8+MZk0A1XxpAqGRmAUznRBKqzSeZ82604CwEs6GAos4L+KoXlasaPxl4QV6uWJqpeenDZzLKPoJkUeE45f2929feBqPDttdtdz90Wicv1z/RQM/RC3SAPPQGnaAzdIGGiKJf6I+1YzXssf3N/m7/WElta13zDNXC/vkXYUfiEw==</latexit>

→ω

<latexit sha1_base64="gAtivJiiN7RhCLUR7sS8v0TqIZQ=">AAAC23icbVFNb9NAEF27fBTTQlqOXFaESuUS7JKkORY1hx6KKCJJK8UmWm/GydL12t1d00SWT9wQV34cB/4LaydIdcNIKz29eTP7ZiZMOVPadX9b9taDh48ebz9xnu7sPnve2NsfqSSTFIY04Ym8CokCzgQMNdMcrlIJJA45XIbXp2X+8htIxRIx0MsUgpjMBIsYJdpQk8btga9hoatG47PBh/Mgb3feu92jIvc53GBf3Uid+33gmhSFs6l+1+91Tnv/1ISnc1LKPsYwI4erui955227eOOsJBXlTBpNt+VWgTeBtwZNtI6LyZ517k8TmsUgNOVEqbHnpjrIidSMcigcP1OQEnpNZjA2UJAYVJBXVgt8YJgpjhJpntC4Yu9W5CRWahmHRhkTPVf3cyX5v9w401EvyJlIMw2CFrhWuFj97pS/RxnHOsHlDfCUSaCaLw0gVDIzAKZzIgnV5lJmeXdacBaCmVBAUecF3OpF5arGjwdekJcjlmZqXvrwlYyyzyBZVDhOuX/v/rY3weio5XVb3U/t5snr9SW20Uv0Ch0iDx2jE3SGLtAQUfTH2rJ2rF07sL/bP+yfK6ltrWteoFrYv/4CfevjIg==</latexit>

→!

<latexit sha1_base64="MyxiWHZthkqe3TPxjtWD9U47g1c=">AAADBXicbVFNb9NAEF27fBTz0bTc4LIirVQuwS5JyLGoOfQAoogkrWSbaL0ZJ0vXH91dQyLLZ278E26IK7+D/8EPYO0YqW4YaaWnN29mZ+YFKWdS2fZvw9y6dfvO3e171v0HDx/ttHb3JjLJBIUxTXgiLgIigbMYxoopDhepABIFHM6Dy5Myf/4ZhGRJPFKrFPyIzGMWMkqUpqatbweegqWqGrmno7dv/Lzbe233j4rc43CFPXklVO4NgStSFNam+uVw0DsZ/FMTni5IYXnvIpgTL2DzQy8UhNYNPua9F91Ca9eyMv9ct6wqK4E1bbXtjl0F3gRODdqojrPprjH1ZgnNIogV5URK17FT5edEKEY56FEyCSmhl2QOroYxiUD6ebVBgQ80M8NhIvSLFa7Y6xU5iaRcRYFWRkQt5M1cSf4v52YqHPg5i9NMQUwL3Chcrn9vcuWZ9H01FWYcqwSXbuEZE0AVX2lAqGB6J0wXREuV9lSf7loHzgLQS8dQNPkYvqhlNWiDd0eOn5dbl/M1RhnCJzLJPoBgYWFZpSXOTQM2weSo4/Q7/ffd9vF+bc42eoqeoUPkoFfoGJ2iMzRGFP0xnhhtY9/8an43f5g/11LTqGseo0aYv/4C3RD1aw==</latexit>

<latexit sha1_base64="XQRPvjMTg+n3FL69QZ68WY4OtYk=">AAAC23icbVFNb9MwGHYyPkbYoBtHLhZl0riUZOtKj0PrYYchhmi7SU2oHPdNa+Y4me1sraKcuCGu/DgO/BectIhl5ZUsPXre5/H7FaacKe26vyx748HDR483nzhPt7afPW/s7A5VkkkKA5rwRF6GRAFnAgaaaQ6XqQQShxwuwquTMn9xA1KxRPT1IoUgJlPBIkaJNtS4cbvna5jr6qPRaf/DWZC3j967nYMi9zlcY19dS537PeCaFIWzrj7sdY9Oun/VhKczUjj+xximZH9p+5Ifvm0Xb4z3n8QZN5puy60CrwNvBZpoFefjHevMnyQ0i0FoyolSI89NdZATqRnlYGpmClJCr8gURgYKEoMK8qrVAu8ZZoKjRJonNK7Yu46cxEot4tAoY6Jn6n6uJP+XG2U66gY5E2mmQdAC14zzZXWnrB5lHOsElzfAEyaBar4wgFDJzACYzogkVJtLmT3d+YKzEMyEAoo6L+BWz6uuavyo7wV5OWLZTK2XHnwlw+wzSBYVjlPu37u/7XUwPGh5nVbnU7t5/Hp1iU30Er1C+8hD79AxOkXnaIAo+m1tWFvWth3Y3+zv9o+l1LZWnheoFvbPP7YZ4zw=</latexit>

!(”3/4 )

<latexit sha1_base64="K69GnJ5AZ7CskYAoFhUO1z4qFTM=">AAACMnicbVDLSsNAFJ34rPHV6rKbYBHERUlEqsuCG5ct9AVtKJPpbTt0Mgkzk2oJ/QK3+if+jO7ErR/hJM3CtF64cDj3Xs49xwsZlcq2P4yt7Z3dvf3CgXl4dHxyWiyddWQQCQJtErBA9DwsgVEObUUVg14oAPseg643e0jm3TkISQPeUosQXB9POB1TgpWmmvNhsWJX7bSsTeBkoIKyagxLRnkwCkjkA1eEYSn7jh0qN8ZCUcJgaQ4iCSEmMzyBvoYc+yDdOP10aV1qZmSNA6GbKytl/17E2Jdy4Xt608dqKtdnCfnfrB+p8b0bUx5GCjhZCY0jZqnASmxbIyqAKLbQABNB9a8WmWKBidLh5FQY9UB74XkrMYcn9ZzK53RbjhsnVhJR0zR1nM56eJugc1N1atVa87ZSv86CLaAyukBXyEF3qI4eUQO1EUGAXtArejPejU/jy/herW4Z2c05ypXx8wubQKnr</latexit>

!

! ”5/4 " ω

𝐿 <latexit sha1_base64="K69GnJ5AZ7CskYAoFhUO1z4qFTM=">AAACMnicbVDLSsNAFJ34rPHV6rKbYBHERUlEqsuCG5ct9AVtKJPpbTt0Mgkzk2oJ/QK3+if+jO7ErR/hJM3CtF64cDj3Xs49xwsZlcq2P4yt7Z3dvf3CgXl4dHxyWiyddWQQCQJtErBA9DwsgVEObUUVg14oAPseg643e0jm3TkISQPeUosQXB9POB1TgpWmmvNhsWJX7bSsTeBkoIKyagxLRnkwCkjkA1eEYSn7jh0qN8ZCUcJgaQ4iCSEmMzyBvoYc+yDdOP10aV1qZmSNA6GbKytl/17E2Jdy4Xt608dqKtdnCfnfrB+p8b0bUx5GCjhZCY0jZqnASmxbIyqAKLbQABNB9a8WmWKBidLh5FQY9UB74XkrMYcn9ZzK53RbjhsnVhJR0zR1nM56eJugc1N1atVa87ZSv86CLaAyukBXyEF3qI4eUQO1EUGAXtArejPejU/jy/herW4Z2c05ypXx8wubQKnr</latexit>

𝐿

Figure 2: On the left, we consider the case of many low-degree neighbors (discussed in the intro). On the right, we consider the case of many high-degree neighbors. Any blue node influences at most α + 1 events Iu := {r(v)√< min (r(w) | w in-neighbor of v)} for u ∈ N (v), in both cases. Any green node influences at most ∆+1 (resp. ∆+1) events Ou := {r(v) < min (r(w) | w out-neighbor of v)} for u ∈ N2 (v). u, we consider two events: Ou : u has smaller rank than all of its out-neighbors, Iu : u has smaller rank than all of its in-neighbors. If both events occur, then u has the smallest rank among all of its neighbors and therefore joins the ruling set. The analysis is split into two phases, first showing that enough nodes in the 2-hop neighborhood of a large-degree node v satisfy their event Ou , and then among those successful in the first phase at least one satisfies its respective event Iu , yielding that v is covered. First phase of the analysis. We first focus on the events Ou ; see Figure 2 (left) for an illustration. Since u has at most α out-neighbors, the probability that it beats all of them is at least 1/(α + 1), which is Θ(1) when α is constant. Thus, among the many neighbors of v, we expect a constant fraction to satisfy Ou . The main obstacle is that the events √ Ou are not independent. However, the dependencies are limited as only nodes with degree at most ∆ are active and can only affect the events √ corresponding to itself and its neighbors. Thus, using a read-k concentration bound with k = ∆, we show that the actual number of successful nodes remains close to its expectation. In particular, with high probability there are still Ω(∆3/4 /α) successful nodes in N (v). Second phase of the analysis. Having identified many successful nodes, we √ now ask whether at least one of them also satisfies Iu . Since every active node has degree at most ∆, √ the probability that a successful node additionally beats all of its in-neighbors is at least 1/( ∆ + 1) and in expectation such a fraction joins the independent set. Again, the events Iu considered in the second phase of the analysis are not independent, and additional dependencies on nodes’ ranks are introduced due to conditioning on the nodes’ success in the first phase of the analysis; see Section B for an example illustrating the new dependencies that have not been reasoned about in [61]. We remove the latter dependencies by applying a version of the Harris-FKG inequality [27, 68], effectively reducing to the case without any conditioning on success from the first phase of the analysis. Then each (independent) rank affects only α + 1 of 8

the events Iu ; hence, among Ω(∆3/4 /α) successful candidates that beat their out-neighbors, read-k concentration implies that with high probability at least one also beats its in-neighbors and joins the independent set. * Case of many high-degree neighbors. The case where v has many high-degree neighbors can be handled in a very similar manner by considering nodes in N2 (v), see Figure 2 (right) for an illustration. One can show that some node in this two-hop neighborhood joins the independent set with probability at least 1 − 1/n. Repeating the process for O(1) rounds then implies that every high-degree node is covered with probability at least 1 − 1/nc . The Remaining Low-Degree Graph. Lemma 5 allows us to reduce the degree to poly log n, which allows us to use [32] to compute a partial independent set in O(log ∆) = O(log log n) rounds such that the remaining unsolved graph shatters into components of size O(poly log n). Postshattering based on [9] would compute an MIS for the√remaining components in O(α2 + log log n) = O(log log n) rounds for instances up to arboricity O( log log n). To prove Theorem 1, we design a slightly different post-shattering by abusing the fact that we are computing a 2-ruling set, making it work up to arboricity O(log log n). In fact, our degree drop lemma (Lemma 5) applies w.h.p. to graphs of arboricity up to poly log n, reducing the maximum degree to poly log n. The main remaining challenge is handling this residual polylogarithmic-degree graph. This regime is difficult because both the maximum degree and the arboricity may still be O(poly log n), which is already as hard as general graphs. Our Theorem 2 addresses this case using the subsampling approach of [15], which exploits the relaxed requirements of computing a 2-ruling set.

2

Preliminaries & Notation

Given a graph G = (V, E), we denote by N (v) the neighborhood of v (excluding v itself). For a node v ∈ V we let deg(v) := |N (v)| denote the degree of v. Furthermore we denote by N2 (v) all nodes w ∈ V with distG (v, w) ≤ 2, i.e., the 2-hop neighborhood of v (again excluding v itself). By N2− (v) we denote all nodes w ∈ V with distG (v, w) = 2, i.e., the exclusive 2-hop neighborhood of v. Note that N2− (v) ⊂ N2 (v) and N2− (v) = N2 (v) \ N (v). For a subset W ⊂ V , let G[W ] be the induced subgraph of the subset W . For an oriented graph and a node v, we let N + (v) be the out-neighbors of v and N − (v) be the in-neighbors of v. We denote {1, . . . , n} by [n] for n ∈ N. An algorithm is correct w.h.p. (with high probability) if there exists a constant c > 1 such that e as follows: g(n) ∈ O(f e (n)) if there exists it errs with probability ≤ 1/nc . We use the notation O c a constant c such that g(n) ∈ O(f (n) · log (f (n))). Additionally, we will need some well-known results about graphs of bounded arboricity [9], and Lemma 9 is a standard result and we omit the proof. Lemma 6. [9, Lemma 3.1] A graph G = (V, E) with arboricity α has at least |V2 | nodes with degree 4α or less. Definition 7. Let G = (V, E) be a graph with arboricity α. A partition of the vertex set H1 , . . . Hℓ is a H−partition with degree at most (2 S + ϵ) · α of size ℓ if every v ∈ Hi , i ∈ {1, . . . , ℓ}, has at most (2 + ϵ) · α neighbors in the vertex set ℓj=i Hj . Lemma 8. [9, Lemma 3.3 and 3.4] For a graph G with arboricity α, and a parameter ϵ, 0 < ϵ ≤ 2, we can compute an H-partition of size ℓ ≤ ⌊ 2ϵ log n⌋ with degree at most (2+ϵ)·α in O(log n) rounds. Lemma 9. Let G be a graph with arboricity α and let M ⊆ V be a set of nodes. Then there exists an independent set I ⊆ M with |I| ≥ |M |/2α. 9

Read-k Families. We now define a read-k family of random variables. Informally speaking, a read-k family is a set of (possibly dependent) random variables {Yj | 1 ≤ j ≤ m} which are fully determined by an underlying set of independent random variables {Xi | 1 ≤ i ≤ n} such that each Xi influences at most k different random variables Yj . For k = 1 the Yj ’s are independent, and for k > 1 the Yj ’s can have an arbitrary dependency structure. Definition 10 (Read-k families). Let X1 , . . . , Xn be independent random variables. For j ∈ [m], let Pj ⊆ [n] and let fj be a Boolean function of (Xi )i∈Pj . Assume that |{j | i ∈ Pj }| ≤ k for every
i ∈ [m]. Then the random variables Yj = fj (Xi )i∈Pj ) are called a read-k family. For read-k families, [30] showed Chernoff-Like bounds allowing us to make statements about the concentration of such random variables. Theorem 11. [30, Corollary of Theorem 1.1]P Let Y1 , . . . , Ym be a family of read-k indicator random variables with Pr[Yi = 1] = pi . Let Y := m i=1 Yi . Then for any δ > 0,  2  δ E[Y ] Pr[Y ≤ (1 − δ)E[Y ]] ≤ exp − . 2k Theorem 11 is not exactly stated as in [30], but it can be derived from it. Similarly, Theorem 12 can be derived from [30]. For completeness, we include the derivations, see Section C. Theorem 12. [30, Corollary of Theorem 1.2] Let Y1 , . . . , Ym be a family of read-k indicator random variables with Pr[Yi = 1] ≤ p. Then Pr[Y1 = · · · = Ym = 1] ≤ pm/k .

3

Randomized 2-Ruling Set for Low Arboricity Graphs

The goal of this section is to prove the following statement. Theorem 1. There is an O(log log n)-round CONGEST algorithm that w.h.p. computes a 2-ruling set in graphs with arboricity up to O(log log n). To prove this result, we first show how to reduce the degree of the graph to ∆′ = O(poly log n) in O(log log ∆) rounds (see Section 3.1), by iteratively computing independent sets and removing their 2-hop neighborhoods from the graph. In Section 3.2, we handle the remaining low-degree graph using a known result of [32], which leaves us with components of size N = O(poly log n). Finally, in Section 3.3, we handle these small components by deterministically computing a 2-ruling set in each component in parallel, in O(log N ) = O(log log n) rounds.

3.1

Stage I: Degree Drop

In this section, we show how to reduce the degree of the graph to ∆′ = O(poly log n) in O(log log ∆) rounds by iteratively reducing the degree polynomially. In particular, we compute an independent set S in O(1) rounds such that all nodes of degree at least ∆3/4 are contained in the 2-hop neighborhood S ∪ N2 (S) w.h.p. Repeating this procedure for O(log log ∆) rounds reduces the degree sufficiently. In particular, we will prove Lemma 5 and restate it here for completeness. Lemma 5 (Degree Drop). There is an O(log log ∆)-round algorithm that computes an independent set S, such that G \ (S ∪ N2 (S)) has maximum degree ∆′ ≤ max{(66)8 , log8 n} w.h.p. In order to prove Lemma 5, we will show how we can reduce the max degree polynomially in O(1) rounds. 10

Lemma 13. Let G be a graph with arboricity α and max degree ∆ ≥ max{(66α4 )8 , log8 n}. There exists a procedure that computes an independent set S in O(1) rounds, such that G \ (S ∪ N2 (S)) has max degree ∆′ ≤ ∆3/4 w.h.p. The degree drop procedure for Lemma 13 is given by Algorithm 1. Running Algorithm 1 for O(log log ∆) rounds implies Lemma 5, as we will see at the end of this subsection. For the rest of the section let U be the set of uncovered nodes after executing Algorithm 1, i.e., U := {v ∈ V | v ∈ V \ (S ∪ N2 (S))}. In order to prove Lemma 13 we show that every node v with deg(v) ≥ ∆3/4 is not in U w.h.p. Algorithm 1: Degree-Drop(G, ∆, c) 1

S←∅

2 for i = 0 to c do

3 4 5 6 7 8

9 10 11 12 13

// Phase 1 √ A ← L = {v ∈ V | deg(v) ≤ ∆} // Active Nodes Uniformly and independently at random compute a real rv ∈ (0, 1) for each v ∈ A In parallel for all v ∈ A if rv < rw ∀w ∈ N (v) ∩ A then S ← S ∪ {v} Remove S ∪ N2 (S) from G // Phase 2 Uniformly and independently at random compute a real rv ∈ (0, 1) for each v ∈ V In parallel for all v ∈ V if rv < rw ∀w ∈ N (v) then S ← S ∪ {v} Remove S ∪ N2 (S) from G

High Level Proof Idea. We will consider two different types of high degree nodes; √ either a node v with deg(v) ≥ ∆3/4 has at least deg(v)/2 neighbors with degree at most ∆ or at √ least deg(v)/2 neighbors with degree larger than ∆. In both cases, we want to show that v is covered, after invoking Algorithm 1 with a constant c, with probability at least 1 − n1c . For the rest of the section, let √ L = {v ∈ V | deg(v) ≤ ∆}, H1 = {v ∈ V | deg(v) ≥ ∆3/4 , |N (v) ∩ L| ≥ deg(v)/2}, H2 = {v ∈ V | deg(v) ≥ ∆3/4 , |N (v) ∩ L| < deg(v)/2}, 3/4 and at least half of their neighbors have i.e., H1 is the set √ of nodes that have degree at least ∆ degree at most ∆ and H2 is the set of √ nodes that have degree at least ∆3/4 and less than half of their neighbors have degree larger than ∆. Observe that for every node v with deg(v) ≥ ∆3/4 it holds that v ∈ H1 or v ∈ H2 , so in particular it suffices to show that every node in H1 and H2 will be covered by Algorithm 1 w.h.p. The proof works similarly for both cases; we consider a node v and find a set M (v) ⊆ N2 (v) of sufficient size w.r.t. the max degree of the active nodes in the corresponding phase. The node v then gets covered if at least one node u ∈ M (v) joins the independent set, since the distance √ of v to u is at most 2. In particular, in Phase 1 of Algorithm 1, only nodes with degree at most ∆ are active,

11

and we will find a set of size Ω(∆3/4 ) in the neighborhood of v. In Phase 2 of Algorithm 1 all nodes are active, so the max degree is ∆ and we will find a set of size Ω(∆5/4 /α) in the 2-hop neighborhood of v. In particular, both sets are polynomially (in ∆) larger than the corresponding (active) max degree of the graph. To show that at least one node of M (v) joins S with high probability, we use read-k families. Successful Nodes and Read-k Families. Throughout the analysis of both cases, we will fix an arbitrary α-out-degree orientation. Notice that our algorithm does not rely on or use this orientation, but it is solely used for the analysis. With respect to this fixed orientation, we can define the notation of successful nodes. Recall that for an oriented graph and a node v, we denote N + (v) as the out-neighbors of v and N − (v) as the in-neighbors of v. Definition 14. Let G = (V, E) be an oriented graph. We say a node v is successful in one iteration of Phase 1 or 2 if its real r(v) is smaller than the real of all its out-neighbors, i.e., r(v) < min{r(u) | u ∈ N + (v)}. We say a set of nodes is successful if all nodes of that set are successful. In both cases, we will consider a fixed set M (v) ⊆ N2 (v) and want to argue that at least one node joins the independent set S w.h.p. First, we will show that a large fraction of the set M (v) will be successful nodes. Second, we will show that one of those nodes also joins with a large probability. We formulate both of these results in a more general setting, and will see in Section 3.1.1 and Section 3.1.2 how to apply the statements to each of the cases. Lemma 15. Let G = (V, E) be a graph with arboricity α, and (active) max degree Λ. Let M ⊆ V be a fixed subset of (active) nodes. Then, with probability at least   |M | 1 − exp − 8(α + 1)(Λ + 1) at least |M |/2(α + 1) nodes of M are successful. Proof. Recall that we have a fixed α-outdegree orientation for the analysis. We define the events Ev = {r(v) < min{r(u) | u ∈ N + (v)}} for all v ∈ M , and let Yv be the indicator r.v. of Ev . Note that every event Ev is fully determined by the ranks r(u) of the nodes u ∈ (v ∪ N + (v)), i.e., Yv = fv (r(u)u∈(v∪N + (v)) ) for some boolean functions fv . Since all active nodes have degree at most Λ, each rank r(v) influences at most Λ + 1 many r.v. Yv ; the r.v. Yu for u ∈ N − (v) and P Yv if v ∈ M . Therefore, {Yv | v ∈ M } and {r(v) | v active} form a read-(Λ + 1) family. Let Y := v∈M Yv be the 1 number of successful nodes in M and observe that P[Yv = 1] ≥ α+1 , since each node has at most α |M | out neighbors. Therefore, E[Y ] ≥ α+1 . Thus, we can apply Theorem 11 to obtain

P[Y ≤ |M |/2(α + 1)] ≤ exp −

1 2 |M |/(α + 1) 2 2(Λ + 1)

!

 ≤ exp −

|M | 8(α + 1)(Λ + 1)

 ,

  |M | and therefore P[Y ≥ |M |/2(α + 1)] ≥ 1 − exp − 8(α+1)(Λ+1) . In both cases we will use that result to show that we can obtain a large number of successful nodes in the 2-hop neighborhood of any node v with degree ≥ ∆3/4 . In order to show that v gets covered, it suffices to show that one of those successful nodes joins the independent set. For that, at least one node also has to have a smaller rank r(u) than all of its in-neighbors. Thus, you may think of M in the statement as the successful 2-hop neighbors of a node we want to cover. 12

Lemma 16. Let G = (V, E) be a graph with arboricity α, and (active) max degree Λ. Let M ⊆ V be a fixed subset of successful, independent (active) nodes. Then, with probability at most  1−

1 Λ+1

|M |/α

no node in M chooses a rank smaller than all its in-neighbors. Proof. Again, recall that we have a fixed α-outdegree orientation for the analysis. We define the events Fv = {r(v) < min{r(u) | u ∈ N − (v)}} and Ev = {r(v) < min{r(u) | u ∈ N + (v)}} for all v ∈ M , and let Zv be the Fvc . S indicator r.v. of T Further define F = v∈M Fv and E = v∈M Ev , i.e., E is the event that M is successful and F is the event that at least one node of M also beats its in-neighbors. First, we aim to upper bound P[F c | E] by the unconditional probability P[F c ]. To this end define the transformed r.v. ( 1 − r(v), if v ∈ M, Xv = r(v), if v ∈ / M. Since the ranks r(v) are mutually independent, the r.v. Xv are mutually independent as well. Further, since M is an independent set, every neighbor z ∈ N (M ) satisfies z ∈ / M . Thus, for every v ∈ M and every z ∈ N (v), we have r(v) < r(z) ⇔ Xv + Xz > 1. Consider the coordinate-wise partial ordering of X = (Xv )v∈V : We say X ≤ X ′ if Xv ≤ Xv′ coordinate-wise (for all v ∈ V ). Observe that the indicator r.v. of the event {Xu + Xz > 1} is non-decreasing in X w.r.t. the coordinate-wise partial ordering of X. Every event Fv and Ev is an intersection of such events and thus their indicator r.v.’s are non-decreasing. Similarly, the indicator r.v. 1E of E and 1F of F are non-decreasing in X, as they are an intersection of Eu ’s, or a union of Fu ’s, respectively. Since the variables (Xv )v∈V are mutually independent, we can apply Theorem 31 and obtain that Cov(h(X), g(X)) = E[h(X)g(X)] − E[h(X)]E[g(X)] ≥ 0 for any pair of non-decreasing functions h, g. Therefore, by setting h = 1E and g = 1F we obtain E[1E 1F ] ≥ E[1E ]E[1F ]. By using the fact that E[1E 1F ] = E[1E∩F ], this yields P[E ∩F ] ≥ P[E] Pr[F ]. Since P[E] > 0, we get P[F | E] ≥ P[F ], or equivalently P[F c | E] ≤ P[F c ]. As the second step we upper bound the unconditional probability P[F c ] using read-k families. Note that every event Fvc is fully determined by the independent (we do not condition on M being successful in this step, but consider the unconditional probability) ranks r(u) of the nodes u ∈ (v ∪ N − (v)), i.e., Zv = fv (r(u)u∈(v∪N − (v)) ) for some boolean functions fv . Note that the inneighbors of a node v ∈ M are not in M . Since every node has at most α out-neighbors, each (active) node v influences at most α different r.v. Zv ; the r.v. Zu for u ∈ N + (v) if v ∈ / M and only Zv if v ∈ M . Therefore, {Zv | v ∈ M } and {r(v) | v active} form a read-α family. Here it is crucial that the underlying ranks are independent, which would not be the case if we were to consider the ranks after conditioning on M ’s success, see Section B. Furthermore, observe that 1 P[Zv = 1] = 1 − deg−1(v)+1 ≤ 1 − Λ+1 . Thus, we can apply Theorem 12 and bound the probability that no node v ∈ M chooses a rank smaller than all its in-neighbors by  |M |/α ^ 1 c c . P[F | E] ≤ P[F ] = P[ Zv = 1] ≤ 1 − Λ+1 v∈M

We have set up all the general statements that hold for any graph of arboricity α and can show for the first case v ∈ H1 that v gets covered w.h.p. 13

3.1.1

Many Low-Degree Neighbors

In this subsection, we show that a node v ∈ H1 stays uncovered with probability at most 1/n during one iteration of Phase 1 of Algorithm 1. So for the rest of this subsection, we assume √ that only nodes in L are active; in particular, we know that the max degree of the active nodes is ∆. Lemma 17 (Many Low-Degree Neighbors). Let ∆ ≥ max{(66α3 )8 , log8 n} and U it be the set of uncovered nodes after one arbitrary iteration of the for-loop of Algorithm 1. For a node v ∈ H1 at the beginning of the iteration, we have P[v ∈ U it ] ≤ n1 . 3/4

Proof. Let L(v) := N (v) ∩ L and observe that |L(v)| ≥ ∆2 , since v ∈ H1 . By Lemma 9 there exists an independent set I ⊆ L(v) with |I| ≥ |L(v)|/2α ≥ ∆3/4 /4α. First, we will find a large subset of independent successful nodes in √ the neighborhood of v. Recall that in Phase 1 of Algorithm 1 only nodes with degree less than ∆ are active. Now we apply Lemma 15 to I and obtain a set of successful nodes M (v) of size |M (v)| ≥ |I|/2(α + 1) ≥ ∆3/4 /9α2 with probability at least !   ∆3/4 |I| √ √ ≥ 1 − exp − 1 − exp − 8(α + 1)( ∆ + 1) 64α2 (α + 1)( ∆ + 1) ! ∆1/4 1 = 1 − exp − ≥ 1 − exp (− log n) = 1 − . 66α3 n Second, we upper bound the probability that none of those successful nodes joins the independent set. By Lemma 16 we obtain that no node of I joins the independent set with probability at most !  |M (v)|/α   1 |M (v)| ∆3/4 √ 1− √ ≤ exp − √ ≤ exp − ∆+1 α( ∆ + 1) 10α3 ∆ ! ∆1/4 ≤ exp − ≤ exp(− log n). 10α3 Thus P[v ∈ U it ] ≤ P[no node of M (v) joins the independent set] ≤ n1 . 3.1.2

Many High-Degree Neighbors

In this subsection, we show that a node v ∈ H2 stays uncovered with probability at most 1/n during one iteration of Phase 1 of Algorithm 1. In contrast to the prior case, all the nodes are active and thus the max degree is ∆. Formally, we show the following. Lemma 18 (Many High-Degree Neighbors). Let ∆ ≥ max{(66α4 )8 , log8 n} and U it be the set of uncovered nodes after one arbitrary iteration of the for-loop of Algorithm 1. For a node v ∈ H2 at the beginning of the iteration, we have P[v ∈ U it ] ≤ n1 . The proof for this case is very similar to the proof we have just seen, but we need to use arboricity in one more step to obtain a set of sufficient size within the 2-hop neighborhood of v. Lemma 19 (Large 2-Hop Neighborhood). Let G be a graph with arboricity α and max degree ∆ ≥ 5/4 16α2 . Consider a node v ∈ H2 . Then |N2− (v)| ≥ ∆4α .

14

Proof. Let d := deg(v). Consider the induced subgraph G[N (v) ∪ N2− (v)] and let mN denote the number of edges on this subgraph. Then we obtain that mN ≤ α(deg(v) + |N2− (v)|) ⇔ |N2− (v)| ≥ We know that mN ≥ deg(v) ·

√

mN − deg(v). α

∆/2 and deg(v) ≥ ∆3/4 , which implies that |N2− (v)| ≥ ∆5/4 /2α − ∆3/4 .

In particular, for ∆ ≥ 16α2 , we have that |N2− (v)| ≥ ∆5/4 /4α. Proof of Lemma 18. By Lemma 19, we know that |N2− (v)| ≥ ∆5/4 /4α, since v ∈ H2 . Thus, by Lemma 9 there exists an independent set I ⊆ N2− (v) with |I| ≥ |N2− (v)|/2α ≥ ∆5/4 /8α2 . Now we can apply Lemma 15 to I and obtain a set of successful nodes H(v) of size |H(v)| ≥ |I|/2(α + 1) ≥ ∆5/4 /17α3 with probability at least !   |N2− (v)| ∆5/4 1 − exp − ≥ 1 − exp − 8(α + 1)(∆ + 1) 64α2 (α + 1)(∆ + 1) ! ∆1/4 1 ≥ 1 − exp (− log n) = 1 − . = 1 − exp − 66α3 n Second, we upper bound the probability that none of those successful nodes joins the independent set. By Lemma 16 we obtain that no node of H(v) joins the independent set with probability at most ! !  |H(v)|/α   1 |H(v)| ∆5/4 ∆1/4 1− ≤ exp − ≤ exp − ≤ exp − ∆+1 α(∆ + 1) 18α4 ∆ 18α4 ≤ exp(− log n). Thus P[v ∈ U it ] ≤ P[no node of H(v) joins the independent set] ≤ n1 . Now we are ready to prove Lemma 13 Proof of Lemma 13. Let c be the constant Algorithm 1 is called with. Since degrees only reduce during Algorithm 1, a node v starting with deg(v) > ∆3/4 at the beginning of the call of Algorithm 1 might have a degree ≤ ∆3/4 after some iterations of the for-loop. Then v did not get covered, but its degree still dropped far enough and is at most ∆3/4 . Thus, we may assume the degree of a node v with deg(v) > ∆3/4 does not drop below ∆3/4 during the call of Algorithm 1. As long as ∆ ≥ max{(66α4 )8 , log8 n} Lemma 17 and Lemma 18 hold. Then for v, since deg(v) > ∆3/4 at the beginning of each iteration of the for-loop, it either holds that v ∈ H1 or v ∈ H2 . Since we always sample new random values at the beginning of each iteration, we can either apply Lemma 17 or Lemma 18 to each v in each iteration. Thus P[v ∈ U ] ≤ (P[v ∈ U it ])c ≤

1 . nc

Therefore, v gets covered w.h.p. and removed from the graph after Algorithm 1. Finally, we can prove the Degree Drop Lemma, which we restate here for readability.

15

Lemma 5 (Degree Drop). There is an O(log log ∆)-round algorithm that computes an independent set S, such that G \ (S ∪ N2 (S)) has maximum degree ∆′ ≤ max{(66)8 , log8 n} w.h.p. Proof of Lemma 5. We run Algorithm 1 for T := O(log log ∆) rounds, always calling it on the remaining graph after iteration. Let S1 , . . . , ST be the ruling sets computed in these  S the previous T := calls and let S i=1 Si . This algorithm runs in O(log log ∆) rounds, since each call takes T

O(1) rounds. The max degree of the remaining graph is max{∆(3/4) , (66α4 )8 , log8 n} w.h.p. by T combining Lemma 13 with a union bound over the T iterations. Since ∆(3/4) = O(1), we have that the max degree of the remaining graph is max{(66α4 )8 , log8 n} w.h.p. When the arboricity of the given graph is bounded by O(poly log n), we get a degree reduction to O(poly log n). Corollary 20. Let G = (V, E) be a graph of arboricity O(poly log n) and with max degree ∆. There is an O(log log ∆) round algorithm that takes G as input and returns an independent set S such that G′ = G \ (S ∪ N2 (S)) has max degree ∆′ = O(poly log n) w.h.p. Proof. This follows by Lemma 5 by observing that max{(66α4 )8 , log8 n} = O(poly log n) when α = O(poly log n).

3.2

Stage II: Shattering

After applying Corollary 20, we can assume that we are given a graph of max degree ∆ = O(poly log n). In this case, we can use the existing work of [32] to compute an MIS such that the remaining graph consists only of small components. Lemma 21 (Low max degree). Let G be a graph with max degree ∆ ≤ logc n, for some constant c > 0. There is a O(log log n) round algorithm that computes an independent set S such that all connected components of G \ (S ∪ N (S)) have size O(poly log n) w.h.p. Proof. Run Ghaffari MIS algorithm [32], which computes an MIS, such that after O(log ∆) = O(log log n) rounds the remaining graph consists of components of size N := O(log∆ n · ∆4 ) = O(poly log n) w.h.p.

3.3

Stage III: Deterministic 2-Ruling Set for Small Components

After applying Corollary 20 and Lemma 21, we are left with a graph that consists of components of size N := O(poly log n). In this subsection, we present a simple and self-contained algorithm to compute a 2-ruling set that we can apply to compute a 2-ruling set on all the connected components in parallel in O(log N ) = O(log log n) rounds, since we assume the arboricity to be O(log log n). Theorem 22. Given a graph with arboricity α, there exists a deterministic CONGEST algorithm computing a 2-ruling set in O(log n + α) rounds. Even though the runtime can also be achieved by combining prior work, e.g. by computing a O(α2 )-coloring using [9] and then  choosing B = α = O(log n) in [50] to compute a 2-ruling 2 log α set in O(B logB C) = O α log α = O(log n) rounds, we think that the algorithm may be of independent interest. The idea of the algorithm is to use the well-known notion of H-partition, Definition 7, and to heavily abuse the fact that we are computing a 2−ruling set. In particular, we will deactivate nodes 16

Algorithm 2: Deterministic 2-RS 1 Compute H-partition with degree 4α of size ℓ ≤ ⌊log n⌋

A ← V —Active nodes

2 for i = ℓ down to 1 do

In parallel for each node v ∈ V (Hi ) ∩ A, remove all nodes in N (v) ∩ V (Hj ) with j < i from A 4 Compute ∆ + 1 = O(a) = O(log n) coloring on G[A] 5 Compute MIS by standard reduction to coloring 3

such that each of the inactive nodes is adjacent to an active node and the induced graph on the active nodes consists of connected components with degree at most 4α. Which allows us to compute an MIS on each connected component efficiently in parallel. Proof of Theorem 22. The pseudocode for the algorithm is given by Algorithm 2. We start by computing a H-partition H1 , . . . , Hℓ with degree at most 4α of size ℓ ≤ ⌊log n⌋ = O(log n) in O(log n) rounds, see Lemma 8. Let A = V denote the active nodes. Iterate through the layers from ℓ down to 1. In iteration i each active node v ∈ A ∩ V (Hi ) deactivates all its neighbors that are in earlier layers, i.e., we remove u ∈ A ∩ V (Hj ) with j < i from A. This step can be performed in parallel for all nodes in V (Hi ) and thus only takes O(1) rounds; therefore, iterating through all layers takes O(ℓ) = O(log n) rounds. Claim. G[A] consists of connected components, each with maximum degree at most 4α and each node V \ A is adjacent to a node in A. If the claim holds, we can compute a ∆ + 1 = O(α) coloring on G[A] in O(∆ + log∗ n) = O(α + log∗ n) rounds [10] and turn it into an MIS in O(∆ + 1) = O(α) rounds by iterating through the color-classes. The MIS S of G[A] is a 2-ruling set of G, since every node is adjacent to a node in A and therefore dist(v, S) ≤ 2 for all nodes v ∈ V (G). The overall runtime then is O(log n + α) rounds, by first computing the H-partition and then the MIS on G[A]. In the remainder of this proof, we show that the claim holds. First, consider any node v that is active at the end of the algorithm. Assume v ∈ V (Hi ) and observe that v was active in iteration ℓ − i + 1, i.e., when we considered layer S Hi . Thus v deactivated all its neighbors from earlier layers, which implies degA (v) ≤ |N (v) ∩ ( ℓj=i Hj )| ≤ 4α since the H−partition has degree 4α. Secondly, consider any node v that got deactivated in the course of the algorithm, let i be the iteration in which v got deactivated. Let d(v) be the node that deactivated v. Since d(v) deactivated v in iteration i we know that d(v) ∈ Hℓ−i+1 . Furthermore, we know that only nodes in layers Hj with j < ℓ − i + 1 get deactivated throughout the rest of the algorithm. So d(v) is an active neighbor of v at the end of the algorithm. We can use this deterministic 2−ruling set algorithm for our remaining instances of size N = poly log n and arboricity O(log log n) in a straightforward way to obtain the following. Corollary 23. Given a graph of size N = O(poly log n) with arboricity O(log log n), there exists a deterministic CONGEST algorithm computing a 2-ruling set in O(log log n) rounds. Finally, we can prove Theorem 1. Proof of Theorem 1. Consider the following algorithm: We run the procedure of Corollary 20 computing an independent set S. Second, we invoke the procedure of Lemma 21 on G′ := G\(S ∪N2 (S))

17

to compute an independent set I. Finally, we invoke the procedure of Corollary 23 on all the components of G′ \ (I ∪ N (I)) in parallel to compute a ruling set on each individual one. Our final 2-ruling set is the union of S, I and the ruling set of each of the components. Correctness of the Subroutines. After the call of the first procedure, we are left with a graph of max degree O(poly log n) w.h.p. by Corollary 20. Thus, we can invoke the procedure of Lemma 21 which leaves us with small components of size O(poly log n) w.h.p. This in turn lets us call the procedure of Corollary 23 on each component in parallel. Runtime. By Corollary 20 after O(log log ∆) rounds G′ has a max degree of poly log n w.h.p. Therefore, the call of the procedure of Lemma 21 takes O(log log n) rounds and all connected components of G′ \ (I ∪ N (I)) have size O(poly log n) w.h.p. Thus, and since the procedure of Corollary 23 runs in parallel on each connected components, the computation of the independent sets on each component runs in O(log log n) rounds. Independence and Domination. In each called procedure, we always compute independent sets and remove each computed independent set and its 2-hop neighborhood before computing the next independent set, ensuring independence across the different calls of procedures. Before the final computation of ruling sets for each component, we removed nodes dominated by distance at most 2, so we computed a 2-ruling set in the end. Small messages. Finally, observe that every subroutine for Stage II and III works in the CONGEST model. For Stage I, we can use fractional values instead of reals for the ranks using c · log n = O(log n) bits. Then we have no collisions w.h.p. 1 − 1/nc−2 by a union bound. This completes the proof of Theorem 1. Remark. The reason why we require arboricity of O(log log n) for Theorem 1 is that it allows us to solve the shattered components of small size efficiently. If we allowed arboricity of O(poly log n), we would end up with instances of size O(poly log n) and arboricity also O(poly log n), which correspond to general graphs. Thus, solving these components in O(log log n) = O(log N ) rounds seems to be no easier than designing an O(log n) deterministic algorithm for 2-ruling sets on general graphs.

4

Randomized 2-Ruling Set for Graphs of General Arboricity

In this section, we are considering graphs of general arboricity α ≫ log log n. In particular, we will show the following result in this section. 5/8 e Theorem 2. There is an O(log α + log5/3 log n)-round LOCAL algorithm to compute a 2-ruling set in graphs with arboricity α w.h.p.

In Corollary 20 we have already established that we can reduce the max degree to O(poly log n) when arboricity is O(poly log n). Therefore, we will consider the case where α = Ω(poly log n). In this situation, we derive a degree drop down to poly α from Lemma 5. Corollary 24. Let G be a graph with max degree ∆ and arboricity α = Ω(poly log n). There is an O(log log ∆)-round procedure that computes an independent set S such that G \ (S ∪ N2 (S)) has max degree ∆′ ≤ 668 α32 = O(poly(α)) w.h.p. Proof. The statement follows immediately by Lemma 5, since max{(66α4 )8 , log8 n} = 668 α32 , already for α ≥ log n. The procedure is also given by running Algorithm 1 for O(log log ∆) rounds. Finally, we will use sampling techniques by [15] to reduce the degree further and finally show how to compute a 2-ruling set. 18

Lemma 25 (Theorem 1 [15]). Let G be an arbitrary n-vertex graph with maximum degree ∆ and f be a parameter. With high probability, we can compute a vertex-subset S ⊆ V (G) in O(logf ∆) rounds such that ∆(G[S]) = O(f · log n), and every vertex in V is either in S or has a neighbor in S. Lemma 26. Given a graph G = (V, E) with max degree ∆ ≤ O(α32 ) we can compute a 2-ruling set 5/8 5/3 e e in O(log α) + O(log log n) rounds w.h.p. Proof. Let f be a parameter that will be fixed later during this proof. First we run the sparsification procedure of Lemma 25 to obtain a vertex-subset S ⊆ V (G) in O(logf ∆) rounds such that in ∆(G[S]) = O(f ·log n) and every vertex in V is either in S or has a neighbor in S. In order to obtain a 2-ruling set of G, it suffices to compute an MIS on G[S]. We run Ghaffari’s MIS algorithm [32], which computes an MIS in O(log ∆(G[S])) = O(log(f ·log n)) = O(log f )+O(log log n) rounds, such that the remaining graph consists of components of size O(∆(G[S])4 ·log∆ n) = O((f ·log n)4 ·log∆ n). Finally, we invoke the MIS algorithm of [34] to compute an MIS on each of the remaining components 5/3 5/3 5/3 e e e in O(log N ) = O(log ((f · log n)4 · log∆ n)) = O(log f + log5/3 log n). So in total, this requires 5/3 5/3 e e O(logf ∆) + O(log f ) + O(log f ) + O(log log n)   log α 5/3 5/3 e e =O + O(log f ) + O(log log n) log f

rounds, where we used that ∆ ≤ α32 . Finally, choosing f = exp(log3/8 α) we obtain a runtime of   log α 5/3 5/3 e e O + O(log f ) + O(log log n) log f   log α 3/8 5/3 e e =O + O((log α)5/3 ) + O(log log n) log3/8 α 5/8 e = O(log α + log5/3 log n) rounds. Finally, we are ready to prove Theorem 2. Proof of Theorem 2. Consider the following algorithm: Invoke the procedure of Corollary 24/Corollary 20 (they are the same) to compute an independent set S. Now consider the residual graph G′ := G \ (S ∪ N2 (S)). If α = O(poly log n) we know that the max degree of G′ is ∆′ = O(poly log n) after O(log log ∆) rounds by Corollary 20 and thus can invoke the deterministic MIS algorithm of Ghaffari and 5/3 ′ 5/3 e e Grunau [34] to obtain an MIS on the remaining graph in O(log ∆ ) = O(log log n) rounds, 5/3 5/3 e e yielding an overall runtime of O(log log ∆) + O(log log n) = O(log log n). We have already established correctness, independence, and domination for the degree drop, and since the MIS computation is correct, we in fact compute a 2-ruling set. Otherwise, if α = Ω(poly log n), we invoke the procedure of Lemma 26 after the degree drop. Correctness of the Subroutines. After the invocation of the degree drop procedure, the max degree dropped to O(α32 ) w.h.p. by Corollary 24. Thus, we can call the procedure of Lemma 26 to compute a 2-ruling set on the remaining graph. Runtime. Reducing the max degree down to α32 takes O(log log ∆) rounds, by Corollary 24. 5/8 e The computation of the 2-ruling set on the remaining graph take O(log α+log5/3 log n) by Lemma 26. Independence and Domination. In each called procedure, we always compute independent sets and remove each computed independent set and its neighborhood before computing the next 19

independent set, ensuring independence across the two procedures. Before the final computation of a 2-ruling set on the remaining graph, we only removed nodes that are dominated by distance at most 2, thus S ∪ I is a 2-ruling set. 5/3 e For a restricted regime of α Theorem 2 runs in O(log log n) rounds. 5/3 e Corollary 3. There is an O(log log n)-round LOCAL algorithm to compute a 2-ruling set in 8/3 (log log n) graphs with arboricity α ≤ 2 w.h.p. 8/3 5/8 8/3 5/3 e e e Proof. For α ≤ 2(log log n) , we have O(log α) = O((log log n)5/8 ) = O(log log n), so the 5/3 e overall runtime of Theorem 2 is O(log log n).

Remark. In order to make Theorem 2 work in the CONGEST model, one could use one of the recent network decomposition algorithms, e.g., [35, 62] to compute an MIS on the remaining components. This would result in a larger O(poly log log n) term in the final runtime.

5

Massively Parallel 2-Ruling Set

In this section, the words node and machine are interchangeable, since each node is hosted on a unique machine with local space O(nε ) with ε ∈ (0, 1). The algorithm relies on Lemma 13 in order to reduce the maximum degree until every node can gather their poly(log log n)-hop neighborhood and simulate Theorem 2 directly. Gathering neighborhoods is done via graph exponentiation [51], which is a standard tool in MPC. Theorem 4. There is an O(log log log n)-round low-space MPC algorithm that w.h.p. computes a 2-ruling set in graphs with arboricity α ≤ 2poly(log log n) , using O(m + n1+ε ) total space. Proof. By Lemma 13, there exists a constant-round LOCAL algorithm that computes an independent set S on a graph G with arboricity α and maximum degree ∆ ≥ max{(66α4 )8 , log8 n}, such that the maximum degree of G \ {S ∪ N2 (S)} is ∆′ ≤ ∆3/4 . This algorithm can be executed directly in low-space MPC within the same runtime: nodes with degree < nε can execute it locally, and nodes with degree > nε can execute it via an nε -ary broadcast tree, which is straightforward to implement as v only needs to aggregate the minimum real computed by its active neighbors. By applying Lemma 13 O(log log log n) times on the input graph, the remaining graph has maximum degree ∆′ ≤ max{∆1/ poly(log log n) , (66α4 )8 , log8 n} . Now, each node gathers its poly(log log n)-hop neighborhood using graph exponentiation in O(log log log n) rounds. This is feasible, because the size of any such neighborhood is bounded: since ∆ ≤ n and α ≤ 2poly(log log n) , it holds that (∆′ )poly(log log n) ≤ (max{∆1/ poly(log log n) , (66α4 )8 , log8 n})poly(log log n) ≤ (max{n1/ poly(log log n) , 2poly(log log n) , log8 n)})poly(log log n) = max{nε/2 , 2poly(log log n) , 2poly(log log n) } = O(nε/2 ) . The exponent of n can be set to ε/2 by choosing a suitable constant in 1/ poly(log log n), i.e., how many times we execute the degree reduction. Hence, the total number of edges in every poly(log log n)-hop neighborhood is bounded by O(nε ) and the total space of the algorithm is 20

bounded by O(m + n1+ε ). Now, we can execute any poly(log log n)-round LOCAL algorithm in constant time due to the fact that any t-round LOCAL algorithm is simply a function from the ball of radius t around every node v, to an output set. In particular, we can execute Theorem 2 when arboricity α ≤ 2poly(log log n) , since the runtime is 5/8 e O(log α + log5/3 log n) = O(log log α · log5/8 α + log log log n · log5/3 log n)

= O(log log log n · poly(log log n) + log log log n · log5/3 log n) = poly(log log n) , yielding a 2-ruling set for the current graph. Combining this set with the independent sets computed during the degree reduction (repeated application of Lemma 13) gives a 2-ruling set for the input graph by the correctness proof of Theorem 2.

Acknowledgements We thank Lasse Leskelä for helpful discussions on probabilistic arguments for handling dependencies in an earlier version of this work.

21

References [1] Noga Alon, Lásló Babai, and Alon Itai. A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem. Journal of Algorithms, 7(4):567–583, 1986. [2] Sepehr Assadi and Aditi Dudeja. Ruling Sets in Random Order and Adversarial Streams. In the International Symposium on Distributed Computing (DISC), pages 6:1–6:18, 2021. doi: 10.4230/LIPIcs.DISC.2021.6. [3] Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, and Serge A. Plotkin. Network Decomposition and Locality in Distributed Computation. In the Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 364–369, 1989. [4] Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. Lower Bounds for Maximal Matchings and Maximal Independent Sets. In the Proceedings of the Symposium on Foundations of Computer Science (FOCS), 2019. [5] Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. Distributed ∆-coloring plays hide-and-seek. In Proc. 54th ACM Symp. on Theory of Computing (STOC), 2022. [6] Alkida Balliu, Sebastian Brandt, and Dennis Olivetti. Distributed Lower Bounds for Ruling Sets. In the Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 365–376, 2020. doi:10.1109/FOCS46700.2020.00042. [7] Alkida Balliu, Sebastian Brandt, and Dennis Olivetti. Distributed lower bounds for ruling sets. SIAM J. Comput., 51(1):70–115, 2022. URL: https://doi.org/10.1137/20m1381770, doi:10.1137/20M1381770. [8] Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, and Dennis Olivetti. Node and edge averaged complexities of local graph problems. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC’22, page 4–14, New York, NY, USA, 2022. Association for Computing Machinery. doi:10.1145/3519270.3538419. [9] L. Barenboim and M. Elkin. Sublogarithmic distributed mis algorithm for sparse graphs using nash-williams decomposition. Distributed Computing, 22(5):363–379, 2010. doi:10.1007/ s00446-009-0088-2. [10] Leonid Barenboim, Michael Elkin, and Uri Goldenberg. Locally-iterative distributed (δ + 1)coloring and applications. J. ACM, 69(1), December 2021. doi:10.1145/3486625. [11] Leonid Barenboim, Michael Elkin, and Fabian Kuhn. Distributed (δ + 1)-coloring in linear (in δ) time. SIAM Journal on Computing, 43(1):72–95, 2014. arXiv:https://doi.org/10.1137/ 12088848X, doi:10.1137/12088848X. [12] Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The Locality of Distributed Symmetry Breaking. Journal of the ACM, 63(3):20:1–20:45, 2016. [13] Malte Baumecker, Yannic Maus, and Jara Uitto. Nearly-optimal distributed ruling sets for trees and high-girth graphs. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, page 88–98, New York, NY, USA, 2025. Association for Computing Machinery. doi:10.1145/3732772.3733547.

22

[14] Paul Beame, Paraschos Koutris, and Dan Suciu. Communication Steps for Parallel Query Processing. the Journal of the ACM, 64(6), 2017. doi:10.1145/3125644. [15] Tushar Bisht, Kishore Kothapalli, and Sriram Pemmaraju. Brief announcement: Super-fast truling sets. In the Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 379–381, 2014. doi:10.1145/2611462.2611512. [16] Mélanie Cambus, Davin Choo, Havu Miikonen, and Jara Uitto. Massively Parallel Correlation Clustering in Bounded Arboricity Graphs. In Seth Gilbert, editor, 35th International Symposium on Distributed Computing (DISC 2021), volume 209 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1–15:18, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/ 10.4230/LIPIcs.DISC.2021.15, doi:10.4230/LIPIcs.DISC.2021.15. [17] Mélanie Cambus, Fabian Kuhn, Shreyas Pai, and Jara Uitto. Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem. In the International Symposium on Distributed Computing (DISC), pages 11:1–11:12, 2023. doi:10.4230/LIPIcs.DISC.2023.11. [18] Mélanie Cambus, Fabian Kuhn, Shreyas Pai, and Jara Uitto. Time and space optimal massively parallel algorithm for the 2-ruling set problem. In Rotem Oshman, editor, 37th International Symposium on Distributed Computing, DISC 2023, October 10-12, 2023, L’Aquila, Italy, volume 281 of LIPIcs, pages 11:1–11:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. URL: https://doi.org/10.4230/LIPIcs.DISC.2023.11, doi:10.4230/LIPICS.DISC.2023. 11. [19] Chandra Chekuri, Aleksander Bjørn Christiansen, Jacob Holm, Ivor van der Hoog, Kent Quanrud, Eva Rotenberg, and Chris Schwiegelshohn. Adaptive Out-Orientations with Applications, pages 3062–3088. URL: https://epubs.siam.org/doi/abs/10.1137/1.9781611977912.110, arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611977912.110, doi:10.1137/1. 9781611977912.110. [20] Aleksander Bjørn Grodt Christiansen, Krzysztof Nowicki, and Eva Rotenberg. Improved dynamic colouring of sparse graphs. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 1201–1214, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3564246.3585111. [21] Corinna Coupette and Christoph Lenzen. A Breezing Proof of the KMW Bound, pages 184–195. URL: https://epubs.siam.org/doi/abs/10.1137/1.9781611976496.21, arXiv:https:// epubs.siam.org/doi/pdf/10.1137/1.9781611976496.21, doi:10.1137/1.9781611976496. 21. [22] Artur Czumaj, Peter Davies, and Merav Parter. Graph sparsification for derandomizing massively parallel computation with low space. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’20, page 175–185, New York, NY, USA, 2020. Association for Computing Machinery. doi:10.1145/3350755.3400282. [23] Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. Communications of the ACM, pages 107–113, 2008. doi:10.1145/1327452.1327492. [24] Michal Dory, Mohsen Ghaffari, and Saeed Ilchi. Near-optimal distributed dominating set in bounded arboricity graphs. Distributed Computing, 37(4):387–398, May 2023. doi:10.1007/ s00446-023-00447-z. 23

[25] Talya Eden, Saleet Mossel, and Dana Ron. Approximating the Arboricity in Sublinear Time, pages 2404–2425. URL: https://epubs.siam.org/doi/abs/10.1137/1.9781611977073.96, arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611977073.96, doi:10.1137/1. 9781611977073.96. [26] Talya Eden, Dana Ron, and C. Seshadhri. Faster sublinear approximation of the number of k-cliques in low-arboricity graphs, pages 1467–1478. 2020. URL: https://epubs.siam. org/doi/abs/10.1137/1.9781611975994.89, arXiv:https://epubs.siam.org/doi/pdf/10. 1137/1.9781611975994.89, doi:10.1137/1.9781611975994.89. [27] James D. Esary, Frank Proschan, and David W. Walkup. Association of random variables, with applications. The Annals of Mathematical Statistics, 38(5):1466–1474, 1967. doi:10. 1214/aoms/1177698701. [28] Salwa Faour and Fabian Kuhn. Brief Announcement: Faster CONGEST Approximation Algorithms for Maximum Weighted Independent Set in Sparse Graphs. In Dariusz R. Kowalski, editor, 39th International Symposium on Distributed Computing (DISC 2025), volume 356 of Leibniz International Proceedings in Informatics (LIPIcs), pages 54:1–54:7, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/ entities/document/10.4230/LIPIcs.DISC.2025.54, doi:10.4230/LIPIcs.DISC.2025.54. [29] Manuela Fischer, Jeff Giliberti, and Christoph Grunau. Deterministic massively parallel symmetry breaking for sparse graphs. In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’23, page 89–100, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3558481.3591081. [30] Dmitry Gavinsky, Shachar Lovett, Michael Saks, and Srikanth Srinivasan. A tail bound for readk families of functions. Random Structures & Algorithms, 47(1):99–108, 2015. URL: https:// onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20532, arXiv:https://onlinelibrary. wiley.com/doi/pdf/10.1002/rsa.20532, doi:10.1002/rsa.20532. [31] B. Gfeller and E. Vicari. A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs. In the Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 53–60, 2007. [32] Mohsen Ghaffari. An Improved Distributed Algorithm for Maximal Independent Set. In the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 270–277, 2016. [33] Mohsen Ghaffari and Christoph Grunau. Dynamic o(arboricity) coloring in polylogarithmic worst-case time. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, page 1184–1191, New York, NY, USA, 2024. Association for Computing Machinery. doi:10.1145/3618260.3649782. [34] Mohsen Ghaffari and Christoph Grunau. Near-optimal deterministic network decomposition and ruling set, and improved MIS. In the Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 2148–2179, 2024. doi:10.1109/FOCS61266.2024.00007. [35] Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, and Václav Rozhon. Improved distributed network decomposition, hitting sets, and spanners, via derandomization. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACMSIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, 24

pages 2532–2566. SIAM, 2023. URL: https://doi.org/10.1137/1.9781611977554.ch97, doi:10.1137/1.9781611977554.CH97. [36] Mohsen Ghaffari, Christoph Grunau, and Ce Jin. Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing (DISC 2020), volume 179 of Leibniz International Proceedings in Informatics (LIPIcs), pages 34:1–34:18, Dagstuhl, Germany, 2020. Schloss Dagstuhl – LeibnizZentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/ LIPIcs.DISC.2020.34, doi:10.4230/LIPIcs.DISC.2020.34. [37] Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, and Yannic Maus. Improved distributed deltacoloring. In the Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 427–436, 2018. URL: https://dl.acm.org/citation.cfm?id=3212764. [38] Mohsen Ghaffari and Jara Uitto. Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation, pages 1636–1653. 2019. URL: https://epubs.siam.org/doi/abs/10.1137/1.9781611975482.99, arXiv:https://epubs. siam.org/doi/pdf/10.1137/1.9781611975482.99, doi:10.1137/1.9781611975482.99. [39] Jeff Giliberti and Zahra Parsaeian. Massively Parallel Ruling Set Made Deterministic. In Dan Alistarh, editor, 38th International Symposium on Distributed Computing (DISC 2024), volume 319 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1– 29:21, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.29, doi:10. 4230/LIPIcs.DISC.2024.29. [40] M. Henzinger, S. Krinninger, and D. Nanongkai. A deterministic almost-tight dis- tributed algorithm for approximating single-source shortest paths. In Proc. 48th ACM Symp. on Theory of Computing (STOC), pages 489–498, 2016. [41] G. Iliopoulos and N. Balakrishnan. Conditional independence of blocked ordered data. Statistics and Probability Letters, 79(8):1008–1015, 2009. URL: https://www.sciencedirect.com/ science/article/pii/S0167715208005683, doi:10.1016/j.spl.2008.12.005. [42] Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks. ACM SIGOPS Operating Systems Review, pages 59–72, 2007. doi:10.1145/1272996.1273005. [43] Hongyan Ji, Kishore Kothapalli, Sriram V Pemmaraju, and Ajitanshu Singh. Fast deterministic massively parallel ruling sets algorithms. In Proceedings of the 26th International Conference on Distributed Computing and Networking, ICDCN ’25, page 152–160, New York, NY, USA, 2025. Association for Computing Machinery. doi:10.1145/3700838.3700872. [44] Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A Model of Computation for MapReduce. In the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 938–948, 2010. doi:10.1137/1.9781611973075.76. [45] Seri Khoury and Aaron Schild. Breaking barriers for distributed mis by faster degree reduction, 2025. URL: https://arxiv.org/abs/2505.15652, arXiv:2505.15652. [46] Seri Khoury and Aaron Schild. Round elimination via self-reduction: Closing gaps for distributed maximal matching, 2025. URL: https://arxiv.org/abs/2505.15654, arXiv: 2505.15654. 25

[47] Kishore Kothapalli, Shreyas Pai, and Sriram V. Pemmaraju. Sample-And-Gather: Fast Ruling Set Algorithms in the Low-Memory MPC Model. In Nitin Saxena and Sunil Simon, editors, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020), volume 182 of Leibniz International Proceedings in Informatics (LIPIcs), pages 28:1–28:18, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs. FSTTCS.2020.28, doi:10.4230/LIPIcs.FSTTCS.2020.28. [48] Kishore Kothapalli and Sriram Pemmaraju. Super-Fast 3-Ruling Sets. pages 136–147, 2012. doi:10.4230/LIPIcs.FSTTCS.2012.136. [49] F. Kuhn, T. Moscibroda, and R. Wattenhofer. Local computation: Lower and upper bounds. J. of the ACM, 63(2), 2016. [50] Fabian Kuhn, Yannic Maus, and Simon Weidner. Deterministic distributed ruling sets of line graphs. In Zvi Lotker and Boaz Patt-Shamir, editors, Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO 2018, Ma’ale HaHamisha, Israel, June 18-21, 2018, Revised Selected Papers, volume 11085 of Lecture Notes in Computer Science, pages 193–208. Springer, 2018. doi:10.1007/978-3-030-01325-7\_19. [51] Christoph Lenzen and Roger Wattenhofer. Brief Announcement: Exponential Speed-up of Local Algorithms Using Non-Local Communication. In the Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 295–296, 2010. doi:10.1145/1835698. 1835772. [52] Christoph Lenzen and Roger Wattenhofer. Minimum dominating set approximation in graphs of bounded arboricity. In Nancy A. Lynch and Alexander A. Shvartsman, editors, Distributed Computing, pages 510–524, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. [53] Nati Linial. Locality in Distributed Graph Algorithms. 21(1):193–201, 1992.

SIAM Journal on Computing,

[54] M. Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM Journal on Computing, 15:1036–1053, 1986. [55] Yannic Maus. Distributed graph coloring made easy. In Kunal Agrawal and Yossi Azar, editors, SPAA ’21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6-8 July, 2021, pages 362–372. ACM, 2021. doi:10.1145/3409964.3461804. [56] Yannic Maus, Saku Peltonen, and Jara Uitto. Distributed symmetry breaking on power graphs via sparsification. In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC ’23, page 157–167, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3583668.3594579. [57] Adir Morgan, Shay Solomon, and Nicole Wein. Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial. In Seth Gilbert, editor, 35th International Symposium on Distributed Computing (DISC 2021), volume 209 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1– 33:19, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.33, doi:10. 4230/LIPIcs.DISC.2021.33. 26

[58] Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Talal Riaz, and Peter Robinson. Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets. In Andréa Richa, editor, 31st International Symposium on Distributed Computing (DISC 2017), volume 91 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1– 38:16, Dagstuhl, Germany, 2017. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.38, doi:10. 4230/LIPIcs.DISC.2017.38. [59] Shreyas Pai and Sriram V. Pemmaraju. Brief Announcement: Deterministic Massively Parallel Algorithms for Ruling Sets. In the Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 366–368, 2022. doi:10.1145/3519270.3538472. [60] David Peleg. Distributed computing: A locality-sensitive approach. 1987. URL: https: //api.semanticscholar.org/CorpusID:58843423. [61] Sriram Pemmaraju and Talal Riaz. Using Read-k Inequalities to Analyze a Distributed MIS Algorithm. In Panagiota Fatourou, Ernesto Jiménez, and Fernando Pedone, editors, 20th International Conference on Principles of Distributed Systems (OPODIS 2016), volume 70 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:17, Dagstuhl, Germany, 2017. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https: //drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.9, doi:10.4230/ LIPIcs.OPODIS.2016.9. [62] Václav Rozhoň and Mohsen Ghaffari. Polylogarithmic-time Deterministic Network Decomposition and Distributed Derandomization. In the Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), pages 350–363, 2020. [63] Johannes Schneider, Michael Elkin, and Roger Wattenhofer. Symmetry breaking depending on the chromatic number or the neighborhood growth. Theoretical Computer Science, 509:40–50, 2013. doi:10.1016/j.tcs.2012.09.004. [64] Johannes Schneider, Michael Elkin, and Roger Wattenhofer. Symmetry breaking depending on the chromatic number or the neighborhood growth. Theor. Comput. Sci., 509:40–50, 2013. doi:10.1016/j.tcs.2012.09.004. [65] Johannes Schneider and Roger Wattenhofer. A new technique for distributed symmetry breaking. In the Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 257–266, 2010. doi:10.1145/1835698.1835760. [66] Tom White. Hadoop: The Definitive Guide. O’Reilly Media, Inc., 2009. [67] Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. Spark: Cluster Computing with Working Sets. In the Proceedings of the USENIX Conference on Hot Topics in Cloud Computing (HotCloud), page 10, 2010. doi:10.5555/1863103.1863113. [68] Yufei Zhao. Probabilistic methods in combinatorics: Lecture 15, correlation inequalities. MIT OpenCourseWare, 18.226 Probabilistic Methods in Combinatorics, 2022. Accessed: 2026-01-06. URL: https://ocw.mit.edu/courses/ 18-226-probabilistic-methods-in-combinatorics-fall-2022/resources/mit18_226_ f22_lec15_pdf/.

27

A

Extended Related Work Domination β

Running Time √ Ω(min{log ∆, log n}) q Ω(min{ logloglogn n , logloglog∆∆ })

log ∆ Ω(min{ β log log ∆ , log∆ log n}) q log log n Ω( β log log log n )

β ≤ ϵ · MR2 (∆, n) q β ≤ ϵ · logloglogloglogn n

Ω(min{β∆1/β , log∆ log n})

[46] [8]

Trees

[45]

Girth at least 7 Arboricity α √

Arboricity ≤ 2

[12]+ [32]

log n

[7] General Graphs [5]

log log n Ω( β log log log n ) √ O( log n)

[15]+ [32]

O(log log n)

Trees

5/3 e O(log log n)



β=2

Line Graphs of trees

[32]

∆ O( loglog log∗ ∆ + poly log log n) √ O(log α + log n) √ O( log n)

β ≤ c · MR1 (∆, n) q β ≤ c · 3 logloglogloglogn n

Citation

General Graphs

O(log ∆) + O(poly log log n) q n O( loglog log∗ n )

β = 1 (MIS)

Graph Class

O log1/4 ∆ + log α + poly log log n   O log1/4 ∆ + poly log log n

[13]

Girth at least 7 

Arboricity α

[12]+ [15]+ [32]

Arboricity O(1)

O(log log n)

Arboricity ≤ O(log log n)

Theorem 1

5/3 e O(log5/8 α) + O(log log n)

Arboricity α

Theorem 2

5/3 e O(log log n)

8/3

Arboricity ≤ 2(log log n)

Corollary 3

β=3

O(log3 log n)

Arboricity O(1)

[48]

β = O(log log log n)

e O(log log n)

Girth at least 7

[13]

β = O(log log n)

O(log log n)

General Graphs

[64]+ [31]

β≥2

O(β · log1/β ∆) + poly log log n

General Graphs

[15] + [32]

q Table 1: Randomized Ruling Sets. Define MR1 (∆, n) := min{ logloglog∆∆ , log∆ log n} and MR2 (∆, n) := min{log ∆, log∆ log n}. All algorithms are randomized, and lower bounds hold for randomized algorithms.

28

Domination β

β = 1 (MIS)

Running Time

Graph Class

Citation

5/3 e O(log n)

General Graphs

[34]

O( logloglogn n ) √ O(α log n + α · log α)

Arboricity of O(log1/2−δ n) √ Arboricity of Ω( log n)

[9]

O(log n + α)

Arboricity α

[9]+ [50] β=2

Theorem 22 β = O(1)

O(∆2/(β+2) + log∗ n)

1 (∆, n) β ≤ c · MD q β ≤ c · 3 logloglogn n

log ∆ Ω(min{ β log log ∆ , log∆ n}) q log n Ω( β log log n )

2 (∆, n) β ≤ ϵ · MD q β ≤ ϵ · logloglogn n

Ω(min{β∆1/β , log∆ n})

β = O(log log n)

e O(log n)

[34]

β = O(log n)

O(log n)

[3]

General Graphs

[55] [7]

General Graphs

[5]

log n Ω( β log log n )

q log ∆ 1 (∆, n) := min{ 2 := Table 2: Deterministic Ruling Sets. MD log log ∆ , log∆ n} and MD (∆, n) min{log ∆, log∆ n}. All algorithms are deterministic, and lower bounds hold for deterministic algorithms. For completeness, we show how to combine known results of [15], [12] and [32] to obtain a 2-ruling set algorithm that is not explicitly stated in the literature. Theorem 27. There is an O(log1/4 ∆ + log α + poly log log n) round LOCAL algorithm to compute a 2-ruling set in graphs with arboricity α w.h.p. Proof. Observe if exp(log1/4 ∆) ≤ poly log n, we can compute a 2-ruling set in O(poly log log n) rounds by [32]. Thus, we assume that exp(log1/4 ∆) ≥ poly log n. First, we use [12, Theorem 7.2] to compute an independent set M with t = O(exp(log3/4 ∆) such that the residual graph 1/4 G′ = G[V (G)\(M ∪N (M ))] has maximum degree at most O(tα) in O(log√ ∆) rounds. t ∆) = O(log Secondly, we apply the sampling result Lemma 25 by √ [15] with f = exp( log n) to sample a subset S ⊆ V (G′ ) in O(logf tα) = O(logf t + logf α) = O( log ∆/ log1/4 ∆ + log α) = O(log1/4 ∆ + log α) rounds such that ∆(G′ [S]) = O(f · log n), and every vertex in V is either in S or has a neighbor in S. To compute a 2-ruling set of G, it suffices to compute an MIS of G′ [S]. For that, we apply [12, Theorem 7.2] a second time with√t′ = exp(log1/4 ∆), to compute an independent set MS of S in O(logt′ (f log n)) = O(log(exp( log ∆) log n)/ log1/4 ∆) = O(log1/4 ∆ + poly log log n) rounds e := G′ [S \ (MS ∪ N (MS ))] has maximum degree at most O(t′ α). such that the residual graph G e using Ghaffaris MIS algorithm [32] in O(log t′ α) + (poly log log) = Finally, we compute an MIS on G 1/4 O(log ∆ + log α + poly log log n) rounds. Overall, we compute a 2-ruling set in O(log1/4 ∆ + log α + poly log log n). 29

If the arboricity is constant, we immediately obtain the following. Corollary 28. There is an O(log1/4 ∆ + poly log log n) round LOCAL algorithm to compute a 2ruling set in graphs with arboricity α = O(1) w.h.p.

B

Example: Successful Nodes are Correlated

Consider the graph in Figure 3. The set M = {u, v} is independent. Let r(u), r(v), r(x) be mutually independent random variables, each uniformly distributed on [0, 1]. u

v

x Figure 3: A three-vertex example with independent candidate set M = {u, v}. Although u and v are non-adjacent, conditioning on both candidates being successful, i.e., on r(u) < r(x) and r(v) < r(x), creates correlation between the ranks r(u) and r(v). The event that both vertices in M are successful is A = {r(u) < r(x), r(v) < r(x)}. We show that r(u) and r(v) are not independent after conditioning on A. For fixed t ∈ [0, 1], conditioning on r(x) = t gives P[A | r(x) = t] = P[r(u) < t, r(v) < t] = P[r(u) < t]P[r(v) < t] = t2 , since r(u) and r(v) are independent uniform random variables on [0, 1]. Note that the density function of r(x) is given by fr(x) (t) = 1 for 0 ≤ t ≤ 1, thus by the law of total probability, Z 1 Z 1 1 P[A] = P[A | r(x) = t]fr(x) (t) dt = t2 dt = . 3 0 0 Using Bayes’ rule for densities, the conditional density of r(x) given A is fr(x)|A (t) =

P[A | r(x) = t]fr(x) (t) t2 = = 3t2 , P[A] 1/3

0 ≤ t ≤ 1.

Conditioned on r(x) = t and on A, the variables r(u) and r(v) are independent and uniformly distributed on [0, t], see [41]. Hence t E[r(u) | r(x) = t, A] = . 2 By the law of total expectation, Z 1 Z 1 Z 3 1 3 t 3 2 E[r(u) | A] = E[r(u) | r(x) = t, A] fr(x)|A (t) = · 3t dt = t dt = . 2 0 8 0 0 2 By symmetry, E[r(v) | A] = 38 . Again, since conditioned on r(x) = t and A, the variables r(u) and r(v) are independent uniforms on [0, t], we get E[r(u)r(v) | r(x) = t, A] = E[r(u) | r(x) = t, A] E[r(v) | r(x) = t, A] = 30

t2 . 4

By the law of total expectation we obtain Z 1 2 Z 1 Z t 3 3 1 4 2 E[r(u)r(v) | r(x) = t, A] fr(x)|A (t) dt = E[r(u)r(v) | A] = t dt = . · 3t dt = 4 0 20 0 4 0 Therefore, 9 3 > = E[r(u) | A]E[r(v) | A]. 20 64 This implies that the conditional ranks are not independent. In fact, r(v) and r(u) are positively correlated after conditioning on M being successful, E[r(u)r(v) | A] =

Cov(r(u), r(v) | A) =

C

3 9 3 − = > 0. 20 64 320

Deferred Proofs

First we state the theorems from [30] we use to derive Theorem 11 and Theorem 12. Theorem 29 (Theorem 1.1). [30] Let Y1 , . . . , Ym P be a family of read-k indicator random variables m 1 Pm := p and Y with Pr[Yi = 1] = pi . Let p := m i=1 Yi . Then for any ε > 0, i=1 i

Here D(q||p) := q log

  q p

Pr[Y ≤ (p − ε)m] ≤ exp(−D(p − ε||p) · m/k).   1−q + (1 − q) log 1−p is the Kullback-Leibler divergence.

Theorem 30 (Theorem 1.2). [30] Let Y1 , . . . , Ym be a family of read-k indicator random variables with Pr[Yi = 1] ≤ p. Then Pr[Y1 = · · · = Ym = 1] = pm/k . P Proof of Theorem 11. Let µ := E[Y ] = m i=1 pi = mp. If p = 0, then µ = 0 and the claimed bound is trivial. Moreover, if δ > 1, then (1 − δ)µ < 0 whenever µ > 0, and hence the event {Y ≤ (1 − δ)µ} is empty. Thus, it suffices to consider 0 < δ ≤ 1 and p > 0. Set ε := δp. Then (p − ε)m = (1 − δ)pm = (1 − δ)µ. Applying the lower-tail bound of [30, Theorem 1.1] gives Pr[Y ≤ (1 − δ)µ] ≤ exp (−D((1 − δ)p||p) · m/k) . It remains to bound the binary relative entropy. Writing q = (1 − δ)p, we have  
1 − (1 − δ)p D(q∥p) = (1 − δ)p log(1 − δ) + 1 − (1 − δ)p log 1−p  
δp = (1 − δ)p log(1 − δ) + 1 − p + δp log 1 + . 1−p Using log(1 + x) ≥ x/(1 + x) for x ≥ 0, the second term is at least δp. Therefore
D((1 − δ)p ∥ p) ≥ p (1 − δ) log(1 − δ) + δ . 2

2

Finally, for 0 ≤ δ ≤ 1,we have (1 − δ) log(1 − δ) + δ ≥ δ2 . Indeed, if h(δ) := (1 − δ) log(1 − δ) + δ − δ2 , 2 then h(0) = 0 and h′ (δ) = − log(1 − δ) − δ ≥ 0. Consequently, D((1 − δ)p ∥ p) ≥ δ 2p . Substituting this into the preceding tail bound and using mp = µ yields  2   2  δ mp δ E[Y ] Pr[Y ≤ (1 − δ)E[Y ]] ≤ exp − = exp − . 2k 2k

31

Proof of Theorem 12. Let pi := Pr[Yi = 1], so that pi ≤ p for every i ∈ [m]. If p = 1, the claimed inequality is immediate. Assume henceforth that p < 1. For every i ∈ [m], introduce an indicator random variable Zi , independent of all random variables defining the read-k family and independent of all other Zj , such that Pr[Zi = 1] =

p − pi . 1 − pi

This quantity lies in [0, 1] because pi ≤ p < 1. Define Yei := Yi ∨ Zi . i e e Then Pr[Yei = 1] = pi + (1 − pi ) Pr[Zi = 1] = pi + (1 − pi ) p−p 1−pi = p. Moreover, Y1 , . . . , Ym is again a read-k family: every original underlying random variable is read by at most k of the functions, and the newly introduced variable Zi is read only by Yei . Since Yi ≤ Yei for every i, we have

{Y1 = · · · = Ym = 1} ⊆ {Ye1 = · · · = Yem = 1}. Applying [30, Theorem 1.2] to the read-k family Ye1 , . . . , Yem , whose marginal probabilities are all equal to p, gives Pr[Y1 = · · · = Ym = 1] ≤ Pr[Ye1 = · · · = Yem = 1] ≤ pm/k .

D

Probabilistic Theorems

We restate some definitions and results that are contained in [27] and are rewritten in a more modern way in [68] that we use in the proof of Lemma 16. For mutually independent random variables X1 , . . . , Xn , each on a linear ordered set let X = (Xi )i∈[n] . We say that a function f (X) is non-decreasing if f (X) ≤ f (X ′ ) whenever X ≤ X ′ coordinate-wise, i.e., Xi ≤ Xi′ for 1 ≤ i ≤ n. Theorem 31. [27, Definition 1.1, Theorem 2.1] For independent random variables X1 , . . . , Xn and X = (Xi )i∈[n] we have Cov(f (X), g(X)) ≥ 0 for all non decreasing functions f and g for which E[f (X)], E[g(X)], E[f (X)g(X)] exist.

32