Approximating Minimum Dominating Set with Few Awake Rounds
summary
The gist
We study the Minimum Dominating Set (MDS) problem in the sleeping Congest model, a generalization of the standard Congest model, in which a node may sleep in some rounds and can only compute…
In short
The study investigates finding a Minimum Dominating Set (MDS) in a 'sleeping' communication model where nodes can only compute when awake. The work shows that an O(log $\Delta$)-approximation for MDS can be achieved with $o(\log^2 \Delta)$ awake complexity. This demonstrates a tradeoff between the quality of the solution and the energy cost (awake rounds) required to find it, suggesting current methods are not optimal.
Key concepts
- Minimum Dominating Set (MDS)
- The goal is to select the smallest possible set of nodes such that every other node in a network is either in this set or directly connected to at least one node in the set. In this paper, we aim to find an approximate version of this optimal selection.
- Sleeping Congest Model
- This is a communication model where nodes can choose to sleep during certain rounds. A node can only perform actions like computing or sending messages when it is awake. This introduces a constraint on how quickly information can be processed and how much energy (awake time) is spent.
- Awake Complexity
- This measures the total number of rounds a node must be awake to complete its task. The paper explores algorithms that minimize this 'energy' cost, showing that for certain approximation levels, this cost can be significantly lower than the standard round complexity.
Terminology used across episodes
This episode discusses
The paper
Approximating Minimum Dominating Set with Few Awake Rounds · Read on arXiv
University of Iowa · IIT Madras
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(Δ) -approximation algorithms (in expectation) for MDS that run in O(squared Δ) rounds, all of these have Ω(squared Δ) awake complexity. Whether this awake complexity can be improved is the question that drives our work. We present the first O(Δ) -approximation algorithm for MDS with O(Δ) awake complexity. The approximation guarantee holds in expectation, and the algorithm runs in O(2Δ) rounds. We can reduce the awake complexity further, but at the cost of approximation: we present, for any 1<α at most Δ, n, an algorithm in the sleeping CONGEST model that computes an O tilde(α αΔ) -approximate dominating set in expectation in O tilde(Δ times α Δ) rounds with O tilde(α Δ) awake complexity. Our results depend on a generalization of the CONGEST model Set Cover algorithm of Grunau, Mitrović, Rubinfeld, and Vakilian (SODA 2020) that we develop. This generalization computes an O(p times q times pΔ) -approximate dominating set in O(pΔ times qΔ) rounds for parameters 1<p,q at mostΔ. Our sleeping CONGEST algorithms apply a variety of techniques including sampling-based estimation and scheduling using virtual binary trees to the aforementioned 2-parameter Set Cover algorithm.
DOI: 10.4230/LIPIcs.DISC.2026.53
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Approximating Minimum Dominating Set with Few Awake Rounds".
Jane: Here's the gist of the paper. We study the Minimum Dominating Set (MDS) problem in the sleeping Congest model, 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 first O(log ∆)-approximation algorithm for MDS with o(log2 ∆) awake complexity runs in O(log2 ∆) rounds with O˜(log ∆) awake complexity Core Problem Motivation The core question driving the work is whether an O(log ∆)-approximation for MDS can be achieved 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.
Tom: First Result on Awake Complexity Theorem 1 (Informal) states that there is an algorithm in the sleeping Congest model that computes an O(log ∆)-approximate dominating set in expectation in O(log2 ∆) rounds and O˜(log ∆) awake complexity.
Jane: This result is obtained by designing a sleeping version of the SetCover algorithm of Grunau, Mitrović, Rubinfeld, and Vakilian
16: .
Tom: For moderately high values of ∆, i.e., ∆ ≥ 2 logε n for any constant ε ∈ (0, 1), the awake complexity bound simplifies to O(log ∆), losing the multiplicative O(poly(log log n)) terms.
Title and authors: Jane: Let's go back to what the paper is actually trying to accomplish in the "Approximating Minimum Dominating Set with Few Awake Rounds" paper. They are looking at how to find a minimum dominating set in this sleeping congestion model, and they are focusing specifically on reducing the awake complexity of that solution.
Tom: The core idea is that in these models, nodes can sleep in certain rounds and only compute or talk when they are awake. The authors state the core question driving their work is whether we can get an O log delta approximation for the minimum dominating set with o log2 delta awake complexity instead of just Omega(log2 delta).
Lu: They’ve done this by designing a sleeping version of a known algorithm called SetCover, which was developed by Grunau, Mitrović, Rubinfeld and Vakilian. That adaptation is the key methodology they're using to build their initial result.
Meng: So they’re not inventing an entirely new way to find the set; they’re taking a proven technique from another area—set cover—and adapting it to this specific sleeping model structure. That makes sense from a practical standpoint, but how does that adaptation actually change the complexity calculation?
Lalam: The paper shows that they can achieve an O log delta approximation in expectation in O log2 delta rounds with O˜(log delta) awake complexity using this adapted set cover approach. That's the first result they’re highlighting to show this is possible.
Tom: That initial result is significant because it directly addresses the question of whether we can beat that Omega(log2 delta) awake complexity barrier for achieving an O log delta approximation in expectation in those standard models.
Jane: And they immediately point out that this improvement has limitations; for moderately high values of delta, specifically when delta is bigger than two log epsilon n for any constant epsilon less than one, the awake complexity bound simplifies significantly to just O log delta.
Lu: That simplification is important because it means for a lot of real-world scenarios where the neighborhood size is large enough, the extra complexity terms vanish, leaving you with a cleaner O log delta awake complexity bound.
Meng: If we’re talking about deployment, that means for large networks, the energy cost per decision is much more manageable. But what if delta isn't that big? What happens to the performance then?
Tom: Well, when delta isn't that large, you lose those simplification terms and you end up back with the higher complexity bound involving log n. It shows a real sensitivity to the graph structure in this model.
Jane: So, if we’re listening to this right now and we’re running a system on a network where things aren't extremely dense, we need to be mindful of that structural dependence in our awake time.
Lu: And they also introduce the idea of a tradeoff between approximation quality and awake complexity as the main direction for their subsequent work, suggesting that you can weaken the approximation guarantee to get better energy performance.
Meng: That tradeoff sounds like a necessary part of real-world algorithm design. You can’t always have perfect accuracy if you are severely constrained by power.
Lalam: They show this tradeoff works: for any one alpha between one and delta, you get an O alpha log delta approximate dominating set in expectation in O˜log tau log alpha log delta rounds with only O˜log alpha awake complexity.
Tom: So we can tune the approximation quality by picking that parameter and see how much energy we save. It’s a lot of control there.
The paper's summary: Jane: Now let's look at the specific improvements they suggest beyond just that first result, because the paper suggests several ways to get even better performance on this problem. They are essentially showing how to engineer a better algorithm.
Lu: They present a generalized version of this approach using parameters p and q. This gives them an O pq log p delta approximate dominating set in expectation in O log p delta log q delta rounds, which lets you control the approximation factor by tuning those two parameters.
Tom: That’s a clear way to say you have levers to pull for both the approximation quality and the round complexity by selecting p and q. It moves beyond just one fixed result.
Meng: I'm interested in how they structure this generalized approach because it sounds like a more flexible framework for different types of graphs than just sticking to the simple set cover adaptation.
Lalam: They also show an awake-efficient version of the p, q MDS algorithm using two phases, Phase one and Phase two <ref:2608.19096#pg1>. The awake complexity of this whole thing is O log p delta plus log of q one times delta plus log p times log n times q two times delta.
Tom: That formula is interesting because it shows they can structure the computation in a way that separates the rounds into different stages, which allows them to manage the energy cost across those stages.
Jane: And when you set up those parameters specifically, if you pick p equals alpha, and q one and q two both equal two, the awake complexity simplifies to O log alpha delta multiplied by the logarithm of n.
Lu: That simplification is a good result because it shows a concrete way to achieve better energy bounds for a specific approximation quality. It’s a tangible engineering target.
Meng: So, if we want to be practical, what does that simplified complexity look like? Is it something we can actually run on our current hardware without massive overhead?
Tom: It means the awake complexity is O log alpha delta multiplied by the logarithm of n. That's much better than what was previously known for achieving an O alpha times the approximation factor.
Jane: That sounds promising because it shows a clearer path toward making these algorithms practical for real-world applications where resource constraints are tight.
Lu: They also suggest setting q two to be the maximum of two or log delta divided by logarithm of n to make those terms in the awake complexity bound equal, which optimizes the tradeoff between the approximation factor and energy cost.
Meng: Tuning a parameter to balance complexity is always a good move when you're trying to squeeze out performance from a system. It shows they’re thinking about optimization beyond just getting *a* working solution.
Tom: This whole paper, "Approximating Minimum Dominating Set with Few Awake Rounds," really shows that the awake complexity can be much smaller than the round complexity suggests, but achieving the absolute best theoretical bound seems to be an open problem for now.
Jane: So they’ve given us a lot of tools—the parameterized tradeoff control and the two-phase structure—to explore how we can deploy these algorithms with minimal energy expenditure.
The paper's improvements: Tom: So, wrapping up the whole discussion on "Approximating Minimum Dominating Set with Few Awake Rounds," the paper shows that you can have an O log delta approximation in expectation in O log2 delta rounds while keeping the awake complexity at O˜(log delta).
Jane: And they then showed a broader tradeoff where you can get better energy efficiency by weakening your approximation guarantee, and they gave us tools to tune parameters p and q to control this relationship precisely.
Lu: The main implication is that we can design algorithms for these distributed systems where the awake complexity is significantly lower than the round complexity, although achieving an O log delta approximation with o log delta awake complexity still seems like a very hard open problem.
Meng: For deployment, it means we have to accept that if you want low energy costs, you might need to settle for a slightly weaker approximation guarantee than what's theoretically possible.
Lalam: The paper "Approximating Minimum Dominating Set with Few Awake Rounds" provides a clear roadmap for how to explore the space of tradeoffs between accuracy and energy cost in these types of problems.
Tom: It’s a lot of tuning, but it gives us concrete levers we can use when designing our next distributed algorithm.
Jane: We should keep an eye on this work because it connects concepts from graph algorithms with energy-constrained computation in ways that could inspire new solutions elsewhere.
Conclusion: Tom: So, to wrap up this talk on "Approximating Minimum Dominating Set with Few Awake Rounds," we saw they found an O log delta approximation in expectation using O log2 delta rounds and a specific awake complexity of O˜log delta.
Jane: That’s the main result they’re highlighting, Tom. The naive question is, can you get better energy efficiency than what's currently known for finding this dominating set?
Lu: What makes it interesting is that they use a sleeping version of the SetCover algorithm to achieve that first O log delta approximation, and then they show a smoother tradeoff later on.
Meng: So if I’m thinking about deploying this on a real network, what does that mean for the actual running cost? Does O˜log delta awake complexity actually translate into something practical?
Lalam: It means that for certain graph sizes, say when delta is bigger than two log epsilon n, that extra complexity drops down to just O log delta. That makes it much cleaner to estimate the energy cost in those larger systems.
Tom: Exactly. And then they build this parameterized tradeoff where you can tune a parameter p and get an approximation factor of O alpha times the approximation factor with an awake complexity of O˜log alpha times log n.
Jane: It’s like you have a dial for accuracy, and turning that dial down gives you a huge drop in energy cost, but the paper also shows they can set up parameters to balance that out better.
Lu: They actually suggest setting one of those parameters, q two, to be the maximum of two or log delta divided by log n to make those terms in the awake complexity bound match up nicely.
Meng: Tuning a parameter like that just tells you how much control you have over what kind of algorithm you’re running. I'm still worried about that dependence on n in the complexity, though.
Lalam: The paper does flag that achieving a clean O log delta approximation with only o log delta awake complexity is still a hard open problem, even if we allow polynomially many rounds.
Tom: It seems they’ve given us some really useful tools for controlling the tradeoff between how good the result is and how much energy it takes to compute it.
Jane: That's what I'd say. It’s a lot of structure for a problem that feels so messy in practice.
Lu: Indeed. The exploration of these parameterized tradeoffs in "Approximating Minimum Dominating Set with Few Awake Rounds" opens up new ways to think about energy-aware algorithms on these networks.
Meng: So, we see how to balance accuracy and energy cost, but there’s still that big gap between the theoretical best and what's actually easy to implement.
Lalam: Exactly. And that gap is where the next set of papers will probably be worth watching if you want to push past those O log delta barriers.
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game