arXiv:2608.19096v2 Announce Type: replace 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 \Delta)$-approximation algorithms (in expectation) for MDS that run in $O(\log^2 \Delta)$ rounds, all of these have $\Omega(\log^2 \Delta)$ awake complexity. Whether this awake complexity can be improved is the question that drives our work. We present the first $O(\log \Delta)$-approximation algorithm for MDS with $O(\log \Delta)$ awake complexity. The approximation guarantee holds in expectation, and the algorithm runs in $O(\log^2\Delta)$ rounds. We can reduce the awake complexity further, but at the cost of approximation: we present, for any $1<\alpha\le\min\{\Delta,\log n\}$, an algorithm in the sleeping CONGEST model that computes an $\tilde{O}(\alpha\log_\alpha\Delta)$-approximate dominating set in expectation in $\tilde{O}(\log\Delta\cdot \log_{\alpha} \Delta)$ rounds with $\tilde{O}(\log_{\alpha} \Delta)$ awake complexity. Our results depend on a generalization of the CONGEST model Set Cover algorithm of Grunau, Mitrovi\'c, Rubinfeld, and Vakilian (SODA 2020) that we develop. This generalization computes an $O(p\cdot q\cdot\log_p\Delta)$-approximate dominating set in $O(\log_p\Delta\cdot\log_q\Delta)$ rounds for parameters $1Source：https://arxiv.org/abs/2608.19096
My favorites