Approximating Minimum Dominating Set with Few Awake Rounds

Approximating Minimum Dominating Set with Few Awake Rounds Hongyan Ji∗1 , Shreyas Pai†2 , and Sriram V. Pemmaraju‡1 1

arXiv:2608.19096v1 [cs.DC] 19 Aug 2026

2

Department of Computer Science, University of Iowa, Iowa City, IA, USA Department of Computer Science and Engineering, IIT Madras, Chennai, India

Abstract We study the Minimum Dominating Set (MDS) problem in the sleeping Congest model (Chatterjee, Gmyr, and Pandurangan, PODC 2020), a generalization of the standard Congest model, in which a node may sleep in some rounds and can only compute, send messages, or receive messages when it is awake. The awake complexity of an algorithm in this model is the worst case number (over all inputs and all nodes) of rounds a node is awake for during the execution of the algorithm. While there are several O(log ∆)-approximation algorithms (in expectation) for MDS that run in O(log2 ∆) rounds, all of these have Ω(log2 ∆) awake complexity. Whether this awake complexity can be improved is the question that drives our work. We present the first O(log ∆)-approximation algorithm for MDS with o(log2 ∆) awake complexity; our algorithm runs in O(log2 ∆) rounds with Õ(log ∆) awake complexity. We can reduce the awake complexity further, but at the cost of approximation: we present, for any 1 < α ≤ ∆, an algorithm in the sleeping Congest model that computes an O(α log ∆)approximate dominating set in expectation in Õ(log ∆·logα ∆) rounds with Õ(logα ∆) awake complexity. Our results depend on a generalization of the Congest model SetCover algorithm of Grunau, Mitrović, Rubinfeld, and Vakilian (SODA 2020) that we develop. This generalization computes an O(p · q · logp ∆)-approximate dominating set in O(logp ∆ · logq ∆) rounds for parameters 1 < p, q ≤ ∆. Our sleeping Congest algorithms apply a variety of techniques including sampling-based estimation and scheduling using virtual binary trees to the aforementioned 2-parameter SetCover algorithm.

CCS Concepts: Theory of computation Distributed algorithms; Theory of computation Approximation algorithms analysis Keywords: minimum dominating set, sleeping CONGEST, awake complexity, distributed approximation

1

Introduction

Given an undirected graph G = (V, E), a dominating set of G is a subset D ⊆ V such that every vertex in V \ D has a neighbor in D. The Minimum Dominating Set (MDS) problem is to find a dominating set of smallest size. MDS is a classical NP-complete combinatorial optimization problem and the natural, greedy sequential algorithm provides a (1+ln ∆)-approximation [18, 9]. This algorithm is essentially optimal since, via the standard reduction from SetCover to MDS, there can be no c ln n-approximation to MDS for any constant c < 1 unless P = N P [10]. In the ∗ hongyan-ji@uiowa.edu; https://orcid.org/0000-0002-6610-844X. Supported in part by the National Science Foundation (NSF) grants CCF-2402835 and CCF-2617608. † shreyas@cse.iitm.ac.in; https://orcid.org/0000-0003-2409-7807. ‡ sriram-pemmaraju@uiowa.edu; https://orcid.org/0000-0002-0834-3476. Supported in part by the National Science Foundation (NSF) grants CCF-2402835 and CCF-2617608.

1

distributed setting, MDS has been studied extensively in the standard Congest and Local models. In the Congest model, Jia, Rajaraman, and Suel [17] gave a randomized algorithm running in O(log n log ∆) rounds with high probability, providing an O(log ∆)-approximation (in expectation) and an O(log n)-approximation (with high probability). Censor-Hillel and Dory [5] subsequently strengthened this result to a high-probability O(log ∆)-approximation in O(log n log ∆) rounds in the Congest model. Kuhn, Moscibroda, and Wattenhofer [19] present a similar result via solving covering-packing linear programs (LPs). As far as we know, for general graph, no algorithm achieving an O(log ∆)-approximation in o(log2 ∆) rounds is currently known in the Congest model. However, in the Local model (i.e., using messages of unbounded size), Kuhn, Moscibroda, and Wattenhofer [19, 20] show how to compute an expected O(log ∆)-approximation in O(log n) rounds, with high probability. The Local and the Congest models charge every node for every round of execution, whether or not the node is actively communicating in that round. In many real-world distributed systems—sensor networks, ad-hoc wireless networks, and other battery-powered settings—energy, not time, is the scarce resource: an idle but awake node consumes nearly as much energy as one that is transmitting or receiving, while a sleeping node (with its radio off) consumes essentially none. This observation motivated a substantial line of work on energy-efficient radio protocols [7, 6], and was carried over to the message-passing distributed-computing setting by Chatterjee, Gmyr, and Pandurangan [8], who introduced the sleeping model: a generalization of the standard Congest and Local models in which a node may sleep in any round, and only the rounds in which it is awake count toward its individual awake complexity (also called energy complexity). Crucially, the awake complexity of an algorithm can be substantially smaller than its round complexity. A growing body of recent work designs algorithms in the sleeping Congest and Local models with low awake complexity for graph problems that are related to MDS. For the maximal independent set (MIS) problem in the sleeping Congest model, Chatterjee, Gmyr, and Pandurangan [8] gave a randomized algorithm that computes an MIS with high probability, has expected O(1) node-averaged awake complexity, and with high probability, has O(log n) worstcase awake complexity and O(log3.41 n) round complexity. Dufoulon, Moses Jr., and Pandurangan [11] subsequently improved the worst-case awake complexity to O(log log n) rounds, though the algorithm uses O(log7 n log log n) rounds. Ghaffari and Portmann [13] reduced the round complexity to O(log2 n), while maintaining the worst-case awake complexity at O(log log n) rounds. For maximum matching and minimum vertex cover, Ghaffari and Portmann [12] presented O(log n)-round algorithms in the sleeping Congest model with O(1) node-averaged awake complexity for (1 + ε)-approximate maximum matching and (2 + ε)-approximate minimum vertex cover, for every constant ε > 0. O-LOCAL problems refer to the class of problems that can be solved using any acyclic orientation of the edges, by choosing a solution for each vertex after all vertices reachable from it have computed their solution, and as a function of these solutions. Problems such as MIS and (∆+1)-coloring are O-LOCAL problems. For this class of problems, Barenboim and Maimon [3] gave a deterministic algorithm using O(log ∆ + log∗ n) awake rounds and O(∆2 + log∗ n) rounds in the sleeping Local model. Balliu et al. [2] subsequently showed that every √ O-LOCAL problem can be solved √ deterministically in the sleeping Local model using O( log n log∗ n) awake rounds and O(n5 log n) rounds. MDS is not O-LOCAL and so this general result does not have any direct implications for MDS. For MDS, prior sleeping-model work has been confined to special graph classes arising in wireless networks [22] (see Section 1.3 for an update). As mentioned earlier, the state of the art for MDS in the Congest model is an O(log ∆)-approximation algorithm running in O(log2 ∆) rounds. No faster algorithms are known to provide this approximation guarantee. Given this situation, our work is motivated by the following question.

2

Core Question: Can we design an O(log ∆)-approximation for MDS with o(log2 ∆) awake complexity? A natural generalization of this question is whether it is possible to design algorithms that exhibit a tradeoff between approximation quality and awake complexity, specifically allowing the approximation guarantee to worsen in exchange for further improvement in the awake complexity. Our work in this paper is motivated by this “approximation versus energy” tradeoff question as well.

1.1

The Sleeping Model

We work in the synchronous sleeping model of Chatterjee, Gmyr, and Pandurangan [8], which generalizes the standard Congest model by allowing each node to sleep in any round. The algorithm proceeds in synchronous rounds, and in each round every node is either awake or asleep. An awake node performs local computation and may send messages, of size O(log n) bits, to each of its neighbors. A sleeping node performs no computation, sends no messages, and receives no messages. Thus any message sent to a sleeping node is lost. A sleeping node wakes only at a round it previously scheduled for its wake up; it cannot be woken by a neighbor. We let ∆ denote the maximum closed-neighborhood size (equivalently, 1 plus the maximum degree) and assume that ∆ ≥ 2 (otherwise the MDS problem becomes trivial). We assume that each node initially knows n and ∆, and that on waking up a node knows the current round number, presumably by accessing the global clock. A node v that is awake in a round i, schedules its next awake round j > i, before completing round i. Node v then sleeps during rounds i + 1, i + 2, . . . , j − 1 and wakes up in round j with no help from any other nodes. The round complexity of an algorithm is the number of rounds until every node terminates. The awake complexity of an algorithm is maxv∈V Av , where Av is the number of rounds in which v is awake.

1.2

Our results

We present two main results on MDS approximation in the sleeping Congest model. Our first result, affirmatively answers our core question. Theorem 1 (Informal). There is an algorithm in the sleeping Congest model that computes an O(log ∆)-approximate dominating set in expectation in O(log2 ∆) rounds and Õ(log ∆)1 awake complexity. We obtain this result by designing a sleeping version of the SetCover algorithm of Grunau, Mitrović, Rubinfeld, and Vakilian [16]. For MDS, this algorithm yields an O(log ∆)-approximation (in expectation) in O(log2 ∆) rounds. We note that even though in our sleeping version, nodes spend large portions of the algorithm asleep, this does not result in the slowing down of the algorithm, which still runs in O(log2 ∆) rounds. As will become clear from the precise version of ε this theorem (Theorem 10 in Section 2), for moderately high values of ∆, i.e., ∆ ≥ 2log n for any constant ε ∈ (0, 1), the awake complexity bound simplifies to O(log ∆), losing the multiplicative O(poly(log log n)) terms. This also means that O(log n) is a simple upper bound on the awake complexity of the algorithm promised by Theorem 1. Our second result establishes a smooth tradeoff between the approximation factor and awake complexity of MDS algorithms, specifically showing there are MDS approximation algorithms with o(log ∆) awake complexity, provided we permit weaker approximation guarantees. 1 All round complexity and awake complexity measures in this paper are in O(poly(log ∆)). We use the Õ(·) notation for these measures in this paper to hide O(poly(log log n)) terms.

3

Theorem 2 (Informal). For any 1 < α ≤ ∆, there is an algorithm in the sleeping Congest model that computes an O(α log ∆)-approximate dominating set in expectation in Õ(log ∆· logα ∆) rounds and Õ(logα ∆) awake complexity. This result (see Theorem 15 for the precise version of this theorem) allows us to obtain ε sublogarithmic awake complexities, such as Õ(1), for α = ∆ε and Õ(log1−ε ∆), for α = 2log ∆ , for constant ε ∈ (0, 1). We use a variety of techniques to obtain our results—see Section 1.4 below for an overview. One new result that we obtain, that may be of independent interest, is the following natural, 2-parameter Congest model generalization of the SetCover algorithm of Grunau, Mitrović, Rubinfeld, and Vakilian [16]. Theorem 3. For every 1 < p, q ≤ ∆, there is a randomized Congest algorithm that returns an O(p · q · logp ∆)-approximate dominating set in expectation, in O(logp ∆ · logq ∆) rounds. By setting p = q = 2 we recover the O(log ∆)-approximation in O(log2 ∆) rounds due to Grunau, Mitrović, Rubinfeld, and Vakilian [16]. We use Theorem 3, with different settings of p and q to obtain both Theorems 1 and 2.

1.3

Independent results

While our paper was being reviewed, the paper of Ghaffari and Yeoh [15] was published in SPAA 2 e 2026. This paper gives a O(log n)-approximation Congest algorithm with high probability for 2 minimum set cover in O(log n) rounds, with O(log log n) awake complexity for element nodes and O(log n log log n) awake complexity for set nodes. Since MDS is a special case of set cover, 2 e their result also implies an O(log n)-approximate MDS algorithm with O(log n log log n) awake complexity. Interestingly, the starting point of the Ghaffari and Yeoh [15] energy-efficient algorithm is the same, BaseMDS algorithm (Algorithm 1) [16] that we use. The paper also presents improved results on the worst case awake complexity for maximum matching and minimum vertex cover approximation.

1.4

Challenges and ideas

The BaseMDS algorithm. Our algorithmic starting point is a parallel emulation of the classical sequential greedy MDS algorithm, which repeatedly picks the vertex v whose closed neighborhood N + (v) (= {v} ∪ N (v)) contains the largest number of still-undominated vertices and adds v to the dominating set D. This achieves a (1 + ln ∆)-approximation [18, 9]. A direct distributed parallelization is hopeless: the algorithm seems inherently sequential and identifying the global maximum-residual-degree vertex would by itself cost Ω(diam(G)) rounds. Here “residual degree” of a node v refers to the number of as-yet-undominated neighbors of node v (including v if it is not dominated). The standard relaxation, going back to early parallel SetCover algorithms [4, 25] and also used in the algorithm of Grunau, Mitrović, Rubinfeld, and Vakilian [16] that we build on, is to replace “the vertex of maximum residual degree” by “all vertices whose residual degree is high enough.” Concretely, we identify geometrically decreasing residual degree thresholds Ti = ∆/2i , 1 ≤ i ≤ ⌈log ∆⌉ and let the algorithm proceed in ⌈log ∆⌉ stages. At the start of stage i, any vertex whose residual degree is at least Ti is considered a candidate for Stage i. All stage i candidates would like to join D in stage i, but a stage may have many candidates whose closed neighborhoods overlap, and adding all of them simultaneously could lead to a very poor approximation. So we need to run some type of symmetry breaking algorithm in each stage to prune the candidates in that stage. The symmetry breaking process needs to ensure that the selected Stage i candidates satisfy two properties: (i) every as-yet-undominated node covered by some Stage i candidate is covered by some selected stage i candidate and (ii) no asyet-undominated node is “over covered” by the selected stage i candidates. Several approaches 4

Algorithm 1 BaseMDS Require: maximum closed-neighborhood size ∆ known to all nodes. 1: D ← ∅. 2: for i = 1, 2, . . . , ⌈log ∆⌉ do 3: for k = 1, 2, . . . , ⌈log ∆⌉ do 4: for each node v in parallel do 5: dki (v) ← |{u ∈ N + (v) : u ∈ / N + (D)}|. 6: if v ∈ / D and dki (v) ≥ Ti then 7: add v to D with probability pk = min{1, 2k /∆}.

▷ stages ▷ iterations

▷ Ti = ∆/2i

8: return D.

have been proposed for symmetry breaking in this context (e.g., randomized pruning based on median support [17, 24], random voting based scheme in [5]). The symmetry breaking used in the algorithm of Grunau, Mitrović, Rubinfeld, and Vakilian [16] is particularly simple. In each stage, we simply run ⌈log ∆⌉ iterations and in iteration k, every still-eligible candidate joins D independently with probability pk = min{1, 2k /∆}. The fact that the probabilities start off very small, at 2/∆, and grow geometrically in each iteration ensures that each as-yet-undominated node is dominated by only O(1) selected candidates in expectation. This is a key result in the analysis of [16]. We refer to this algorithm from [16] as BaseMDS. Algorithm 1 presents the pseudocode. The BaseMDS algorithm computes an O(log ∆)-approximate dominating set in expectation in O(log2 ∆) Congest rounds [16]. We prove our main results described earlier by designing an energy efficient version of BaseMDS (Algorithm 1) (and its generalization Algorithm 3). In doing this, we encountered some significant challenges that we discuss below. Challenge 1: Nodes continually need to monitor residual degrees. The most basic challenge in designing a sleeping version of BaseMDS is that nodes need to continually monitor their dynamically decreasing residual degrees so that they can attempt to join D when their residual degree exceeds a threshold Ti . While the thresholds Ti are fixed ahead of time, it is hard to anticipate how the residual degrees will fall from one iteration to the next. Specifically, each node v in BaseMDS needs to monitor its residual degree at the start of each stage to determine if it is a candidate for that stage. If a node v is a stage i candidate, it needs to continually monitor its residual degree during the iterations in stage i in order to participate in symmetry breaking. It is not difficult to construct worst-case examples in which a node becomes a candidate in most stages and therefore has to monitor its degree for Θ(log2 ∆) iterations over the entire algorithm. Our first conceptual contribution is showing that if a node v is a candidate in stage i, it only needs to wake up in 1 iteration during the stage to participate in symmetry breaking. Furthermore, it can identify its wake-up iteration at the start of the stage in order to schedule its wake-up. Challenge 2: Nodes continually need to share their status with neighbors. Overcoming Challenge 1 immediately implies that each node needs to be awake as a candidate for O(log ∆) rounds, i.e., O(1) rounds per stage. However, whenever a node wakes up to monitor its residual degree, its neighbors also need to be awake in order to provide up-to-date information on their status (dominated or not). This means that nodes may have to be continually awake to respond to queries from neighbors about their status. Our second conceptual contribution deals with this challenge. To each node u, we assign a single randomly chosen stage-iteration pair over the entire algorithm, and during this pair, node u acts as an estimator, providing status updates to any neighbor querying it. This essentially means that for any node v that needs to compute its residual degree in an iteration, the estimators in v’s neighborhood that are awake during that iteration form a random neighborhood sample. We show in Lemma 6 that as long as the 5

threshold Ti = Ω(poly(log n)), this energy-saving sampling scheme is enough for node v to obtain an accurate estimate of its residual degree. Challenge 3: Coordinating dominators and estimators. Our next challenge arises from the fact that nodes that wake up in just one iteration, to act as estimators, will have no clue about their status (dominated or not). Specifically, they would not have heard from any neighbors who joined D in a prior iteration because they were not awake at that time. So we need to somehow coordinate the wake up schedule of a node w that wakes up as an estimator in iteration j and the wake up schedule of a neighbor w′ ∈ N (w) that joins D in an earlier iteration i < j. Schedules obtained by using a virtual binary tree (VBT) [13, 3, 1] have been proposed to solve precisely this coordination challenge. Continuing our example, let S = {1, 2, . . . , ⌈log ∆⌉} denote the iteration numbers in a stage of BaseMDS. The node w, that is scheduled to wake up in iteration j uses a VBT to compute a set Sj ⊆ S of iterations and similarly the node w′ ∈ N (w) that joins D in iteration i uses a VBT to compute a set Si ⊆ S of iterations. The VBT-based schedule has the property that (i) the sets are small, i.e., |Si |, |Sj | = O(log |S|) and (ii) there is an iteration ℓ ∈ Si ∩ Sj such that i ≤ ℓ ≤ j. See Lemma 4 for a precise statement of the VBT schedule property. This implies if w is awake for all iterations in {j} ∪ Sj and w′ is awake for all iterations in {i} ∪ Si then there is a common iteration ℓ, i ≤ ℓ ≤ j, during which both w and w′ are awake and during this iteration w can learn about w′ and can update its status so that it can correctly answer status queries in iteration j. The fact that the sizes |Si |, |Sj | ∈ O(log log ∆) implies that all of this can be achieved with only an O(log log ∆) overhead in the awake complexity of nodes. Challenge 4: Reducing awake complexity to o(log ∆). Given that each node wakes up a constant number of times per stage to monitor its degree and there are Θ(log ∆) stages, how do we reduce the awake complexity of the algorithm to o(log ∆)? Our approach to doing this is by reducing the number of stages in the algorithm. Specifically, we generalize the BaseMDS algorithm by allowing the degree thresholds to fall by a factor p > 1 in each stage, rather than by a factor 2. Using a parameterized degree threshold sequence Ti = ∆/pi implies Θ(logp ∆) stages and using values of p > 2 reduces the number of stages, while incurring a corresponding loss in approximation factor. In fact, we also parameterize the sampling probability sequence k k that define iterations, using min{1, q∆ }, instead of min{1, 2∆ }, for a parameter q > 1. The resulting algorithm is a natural 2-parameter Congest model generalization of BaseMDS that we call (p, q)-MDS. We show, by generalizing the analysis of Grunau, Mitrović, Rubinfeld, and Vakilian [16], that this algorithm yields a O(p·q·logp ∆)-approximation to MDS (in expectation), while running in O(logp ∆ · logq ∆) rounds. The sleeping implementation of this generalization underlies Theorems 1 and 2. Interestingly, we use it to obtain slight improvements in Theorem 1 as well. There have been several papers [21, 19, 24] on approximation versus rounds tradeoff for MDS in the Congest model. For example, Kuhn and Wattenhofer [21] gave an O(k∆2/k log ∆)approximation in O(k 2 ) rounds for each integer k ≥ 1. Our (p, q)-MDS algorithm gives a tradeoff of the same general form: setting p = q = ∆1/k in Theorem 3 gives an O(k∆2/k )-approximation in expectation in O(k 2 ) rounds. We do not use (p, q)-MDS to improve the best known round– approximation tradeoff. Rather, its staged threshold structure is particularly amenable to our sleeping implementation, allowing the same parameters to control the awake complexity as well.

1.5

Other related work

Global problems such as Minimum Spanning Tree (MST) and Single Source Shortest Path (SSSP) have also been studied in distributed settings from the energy perspective. For MST in the sleeping Congest model, Augustine, Moses Jr., and Pandurangan [1] proved that the optimal awake complexity is Θ(log n). They gave a randomized algorithm that, with high probability, computes an MST using O(log n) awake rounds and O(n log n) rounds, as well as a deterministic algorithm using O(log n) awake rounds and O(n log5 n) rounds. For SSSP in the 6

sleeping Congest model, Ghaffari and Trygub [14] present a deterministic algorithm that runs e in O(n) rounds and each node is awake during only poly(log n) rounds.

2

Awake-efficient BaseMDS

We present a sleeping Congest version of BaseMDS (Algorithm 1) [16] that computes an O(log ∆)-approximate dominating set in expectation in O(log2 ∆) rounds, with each node awake in O(log ∆ log log n) rounds. The stated round and awake-complexity bounds hold deterministically. We use the same thresholds Ti = ∆/2i and probabilities pk = min{1, 2k /∆} as in BaseMDS. Also recall that dki (v) denotes the number of undominated nodes in the closed neighborhood of v just before iteration k of stage i, with respect to the current dominating set D, i.e., dki (v) = |{u ∈ N + (v) : u ∈ / N + (D)}|. We will refer to dki (v) as the residual degree of v during iteration k of stage i. We note that the algorithm only uses 1-bit messages. The algorithm has two phases. Let i⋆ = min{i : Ti ≤ C⌈log ∆⌉2 log n}, where C is a constant that will be fixed later (in Lemma 6). Phase 1 runs stages 1, . . . , i⋆ − 1. During Phase 1 most nodes sleep most of the time, and a candidate decides whether to join D from a sampling-based estimate of its residual degree. Phase 2 runs the remaining O(log log n) stages exactly as in BaseMDS, with every node awake in every round. We split the algorithm in this manner because we need sufficiently many samples for a node to obtain an accurate estimate of its residual degree (Lemma 6). Before Phase 1 starts, each node u picks an estimator assignment (Iu , Ku ) ∈ [⌈log ∆⌉] × [⌈log ∆⌉] uniformly at random. If Iu < i⋆ , node u wakes up in iteration Ku of stage Iu and acts as an estimator, replying to queries from its neighbors. Thus each node acts as an estimator in at most one iteration during Phase 1. We now describe Phase 1 of our algorithm. Each stage i, 1 ≤ i < i⋆ , begins with two status-exchange rounds in which every node is awake. In the first of these rounds, every v ∈ D broadcasts this fact, and any node hearing such a broadcast from a neighbor records that it is dominated. In the second round, every undominated node broadcasts this status. Using this information, each node v then computes d1i (v), its residual degree during iteration 1 of stage i. A node v with d1i (v) ≥ Ti becomes a candidate for stage i. Each candidate v then tosses a sequence of ⌈log ∆⌉ biased coins, with coin k in the sequence having success probability pk . Let Jv,i ∈ [⌈log ∆⌉] denote the minimum index k such that the outcome of coin k is a success. Since p⌈log ∆⌉ is 1, Jv,i is well-defined. As a candidate, v only needs to wake in iteration Jv,i to decide whether to join D. The stage is then run for ⌈log ∆⌉ iterations, each with two rounds. In round 1 of iteration k, every awake node w ∈ D that joined D earlier in stage i informs all neighbors of this fact and any awake node hearing from a neighbor in D marks itself dominated. In round 2 of iteration k, every node u with (Iu , Ku ) = (i, k) that was undominated at the start of stage i sends its status (i.e., dominated or undominated) to all neighbors. Note that such a node u has picked iteration k in stage i to serve as an estimator. Let X be the number of nodes in N + (v) that were undominated at the start of stage i and replied to v in this round (including v itself if (Iv , Kv ) = (i, Jv,i ) and v was undominated at the start of stage i), and let Y be the number of these that are still undominated. The candidate v then computes b = Y d1 (v) if X > 0, d(v) X i

b = 0 if X = 0. d(v)

b ≥ Ti , then v joins D. as an estimator of its residual degree in stage i, iteration k. If d(v) The above description ignores Challenge 3 from the “Introduction” which asks how nodes that wake up in iteration k in stage i as estimators, can know their status accurately. The next subsection describes the virtual binary tree idea [3, 1, 13] as it applies to our algorithm. This results in each node staying awake for an additional O(log log ∆) rounds, so that estimators know their status accurately. 7

2.1

Wake schedule via virtual binary trees

We want to ensure that candidates that join D in stage i inform neighbors that wake up later as estimators in stage i. We use the virtual binary tree idea described in previous work [3, 1, 13], specifically the formulation of Ghaffari and Portmann [13], restated below. Lemma 4 ([13], Lemma 2.5). For any positive integer T , there exist sets S1 , . . . , ST ⊆ [T ] with |Sk | ≤ ⌈log T ⌉ such that for every i, j ∈ [T ] with i ≤ j there exists ℓ ∈ Si ∩Sj satisfying i ≤ ℓ ≤ j. We use this lemma as follows. Consider two neighboring nodes u and v, scheduled to wake up in iterations ku and kv , ku ≤ kv , in stage i. Now suppose that instead of waking up just in iterations ku and kv , node u wakes up in all iterations k ∈ {ku } ∪ Sku in stage i and node v wakes up in all iterations k ∈ {kv } ∪ Skv in stage i. Then the lemma guarantees that there exists an iteration ℓ ∈ Sku ∩ Skv in stage i in which both u and v are awake and they can share information in that common iteration. Replacing each Sk with Sk ∪ {k}, we may assume k ∈ Sk for every k. Since each stage has T = ⌈log ∆⌉ iterations, applying Lemma 4, we see that every set Sk satisfies |Sk | = O(log log ∆), which in turn implies that every node that is scheduled to wake up in stage i will wake up in O(log log ∆) iterations. Note that all nodes can compute all sets {Sk }Tk=1 at the start of the algorithm and reuse them in every stage for determining at the start of the stage, which iterations to wake up in. We now provide more details about the wake up schedules of estimators and candidates separately. Estimator schedule. An estimator u with (Iu , Ku ) = (i, k) wakes at every ℓ ∈ Sk with ℓ ≤ k. Node u acts as an estimator in iteration k. The earlier wake-up iterations allow u to receive updates from any neighbor that joined D in an earlier iteration of stage i. Candidate schedule. A candidate v with Jv,i = k wakes up in iteration k to determine its residual degree and then possibly join D. If v joins D at iteration k, it wakes in every later iteration ℓ ∈ Sk with ℓ > k to inform all neighbors (who are awake in that iteration) of this fact. Otherwise (if v does not join D in iteration k), v sleeps for the remainder of the stage. By Lemma 4, for any w that joined D in stage i and any estimator u with Jw,i ≤ Ku , the sets SJw,i and SKu intersect at some ℓ ∈ [Jw,i , Ku ]. Thus, at iteration ℓ, node w informs node u that it has joined D. Consequently, before acting as an estimator in iteration Ku , node u knows that it has become dominated. Algorithm 2 presents the full pseudocode.

2.2

Analysis

In transforming BaseMDS into an energy-efficient algorithm (Algorithm 2), we ensured that each node wakes up only O(1) times per stage by virtue of it being a candidate. We first show that this transformation is correct. Consider a node v and suppose that v is a candidate for stage i. In other words, d1i (v) ≥ Ti . Consider the following two executions for node v during the iterations in stage i. Execution 1: For each iteration k = 1, 2, . . . , ⌈log ∆⌉, node v tosses a coin with probability pk = min{1, 2k /∆} and joins D at the first iteration k during which dki (v) ≥ Ti and the coin k is successful. Execution 2: Set J = min{k : coin k is successful}. Node v joins D at iteration J iff dJi (v) ≥ Ti . The following lemma shows that the two executions are equivalent. Lemma 5 (First-success sampling). If the coins used in executions 1 and 2 are coupled, then either node v does not join D in both executions or node v joins D in both executions in the same iteration. Therefore, the two executions have the same partial dominating set D after every iteration of stage i. 8

Algorithm 2 BaseMDS-Awake ⌈log ∆⌉

Require: ∆ known to all nodes; constant C from Lemma 6; wake schedules {Sk }k=1 Lemma 4. 1: D ← ∅; i⋆ ← min{i : Ti ≤ C⌈log ∆⌉2 log n}

from

▷ Ti = ∆/2i

2: Each v draws (Iv , Kv ) ∼ Unif([⌈log ∆⌉] × [⌈log ∆⌉]).

Phase 1: sampling-based estimation. 3: for i = 1, . . . , i⋆ − 1 do ▷ stages 4: Round 1: every awake candidate in D informs neighbors that it is in D; any awake node hearing this marks itself dominated. 5: Round 2: every node wakes; every undominated node broadcasts this status, and each v uses this information to compute d1i (v) = |N + (v) \ N + (D)|. 6: Each v for which d1i (v) ≥ Ti is a candidate. 7: Each candidate v computes first-success iteration Jv,i ∈ [⌈log ∆⌉] by tossing a sequence of biased coins with pk = min{1, 2k /∆}. ▷ Lemma 5 8: for k = 1, . . . , ⌈log ∆⌉ do ▷ iterations 9: Every candidate v with Jv,i = k wakes up. 10: Every candidate w ∈ D that joined earlier in stage i wakes up if k ∈ SJw,i . 11: Every estimator u with Iu = i wakes up if k ∈ SKu and k ≤ Ku . 12: Round 1: every awake candidate informs neighbors that it is in D; any awake node hearing this marks itself dominated. 13: Round 2: every u with (Iu , Ku ) = (i, k) that was undominated at the start of stage i informs all neighbors of its status. b from the received statuses; if d(v) b ≥ Ti , 14: Each candidate v computes its estimate d(v) v joins D, and schedules wake-ups at {ℓ ∈ Sk : ℓ > k}. Phase 2: exact cleanup. 15: Run stages i⋆ , . . . , ⌈log ∆⌉ of BaseMDS (Algorithm 1) exactly on the residual instance, with every node awake. 16: return D. Proof. Couple the two executions by using the same sequence of coins for every candidate v, and let J = min{k : coin k is successful}. If dJi (v) ≥ Ti , then v joins D in iteration J in both executions. Otherwise, dJi (v) < Ti , and since residual degree is nonincreasing during a stage, dki (v) < Ti for every k > J. Thus v does not join D in either execution. Hence the same nodes join D in every iteration, and the two executions have the same partial dominating set D after every iteration of stage i. 2.2.1

Correctness of estimation

The next lemma shows that, in Phase 1, the sampling estimates of residual degree yield a correct eligibility decision whenever the true residual degree is sufficiently far from the threshold. Lemma 6. Fix constants γ ∈ (0, 1/2) and c0 ≥ 1. For a sufficiently large constant C = C(γ, c0 ), with probability at least 1 − n−c0 , the following holds for every Phase 1 candidate v, every stage i in which it is a candidate, and every iteration k of that stage: b ≥ Ti , dki (v) ≥ (1 + γ)Ti =⇒ d(v)

b < Ti , dki (v) ≤ (1 − γ)Ti =⇒ d(v)

b denotes the residual degree estimate that v computes in iteration k, stage i. where d(v) Proof. Let L = ⌈log ∆⌉. Consider a vertex v which is a Phase 1 candidate in a stage i < i⋆ . Consider an iteration k in stage i. Let A be the nodes of N + (v) that are undominated at the 9

beginning of stage i, and let B ⊆ A be those still undominated immediately before iteration k. Thus |A| = d1i (v) and |B| = dki (v). Our goal is to show that the fraction of estimators that are still undominated is close to |B|/|A|. Let X be the number of estimators in iteration k, stage i, that belong to A and Y be b = (Y /X)|A| as the residual the number of these estimators that belong to B. Since we use d(v) b degree estimator, if Y /X ∼ |B|/|A|, then d(v) ∼ |B|. First, we view the estimator assignments sequentially. Let S denote the L2 stage–iteration pairs, ordered lexicographically. Although the algorithm assigns to each node one stage–iteration pair selected uniformly at random at the beginning (Line 2, Algorithm 2), for the purposes of the analysis, we may equivalently generate these assignments in each iteration, as follows. Let M denote the number of stage–iteration pairs in the suffix of S starting at (and including) the current pair (i, k). Imagine that at the start of iteration k in stage i, every node not yet assigned a stage–iteration pair is assigned the current pair (i, k), independently, with probability 1/M . A simple coupling argument in which the random choices made by the two processes are coupled together, can establish the equivalence. Indeed, the probability that a node is assigned to any QL2 2 particular pair is r=M +1 (1−1/r)·(1/M ) = 1/L . Furthermore, the probability that a node has Q 2 2 not been assigned prior to the current stage–iteration pair (i, k) is L r=M +1 (1 − 1/r) = M/L . ′ Let A ⊆ A be the nodes assigned to stage–iteration pair (i, k) or to a later pair, and let B ′ = B ∩ A′ . Next, we bound the sizes of |A′ | and |B ′ |. We know that E[|A′ |] = |A| · M/L2 . Since v is a candidate in stage i, |A| ≥ Ti . Furthermore, since i < i⋆ , Ti > CL2 log n. Therefore, E[|A′ |] > C log n and using Chernoff bounds [23, Chapter 4], in the form of Corollary 17(1) in Appendix A, we get that Prob[|A′ | ∈ (1 ± γ/4)|A| · (M/L2 )] ≥ 1 − n−(c0 +5) .

(1)

Similarly, E[|B ′ |] = |B| · M/L2 . To bound the deviation of |B ′ | from its expectation, we assume that |B| ≥ γTi /8. An application of Chernoff bounds implies that Prob[|B ′ | ∈ (1 ± γ/4)|B| · (M/L2 )] ≥ 1 − n−(c0 +5) .

(2)

We postpone considering the case |B| < γTi /8 until the end of the proof. Next we bound X and Y in terms of |A′ | and |B ′ | respectively. Conditioned on all assignments in previous stage–iteration pairs, A′ and B ′ are fixed. According to our sequential view of selecting estimators in each iteration, each node of A′ is assigned to the current stage–iteration pair (i, k) independently, with probability 1/M . Thus X counts the nodes of A′ assigned to the current stage–iteration pair, while Y counts the nodes of B ′ assigned to the current stage– iteration pair. Therefore E[X|A′ ] = |A′ |/M and E[Y |A′ ] = |B ′ |/M . Let E1 denote the event |A′ | ∈ (1 ± γ/4)|A| · (M/L2 ), whose probability is bounded in (1). We now bound X conditioned on E1 .       |A′ | γ 2 |A′ | 1 Prob X ∈ (1 ± γ/4) (3) E1 ≥ 1 − exp − · · ≥ 1 − n−(c0 +5) . M 4 M 3 The second inequality above is due to the conditioning on E1 , which implies that |A′ | ≥ (1 − γ/4)|A| · (M/L2 ) > (1 − γ/4)C log n. To obtain bounds on Y , as before, we assume |B| ≥ γTi /8. Let E2 denote the event |B ′ | ∈ (1 ± γ/4) |B| · (M/L2 ), whose probability is bounded in (2). We bound Y conditional on E2 as follows:       γ 2 |B ′ | 1 |B ′ | Prob Y ∈ (1 ± γ/4) E2 ≥ 1 − exp − · · ≥ 1 − n−(c0 +5) . (4) M 4 M 3 The second inequality above is due to the
conditioning on E2 , which implies that |B ′ | ≥ γ
γ
γTi M M 1 − 4 |B| · L2 ≥ 1 − 4 · 8 · L2 > 1 − γ4 · γ8 · C log n. 10

Next we bound X and Y in terms of |A| and |B| respectively.     |A| |A| ≥ Prob X ∈ (1 ± γ/4) 2 E1 · Prob[E1 ] Prob X ∈ (1 ± γ/4) 2 L L   (1 ± γ/4) |A′ | ≥ Prob X ∈ E1 · (1 − n−(c0 +5) ) (1 ± γ/4) M   |A′ | ≥ Prob X ∈ (1 ± γ/4) E1 · (1 − n−(c0 +5) ) M ≥ (1 − n−(c0 +5) ) · (1 − n−(c0 +5) ) ≥ 1 − n−(c0 +4) .

(5)

The second inequality above follows from (1). As before, to bound Y , we assume |B| ≥ γTi /8. In this case, we use calculations very similar to the calculations above involving X and |A| to show that   |B| Prob Y ∈ (1 ± γ/4) 2 ≥ 1 − n−(c0 +4) . (6) L Finally, we translate the bounds on X and Y into decision probabilities. Case 1: dki (v) = |B| ≥ (1 + γ)Ti . Then, b d(v) = ≥ = ≥ ≥

Y · |A| X (1 − γ/4)|B| L2 · · |A| with probability ≥ 1 − n−(c0 +3) L2 (1 + γ/4)|A| (1 − γ/4) · |B| (1 + γ/4) (1 − γ/4) · (1 + γ) · Ti (1 + γ/4) (1 − γ/2) · (1 + γ) · Ti

≥ Ti The second inequality above follows from (5) and (6). Case 2: dki (v) = |B| ≤ (1 − γ)Ti . We consider two subcases depending on |B|. • |B| ≥ γTi /8: In this case, we use the upper bound on Y in (6), the lower bound on X b ≤ Ti with probability in (5), and calculations very similar to Case 1 to show that d(v) −(c +3) at least 1 − n 0 . • |B| < γTi /8: Note that E[Y ] = E[E[Y ||B ′ |]] =

E[|B ′ |] |B| γTi = 2 < . M L 8L2

Applying a one-sided Chernoff bound to Y gives Prob[Y ≤ (γ/4)Ti /L2 ] ≥ 1 − n−(c0 +4) . Here we use that Ti > CL2 log n. Together with the lower bound on X in (5), and using similar calculations as in Case (1), this gives b ≤ d(v)

γTi < Ti 4(1 − γ/4)

with probability at least 1 − n−(c0 +3) . The second inequality above requires γ < 1/2, as stipulated by the theorem statement. 11

Thus both claims in the theorem statement hold for the fixed triple (v, i, k) with probability at least 1 − n−(c0 +3) . Since there are at most nL2 ≤ n3 triples (v, i, k), a union bound gives the claimed probability of at least 1 − n−c0 . 2.2.2

Awake complexity

Lemma 7. In Algorithm 2, each node is awake for O(log ∆ + log log ∆) = O(log ∆) rounds during Phase 1. Proof. As a candidate: Every node is awake for 2 rounds at the start of each stage i, for status exchange. If a node v determines that it is a candidate for stage i, it wakes up during its first-success iteration Jv,i . This implies O(log ∆) awake rounds during Phase 1. Furthermore, if a node joins D in stage i, it wakes up an additional O(log log ∆) rounds in stage i, as prescribed by the virtual binary tree schedule SJv,i . As an estimator: Every node u wakes at its randomly assigned stage–iteration pair (Iu , Ku ) and also during the O(log log ∆) iterations in SKu in stage Iu . Thus nodes wake up for a total of O(log ∆ + log log ∆) = O(log ∆) rounds. 2.2.3

Approximation analysis

We start by stating the approximation guarantee provided by Algorithm 1, proved in [16]. Theorem 8 ([16], Theorem 3.1). Let G be some MDS instance and let D denote the solution returned by Algorithm 1. Furthermore, let OPT denote the value of an optimal fractional dominating set for G. Then, E[|D|] = O(log ∆) · OPT. Algorithm 2 faithfully mimics Algorithm 1 except that it uses residual degree estimates, rather than the actual residual degrees. These residual degree estimates are approximately correct, as shown in Lemma 6. The following lemma shows that the approximation guarantee in Theorem 8 is maintained, even using these approximate residual degree estimates. Lemma 9 (Approximate eligibility). Fix constants 0 < a < 1 < b and a cutoff stage h ∈ {1, . . . , ⌈log ∆⌉}. Consider a variant of the BaseMDS algorithm (Algorithm 1) in which, for stages i < h, the exact eligibility test for being a candidate in stage i, dki (v) ≥ Ti , is replaced by any rule satisfying dki (v) ≥ bTi ⇒ v is a candidate,

dki (v) ≤ aTi ⇒ v is not a candidate,

with the count of eligible vertices in N + (u) \ D nonincreasing in k while
u remains undominated; stages i ≥ h use the exact eligibility test. Then D is an O ab · log ∆ -approximate dominating set in expectation. Lemma 6 implies that we can apply the above lemma with a = 1 − γ, b = 1 + γ, and h = i⋆ . Since γ < 1/2, we have b/a = (1 + γ)/(1 − γ) < 3, and so the approximation factor is O(log ∆), matching the guarantee in Theorem 8. 2.2.4

Proof of the main theorem

Theorem 10. Algorithm 2 computes an O(log ∆)-approximate dominating set in expectation in O(log2 ∆) rounds, with each node awake in at most O(log ∆ log log n) rounds. Proof. Rounds. Phase 1 and Phase 2 together run ⌈log ∆⌉ stages (split at i⋆ ), each with ⌈log ∆⌉ iterations, each iteration executed in O(1) rounds. This is a total of O(log2 ∆) rounds. Awake rounds. Phase 1 requires O(log ∆) awake rounds per node according to Lemma 7. Phase 2 is executed with no sleeping and it adds O(log ∆ log log n) awake rounds, for a total of O(log ∆ log log n) awake rounds. 12

Algorithm 3 (p, q)-MDS Require: parameters 1 < p, q ≤ ∆; maximum closed-neighborhood size ∆ known to all nodes. 1: D ← ∅. 2: for i = 1, 2, . . . , ⌈logp ∆⌉ do ▷ stages 3: for k = 1, 2, . . . , ⌈logq ∆⌉ do ▷ iterations 4: for each node v in parallel do 5: dki (v) ← |{u ∈ N + (v) : u ∈ / N + (D)}|. 6: if v ∈ / D and dki (v) ≥ Ti then ▷ Ti = ∆/pi 7: add v to D with probability pk = min{1, q k /∆}. 8: return D.

Approximation. The BaseMDS provides an O(log ∆) approximation in expectation (Theorem 8). Fixing c0 = 2, Lemma 6 and Lemma 9 together imply that with probability at least 1 − n−2 , Algorithm 2 provides an O(log ∆) approximation in expectation, even though it uses residual degree estimates to decide which nodes are candidates in each stage. With probability at most n−2 , |D| can be much larger than OPT, but since |D| ≤ n, the additional contribution of this rare, bad event to E[D] is just o(1).

3

The (p, q)-MDS algorithm

We now present a simple and natural generalization of BaseMDS, that we call (p, q)-MDS. This algorithm yields a tradeoff between the approximation factor and the round count: by Theorem 3, (p, q)-MDS returns an O(pq logp ∆)-approximate dominating set in O(logp ∆·logq ∆) rounds in expectation. Thus increasing either one or both of the two parameters p and q reduces the number of rounds, while increasing the approximation factor. This round-approximation tradeoff implies a tradeoff between the awake complexity and approximation factor as well via the awake-efficient version, described in the next section. In the (p, q)-MDS algorithm, 1 < p ≤ ∆ is the ratio between consecutive thresholds and 1 < q ≤ ∆ is the base of the inner-loop probabilities. The algorithm runs ⌈logp ∆⌉ outer stages with thresholds Ti = ∆/pi , and each stage has ⌈logq ∆⌉ iterations with probabilities pk = min{1, q k /∆}; setting p = q = 2 recovers BaseMDS. Algorithm 3 presents the pseudocode. The analysis below generalizes the approximation analysis of [16, Lemmas 3.2–3.3 and Theorem 3.1]. In the BaseMDS algorithm of [16], Lemma 3.3 bounds by a constant the expected number of neighbors of any node v added to the dominating set in the stage in which the element is first covered. Lemma 3.2 uses this bound to then bound the expected number of nodes added to the dominating set in the first stage, and Theorem 3.1 applies this argument to the residual instance at each stage. We use the same charging structure, but extend it to arbitrary 1 < p, q ≤ ∆. We obtain a bound of O(q) on the expected number of nodes added to the dominating set in the first stage. Using this, we show that each stage contributes O(pq) · OPT nodes in expectation to the dominating set, and summing over ⌈logp ∆⌉ stages, gives the O(pq logp ∆) approximation bound. This argument leads to the following theorem. Theorem 3 (restated). For every 1 < p, q ≤ ∆, there is a randomized Congest algorithm that returns an O(p · q · logp ∆)-approximate dominating set in expectation, in O(logp ∆ · logq ∆) rounds. Proof. The round complexity is immediate: ⌈logp ∆⌉ outer stages, each with ⌈logq ∆⌉ iterations, each implementable in O(1) Congest rounds. We prove the approximation. Let Ui be the set of undominated vertices at the beginning of stage i and Di the set of vertices selected during stage i. 13

Residual degree invariant. At the beginning of every stage i, every vertex’s residual degree has size at most pTi . For i = 1, this follows from |N + (v)| ≤ ∆ = pT1 . For i > 1, the final iteration of stage i − 1 has p⌈logq ∆⌉ = 1, so any vertex not in D with residual degree at least Ti−1 = pTi is eligible at that iteration and joins D with probability one. Since an optimum dominating set covers Ui and each of its vertices covers at most pTi vertices of Ui , |Ui | ≤ pTi · OPT . First-cover charge. Fix a stage i and u ∈ Ui . If u is not dominated during stage i, set Xu = 0; otherwise, with k the first iteration in which u becomes dominated, let Xu be the number of vertices selected at iteration k whose closed neighborhoods contain u. While u is undominated, the count of eligible vertices in N + (u) \ D is nonincreasing in k (no neighbor of u has joined D and residual degrees only decrease). By deferred decisions [23, §1.3], it suffices to consider a fixed nonincreasing sequence n1 ≥ n2 ≥ · · · ≥ 0, where nP in k is the number of eligible P vertices + −R k−1 N (u) just before iteration k. Put rk = nk pk and Rk = j≤k rj . Then E[Xu ] ≤ k rk e , −R k−1 where e upper-bounds the probability that no eligible neighbor was selected at an earlier iteration. Since r1 ≤ n1 q/∆ ≤ q and rk ≤ q rk−1 for k ≥ 2, X X X Z Rk−1 e−x dx ≤ 2q, rk e−Rk−1 ≤ q + q rk−1 e−Rk−1 ≤ q + q k

k≥2

k≥2

Rk−2

R A+r using r e−(A+r) ≤ A e−x dx. Therefore E[Xu ] ≤ 2q. Stage bound. Every vertex selected at stage P i has residual degree at least Ti at the moment of selection (it is eligible there), so Ti |Di | ≤ u∈Ui Xu . Taking expectations, E[|Di | | Ui ] ≤

2q |Ui | ≤ 2pq · OPT . Ti

Summing over the ⌈logp ∆⌉ stages gives E[|D|] = O(pq logp ∆) · OPT. Finally, the output is a dominating set: T⌈logp ∆⌉ ≤ 1 and p⌈logq ∆⌉ = 1; any vertex still undominated before the last iteration has residual degree at least 1 ≥ T⌈logp ∆⌉ , hence is eligible and joins with probability one.

4

Awake-efficient (p, q1 , q2 )-MDS

This section presents an awake-efficient implementation of the (p, q)-MDS algorithm of Section 3. Transforming (p, q)-MDS into an awake efficient algorithm follows along the lines of transforming BaseMDS into BaseMDS-Awake (Algorithm 2), with one important difference. As in BaseMDS-Awake, we use two phases, with nodes sleeping a lot in Phase 1, but staying awake fully in Phase 2. For the stages in Phase 1, we invove (p, q1 )-MDS, whereas for Phase 2 we invoke (p, q2 )-MDS, with different values of q1 and q2 . In fact, settings that lead to best tradeoffs between awake complexity and approximation include q1 = O(1) and q2 = log ∆/ log log n. We call this the (p, q1 , q2 )-MDS-Awake algorithm; its pseudocode is given in Algorithm 4. The helper lemmas for BaseMDS-Awake translate to (q1 , q2 )-MDS-Awake in a straightforward manner. The first-success sampling lemma (Lemma 5) extends directly to Algorithm 4, with ⌈logq1 ∆⌉ Phase 1 iterations and probabilities pk = min{1, q1k /∆}. The next lemma is the parameterized counterpart of Lemma 6. Lemma 11 (Estimator decision). Fix 1 < p, q1 ≤ ∆, γ ∈ (0, 1/2), and c0 ≥ 1. For a sufficiently large constant C = C(γ, c0 ), with probability at least 1 − n−c0 , the following holds simultaneously for every Phase 1 candidate v, every stage i < i⋆ in which it is a candidate, and every iteration k ∈ [⌈logq1 ∆⌉]: b ≥ Ti , dki (v) ≥ (1 + γ)Ti =⇒ d(v)

b < Ti , dki (v) ≤ (1 − γ)Ti =⇒ d(v) 14

Algorithm 4 (p, q1 , q2 )-MDS-Awake Require: Parameters 1 < p, q1 , q2 ≤ ∆; ∆ known to all nodes; constant C from Lemma 6; wake ⌈logq ∆⌉

schedules {Sk }k=1 1

from Lemma 4.

1: D ← ∅; i⋆ ← min{i : Ti ≤ C⌈logp ∆⌉⌈logq1 ∆⌉ log n}

▷ Ti = ∆/pi

2: Each v draws (Iv , Kv ) ∼ Unif([⌈logp ∆⌉] × [⌈logq1 ∆⌉]).

Phase 1: sampling-based estimation. 3: for i = 1, . . . , i⋆ − 1 do ▷ stages 4: Round 1: every node wakes; every v ∈ D broadcasts this fact, and any node hearing such a broadcast from a neighbor marks itself dominated. 5: Round 2: every node wakes; every undominated node broadcasts this status, and each v uses this information to compute d1i (v) = |N + (v) \ N + (D)|. 6: Each v for which d1i (v) ≥ Ti is a candidate. 7: Each candidate v computes first-success iteration Jv,i ∈ [⌈logq1 ∆⌉] by tossing a sequence of biased coins with pk = min{1, q1k /∆}. ▷ Lemma 5 8: for k = 1, . . . , ⌈logq1 ∆⌉ do ▷ iterations 9: Every candidate v with Jv,i = k wakes up. 10: Every candidate w ∈ D that joined earlier in stage i wakes up if k ∈ SJw,i . 11: Every estimator u with Iu = i wakes up if k ∈ SKu and k ≤ Ku . 12: Round 1: every awake candidate in D informs neighbors that it is in D; any awake node hearing this marks itself dominated. 13: Round 2: every u with (Iu , Ku ) = (i, k) that was undominated at the start of stage i informs all neighbors of its status. b from the received statuses; if d(v) b ≥ Ti , 14: Each candidate v computes its estimate d(v) v joins D, and schedules wake-ups at {ℓ ∈ Sk : ℓ > k}. Phase 2: exact cleanup. 15: Run stages i⋆ , . . . , ⌈logp ∆⌉ of (p, q2 )-MDS (Algorithm 3) exactly on the residual instance,

with every node awake.

16: return D.

b denotes the estimate that v would compute in iteration k. where d(v) Proof. The proof of Lemma 6 applies with L2 replaced by ⌈logp ∆⌉⌈logq1 ∆⌉, the number of stage–iteration pairs. Fix a Phase 1 candidate v, a stage i < i⋆ , and an iteration k. Let A be the nodes of N + (v) that are undominated at the beginning of stage i, and let B ⊆ A be those still undominated immediately before iteration k, as in the proof of Lemma 6. Thus |A| = d1i (v) and |B| = dki (v). Since each node chooses its estimator pair uniformly from [⌈logp ∆⌉] × [⌈logq1 ∆⌉], the sequential exposure argument in that proof applies unchanged after replacing L2 by ⌈logp ∆⌉⌈logq1 ∆⌉. Since v is a candidate, |A| ≥ Ti , and since i < i⋆ , Ti > C⌈logp ∆⌉⌈logq1 ∆⌉ log n. Hence the same Chernoff-bound argument shows that, with failure probability at most n−(c0 +3) , X ∈ (1 ± γ/4)|A|/(⌈logp ∆⌉⌈logq1 ∆⌉) and, whenever |B| ≥ γTi /8, Y ∈ (1 ± γ/4)|B|/(⌈logp ∆⌉⌈logq1 ∆⌉). b ≥ Ti , while |B| ≤ (1 − γ)Ti and Therefore, exactly as in Lemma 6, |B| ≥ (1 + γ)Ti implies d(v) b |B| ≥ γTi /8 imply d(v) < Ti . It remains to consider |B| < γTi /8. In this case, E[Y ] = |B|/(⌈logp ∆⌉⌈logq1 ∆⌉) < γTi /(8⌈logp ∆⌉⌈logq1 ∆⌉). The same one-sided Chernoff bound as in Lemma 6, together with the b ≤ γTi /(4(1 − γ/4)) < Ti , where the last inequality uses γ < 1/2. lower bound on X, gives d(v) Thus both implications hold for every fixed triple (v, i, k) with failure probability at most −(c n 0 +3) . For fixed p, q1 > 1, there are at most n⌈logp ∆⌉⌈logq1 ∆⌉ = O(n log2 n) such triples. A 15

union bound therefore gives the claimed probability of at least 1 − n−c0 , for a sufficiently large C = C(γ, c0 ). The approximate-eligibility lemma is restated below for general parameters as Lemma 12. Lemma 12 (Approximate eligibility). Fix 1 < p, q1 , q2 ≤ ∆, constants 0 < a < 1 < b, and a cutoff stage h ∈ {1, . . . , ⌈logp ∆⌉}. Suppose we invoke (p, q1 )-MDS in stages i < h and (p, q2 )MDS in stages i ≥ h. For stages i < h, the exact eligibility test dki (v) ≥ Ti is replaced by any rule satisfying dki (v) ≥ bTi ⇒ v is a candidate,

dki (v) ≤ aTi ⇒ v is not a candidate,

with the count of eligible vertices in N + (u) \ D nonincreasing in k while
u remains undominated; stages i ≥ h use the exact rule. Then D is an O q1 ph + q2 p(logp ∆ − h) -approximate dominating set in expectation. Proof. The argument of Theorem 3 carries over with three modifications. Residual invariant. At the start of stage i, any undominated vertex with residual degree at least pTi = Ti−1 (when i − 1 ≥ h) or at least pbTi = bTi−1 (when i − 1 < h) was eligible at the final probability-1 iteration of stage i − 1 and joined D with probability one. Hence, at the beginning of stage i, the number of undominated vertices is at most pbTi · OPT. Per-stage first-cover bound. The first-cover argument in the proof of Theorem 3 shows that, for any fixed vertex, the expected number of selected vertices whose closed neighborhoods contain it in the iteration when it is first dominated is at most 2q1 in a Phase 1 stage and at most 2q2 in a Phase 2 stage. Stage bound. Every vertex selected in stage i has residual degree at least aTi at the moment of selection. Combining this fact with the residual and first-cover bounds above, the expected number of vertices selected in each Phase 1 stage is at most 2q1 pb/a · OPT = O(q1 p) · OPT. The analogous bound with q2 holds for each Phase 2 stage. Summing over the h − 1 Phase 1 stages and the ⌈logp ∆⌉ − h + 1 Phase 2 stages gives the claimed bound. Lemma 13 bounds the awake complexity of Phase 1 of Algorithm 4. It extends Lemma 7 to the parameters p, q1 , q2 by replacing 2 throughout the proof with the appropriate parameter. Lemma 14 bounds the awake complexity of Phase 2. Lemma 13. In Algorithm 4, each node is awake for O(logp ∆ + log logq1 ∆) rounds during Phase 1. Proof. O(1) candidate wake-ups per stage contribute O(⌈logp ∆⌉) across Phase 1; a single join contributes O(log⌈logq1 ∆⌉) rebroadcast wake-ups in SJv,i ; the estimator role contributes another O(log⌈logq1 ∆⌉) wake-ups in SKu . Lemma 14. In Algorithm 4, Phase 2 executes the remaining O(logp log n) stages of the (p, q2 )variant of BaseMDS exactly. It uses O(logp log n · logq2 ∆) rounds and the same number of awake rounds per node. Proof. Ti⋆ ≤ C⌈logp ∆⌉⌈logq1 ∆⌉ log n and ∆ ≤ n give ⌈logp ∆⌉ − i⋆ + 1 = O(logp log n). Each remaining stage has ⌈logq2 ∆⌉ iterations executed in O(1) rounds with every node awake.

4.1

Parameter choices

Lemmas 13 and 14 show that the awake complexity of (p, q1 , q2 )-MDS is O(logp ∆ + log logq1 ∆ + logp log n · logq2 ∆).

16

(7)

Using Theorem 3, we see that Phase 1 contributes O(pq1 logp ∆) to the expected approximation, whereas Phase 2 contributes O(pq2 logp log n), for a total of O(pq1 logp ∆ + pq2 logp log n).

(8)

Using the setting of p = α, q1 = q2 = 2 in (7) and (8) and simplifying yields an awake complexity of O(logα ∆ · log log n) and approximation factor of O(α · max(logα ∆, logα log n)). Now we note that the dominant term in the awake complexity is the last term “logp log n · logq2 ∆” in (7), which can be reduced by increasing q2 . Furthermore, this increase will not worsen the approximation factor when the second term “pq2 logp log n” in (8) is less than the first term. This motivates setting q2 = max{2, log ∆/ log log n}, which equalizes the two terms, leading to the following theorem, which slightly improves the tradeoff between the awake complexity and approximation factor above. Theorem 15. For any 1 < α ≤ ∆, there is an algorithm in the sleeping Congest model that computes an O(α log ∆)-approximate dominating set in expectation in O(log ∆ · logα ∆) rounds. The awake complexity is O((log log n)2 + (log log n)3 / log α) when log log ∆ ≤ 2 log log log n, and O(log ∆/ log log ∆ + logα ∆(1 + log log n/ log log ∆)) when log log ∆ > 2 log log log n. In ε particular, the awake complexity is O(log n) for all ∆. Moreover, when ∆ ≥ 2log n for any constant ε ∈ (0, 1), the awake complexity simplifies to O(logα ∆ + log ∆/ log log ∆). Proof. For 1 < α < 2, we run the algorithm with parameter 2; all the claimed bounds continue to hold up to constant factors. Hence assume 2 ≤ α ≤ ∆. We instantiate Algorithm 4 with p = α, q1 = 2, and q2 = max{2, log ∆/ log log n}. Let Lα = ⌈logα ∆⌉, and let m2 = Lα − i⋆ + 1 denote the exact number of Phase 2 stages. By the definition of i⋆ , m2 = O(1 + logα log n). Rounds. Phase 1 and Phase 2 together contain exactly Lα stages. A Phase 1 stage has ⌈log ∆⌉ iterations, while a Phase 2 stage has ⌈logq2 ∆⌉ ≤ ⌈log ∆⌉ iterations. Each iteration takes O(1) rounds. Since α ≤ ∆, we have logα ∆ ≥ 1, and hence Lα = O(logα ∆). Therefore the total round complexity is O(log ∆ · logα ∆). Awake rounds. By Lemma 13, Phase 1 requires O(logα ∆ + log log ∆) awake rounds per node. Phase 2 requires O((1 + logα log n) logq2 ∆) awake rounds. Consider first the following regime: log log ∆ ≤ 2 log log log n.

(A)

Then log ∆ ≤ (log log n)2 . Since q2 ≥ 2, we have logq2 ∆ = O(log ∆) = O((log log n)2 ). Thus Phase 2 requires O((log log n)2 + (log log n)3 / log α) awake rounds. The Phase 1 bound is absorbed by this quantity, so the total awake complexity in regime (A) is O((log log n)2 + (log log n)3 / log α). Now consider the complementary regime: log log ∆ > 2 log log log n.

(B)

For sufficiently large n, this implies log ∆/ log log n > 2, and hence q2 = log ∆/ log log n. Moreover, log q2 = log log ∆−log log log n > 21 log log ∆. Therefore logq2 ∆ = O(log ∆/ log log ∆), and Phase 2 requires O(log ∆/ log log ∆ + (log ∆/ log α)(log log n/ log log ∆)) awake rounds. Combining this with the Phase 1 bound gives O(log ∆/ log log ∆ + logα ∆(1 + log log n/ log log ∆)) awake rounds, where log log ∆ is absorbed by log ∆/ log log ∆. Both regimes give an O(log n) awake bound. This is immediate in regime (A), since any fixed polynomial in log log n is o(log n). In regime (B), using log ∆ ≤ log n and the monotonicity of x/ log x, we have (log ∆/ log log ∆) log log n = O(log n). Since log α ≥ 1, every term in the regime (B) bound is therefore O(log n). 17

ε

If ∆ ≥ 2log n for a constant ε ∈ (0, 1), then log log ∆ ≥ ε log log n, so regime (B) applies for sufficiently large n and log log n/ log log ∆ = O(1). The awake complexity then simplifies to O(logα ∆ + log ∆/ log log ∆). Approximation. By Lemma 12, Phase 1 contributes O(αq1 Lα ) = O(α log ∆) to the expected approximation factor. For Phase 2, if q2 = 2, then q2 m2 ≤ 2Lα = O(log ∆). Otherwise, q2 = log ∆/ log log n, and m2 = O(1 + logα log n) gives q2 m2 = O(log ∆/ log log n + log ∆/ log α) = O(log ∆). Thus Phase 2 also contributes O(α log ∆), and the expected approximation factor is O(α log ∆).

5

Conclusions

We show that the awake complexity of computing an approximate MDS can be much smaller than the round complexity. Specifically, our techniques allow us to obtain an awake complexity that is almost an O(log ∆) factor smaller than the round complexity. We are able to achieve this without any additional cost in round complexity or approximation. Several questions remain open. Perhaps the most basic question raised by our work is whether we can achieve an O(log ∆)-approximate MDS with o(log ∆) awake complexity. Keeping the overall structure of our algorithm, ensuring an o(log ∆) awake complexity would imply that nodes don’t wake up every stage and in fact sleep through many stages. One natural idea along these lines is the following: suppose a node v is awake in stage i, but has not been added to the dominating set in stage i. Node v can use its residual degree at the end of stage i to pick a target stage to wake up in. Node v can then sleep until the start of the target stage. For example, if a node has very few undominated neighbors, it can potentially sleep for many stages. Unfortunately, adding this type of sleep schedule does not improve the awake complexity in the worst case. For the counterexample in Appendix B, a large fraction of the nodes wake up in many stages. This happens because a node may determine its target wake up stage based on its current residual degree, but by the time it has woken up, its residual degree has fallen further, making this a “wasted” wake up. In fact, in our counterexample, even the average awake complexity is Θ(log ∆). Designing an O(log ∆)-approximate MDS in o(log ∆) awake rounds seems to be a challenging open problem requiring fundamentally new ideas. It is also natural to ask whether allowing a larger round complexity can lead to lower awake complexity. Our current techniques do not give such a tradeoff, and we do not know whether an O(log ∆)-approximation with o(log ∆) awake complexity can be obtained even if polynomially many rounds are allowed. Another open question is whether we can show lower bounds on the awake complexity of computing an approximate MDS? While the awake complexities we achieve are closer to the KMW round complexity lower bounds [20] for computing log(∆)-approximate MDS, it is not clear whether they are optimal. The actual lower bound on awake complexity of computing an O(log ∆)-approximate MDS can be much smaller than the KMW lower bound. It would be interesting to see if one can design approximate MDS algorithms that have an awake complexity much lower than the KMW round complexity lower bounds. Acknowledgements. Shreyas Pai is grateful to the A. Raghunathan Center for Theoretical CS for support.

References [1] John Augustine, William K. Moses Jr., and Gopal Pandurangan. Awake complexity of distributed minimum spanning tree. In Structural Information and Communication Complexity, SIROCCO 2024, volume 14662 of Lecture Notes in Computer Science, pages 45–63. Springer, 2024. doi:10.1007/978-3-031-60603-8_3. 18

[2] Alkida Balliu, Pierre Fraigniaud, Dennis Olivetti, and Mikaël Rabie. Solving sequential greedy problems distributedly with sub-logarithmic energy cost. In Proceedings of the 44th ACM Symposium on Principles of Distributed Computing, PODC 2025, pages 417–427. ACM, 2025. doi:10.1145/3732772.3733499. [3] Leonid Barenboim and Tzalik Maimon. Deterministic logarithmic completeness in the distributed sleeping model. In 35th International Symposium on Distributed Computing, DISC 2021, volume 209 of LIPIcs, pages 10:1–10:19. Schloss Dagstuhl, 2021. doi: 10.4230/LIPIcs.DISC.2021.10. [4] Bonnie Berger, John Rompel, and Peter W. Shor. Efficient NC algorithms for set cover with applications to learning and geometry. Journal of Computer and System Sciences, 49(3):454–477, 1994. doi:10.1016/S0022-0000(05)80068-6. [5] Keren Censor-Hillel and Michal Dory. Distributed spanner approximation. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, pages 139–148. ACM, 2018. doi:10.1145/3212734.3212758. [6] Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Qizheng He, Wenzheng Li, and Seth Pettie. The energy complexity of broadcast. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, pages 95–104. ACM, 2018. doi:10.1145/3212734.3212774. [7] Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, and Wei Zhan. Exponential separations in the energy complexity of leader election. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 771–783. ACM, 2017. doi:10.1145/3055399.3055481. [8] Soumyottam Chatterjee, Robert Gmyr, and Gopal Pandurangan. Sleeping is efficient: MIS in O(1)-rounds node-averaged awake complexity. In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC 2020, pages 99–108. ACM, 2020. doi: 10.1145/3382734.3405718. [9] Vasek Chvatal. A greedy heuristic for the set-covering problem. Mathematics of operations research, 4(3):233–235, 1979. doi:10.1287/moor.4.3.233. [10] Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 624–633, 2014. doi:10.1145/2591796.2591884. [11] Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan. Distributed MIS in O(log log n) awake complexity. In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, pages 135–145. ACM, 2023. doi:10.1145/3583668. 3594574. [12] Mohsen Ghaffari and Julian Portmann. Average awake complexity of MIS and matching. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2022, pages 45–55. ACM, 2022. doi:10.1145/3490148.3538566. [13] Mohsen Ghaffari and Julian Portmann. Distributed MIS with low energy and time complexities. In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, pages 146–156. ACM, 2023. doi:10.1145/3583668.3594587. [14] Mohsen Ghaffari and Anton Trygub. A near-optimal low-energy deterministic distributed sssp with ramifications on congestion and apsp. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC ’24, page 401–411, New York, NY, USA, 2024. Association for Computing Machinery. doi:10.1145/3662158.3662812. 19

[15] Mohsen Ghaffari and Zi Song Yeoh. Exponential energy savings in local distributed graph algorithms. In Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2026, pages 261–287. ACM, 2026. doi:10.1145/3816782.3819215. [16] Christoph Grunau, Slobodan Mitrović, Ronitt Rubinfeld, and Ali Vakilian. Improved local computation algorithm for set cover via sparsification. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 2993–3011. SIAM, 2020. doi:10.1137/1.9781611975994.181. [17] Lujun Jia, Rajmohan Rajaraman, and Torsten Suel. An efficient distributed algorithm for constructing small dominating sets. Distributed Computing, 15(4):193–205, 2002. doi: 10.1007/s00446-002-0078-0. [18] David S Johnson. Approximation algorithms for combinatorial problems. In Proceedings of the fifth annual ACM symposium on Theory of computing, pages 38–49, 1973. doi: 10.1145/800125.804034. [19] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. The price of being near-sighted. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’06, pages 980–989, Philadelphia, PA, USA, 2006. Society for Industrial and Applied Mathematics. [20] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. Journal of the ACM, 63(2):17:1–17:44, 2016. doi:10.1145/2742012. [21] Fabian Kuhn and Roger Wattenhofer. Constant-time distributed dominating set approximation. In Proceedings of the Twenty-Second Annual ACM Symposium on Principles of Distributed Computing, PODC 2003, pages 25–32. ACM, 2003. doi:10.1145/872035.872040. [22] Tan D. Lam and Dung T. Huynh. Minimum dominating set and minimum connected dominating set construction in wireless sensor networks under the sleeping model. In Kevin Daimi, Hamid R. Arabnia, and Leonidas Deligiannidis, editors, Security and Management and Wireless Networks, volume 2254 of Communications in Computer and Information Science, pages 547–565, Cham, 2025. Springer Nature Switzerland. [23] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York, NY, 2005. [24] Saurav Pandit and Sriram V. Pemmaraju. Rapid randomized pruning for fast greedy distributed algorithms. In Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC ’10), pages 325–334, Zurich, Switzerland, 2010. ACM. doi:10.1145/1835698.1835777. [25] Sridhar Rajagopalan and Vijay V. Vazirani. Primal-dual RNC approximation algorithms for set cover and covering integer programs. SIAM Journal on Computing, 28(2):525–540, 1998. doi:10.1137/S0097539793260763.

A

Chernoff bounds

We use the following standard forms of the Chernoff bound (Chapter 4 of Mitzenmacher and Upfal [23]). Lemma 16 (Chernoff bounds). Let X1 , X2 , . . . , XN be independent random variables taking P values in {0, 1}, let X = N X , j=1 j and let µ = E[X].

20

1. For every δ ∈ (0, 1), Prob[X ∈ / (1 ± δ)µ] ≤ 2 exp −δ 2 µ/3 .
2. For every µH ≥ µ and every δ ∈ (0, 1], Prob[X ≥ (1 + δ)µH ] ≤ exp −δ 2 µH /3 . Part (1) is the two-sided bound we use when we know the expectation. Part (2) is the one-sided bound we use when we only have an upper bound µH on the expectation, which is the situation in the case |B| < γTi /8 in the proof of Lemma 6. In that proof we apply these bounds to sums whose expectation, or whose upper bound µH , is at least a constant fraction, depending only on γ, of C log n, and we want a failure probability of at most n−c for a constant c of our choosing. The following consequence of Lemma 16 is the form we use; the constant C of Lemma 6 is chosen large enough in terms of γ and c0 to absorb both these fractions and the constant factors in the two bounds above. Corollary 17. Fix constants δ ∈ (0, 1) and c > 0, and let X be as in Lemma 16. There is a constant C = C(δ, c) such that the following hold for every n ≥ 2. 1. If E[X] ≥ C log n, then Prob[X ∈ (1 ± δ)E[X]] ≥ 1 − n−c . 2. If µH ≥ E[X] and µH ≥ C log n, then Prob[X ≤ 2µH ] ≥ 1 − n−c . Proof. For (1), Lemma 16(1) bounds the failure probability by 2 exp(−δ 2 C log n/3), which is at most n−c once C is a large enough constant in terms of δ and c. For (2), Lemma 16(2) applied with δ = 1 bounds the failure probability by exp(−µH /3) ≤ exp(−C log n/3), which is again at most n−c for a large enough constant C.

B

Counterexample

Here we show an input graph G where a constant fraction of the nodes will need to wake up in all but the first stage of the BaseMDS algorithm. We consider an awake-efficient implementation of the BaseMDS algorithm where each node will decide to wake up in the stage where it becomes a candidate according to its current residual degree. We ignore the energy cost to accurately estimate the residual degree. Assume for the sake of clarity that ∆ = 2L+1 where L is the number of stages in BaseMDS. This means that for all 0 ≤ i ≤ L, the thresholds for becoming a candidate in stage i, Ti = ∆/2i are integers (and TL = 2). We construct a graph G of maximum degree at most ∆ in which every vertex in a core set Vcore is a candidate in at least L stages of the (p, q)-MDS algorithm. Let |Vcore | = ∆/2 − 2. For each i = 2, . . . , L, create two blocks Bi , Qi each having Ti vertices and a controller vertex ci . Connect every vertex in Vcore to every vertex in Bi , and connect ci to every vertex in Bi ∪ Qi . We add another controller vertex c1 that is adjacent to all nodes in Vcore and has additional ∆/2 neighbors Q1 . There are no other edges of vertices in G is P PLin G. The number i−1 ) ≤ 4∆. The following 1 + |Vcore | + |Q1 | + L (1 + |B | + |Q |) = ∆ − 1 + (1 + ∆/2 i i i=2 i=2 diagram illustrates one block of the construction. We degree in G is indeed at most ∆. Every v ∈ Vcore has degree P show that thePmaximum L i = ∆/2 − 1. Controller c has degree |V 1+ L |B | = 1 + ∆/2 i 1 core | + |Q1 | = ∆ − 2 and i=2 i=2 i−1 every controller ci for i ≥ 2 has degree |Bi | + |Qi | = 2Ti ≤ ∆/2 . Each vertex in Bi has degree |Vcore | + 1 = ∆/2 − 1, and each vertex in Qi has degree 1. The degrees of each node are set up in such a way that only ci is a candidate in stage i, vertices in Bi are candidates in the second stage, vertices in Vcore are candidates in the third stage, and vertices in Qi may be candidates only in the last stage, so all these vertices will sleep until these stages. Since c1 is the only candidate in stage one, it will remain a candidate until it joins the dominating set in stage one, which is guaranteed to happen, since in the last iteration of each stage, the candidates join with probability 1. Once c1 joins the dominating set, the vertices in Vcore are dominated and their residual degree is decreased by 2. Whereas 21

Vcore v1

···

vN

ci ··· bi,1

···

bi,2

··· bi,ki

qi,1

qi,2

···

qi,ℓi

Qi

Bi

Figure 1: One part of our counterexample graph G. Each core vertex is adjacent to all vertices in Bi , and the controller ci is adjacent to all vertices in Bi ∪ Qi . This figure only describes the construction for i > 1. the residual degree of nodes in Bi reduces to at most 2 as most of their neighbors in Vcore are dominated. Therefore, nodes in Bi wake up in the second stage, notice that their residual degree has fallen, and sleep until the last stage. This means that, c2 is the only candidate in the second stage, and similarly will join the dominating set in some iteration of the second stage. Now, whenPnodes in Vcore they find their residual degree PLwake up in the third stage, L L−2 ). This makes the Vcore nodes has decreased to i=3 |Bi | = i=3 (Ti ) = (∆/8)(1 − 1/2 ineligible to be candidates in the third stage, but they are eligible to be candidates in the fourth stage. Therefore, all nodes in Vcore sleep until the fourth stage. This means that, c3 is the only candidate in the third stage, and it will join the dominating set. This process will repeat in all future stages. To summarize, in stage i, vertices in Vcore and ci will wake up, the Vcore vertices will realize that their residual degree has fallen below the threshold for stage i, but it is above the threshold for stage i + 1. Therefore, vertices in Vcore wake up in stage i and decide to sleep until stage i + 1. This allows ci to join the dominating set in stage i, which prevents vertices in Vcore from becoming candidates in stage i + 1, which they will only figure out when they wake up in stage i + 1. Therefore, all vertices in Vcore wake up at least once in almost all the stages, which means that the (worst-case and average) awake complexity is Ω(L).

22

Related documents

• Local Clique Covers and Chromatic Number#985390
• Establishing the Polynomial Wolff Axioms for $δ$-Separated $δ$-Tubes With #o-minimality#1050320
• Min-Sum Set Cover on Parallel Machines#1141517
• Hyperplanes Avoiding Problem and Integer Points Counting in Polyhedra#144227
• Query Optimization and Evaluation via Information Theory: A Tutorial#2762