A New Approximation Algorithm for Minimum-Weight (1,m)–Connected Dominating Set

Abstract

Consider a graph with nonnegative node weight. A vertex subset is called a CDS (connected dominating set) if every other node has at least one neighbor in the subset and the subset induces a connected subgraph. Furthermore, if every other node has at least m neighbors in the subset, then the node subset is called a (1,𝑚) CDS. The minimum-weight (1,𝑚) CDS problem aims at finding a (1,𝑚) CDS with minimum total node weight. In this paper, we present a new polynomial-time approximation algorithm for this problem, which improves previous ratio by a factor of 2/3. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grant U20A2068] and the National Science Foundation [Grant III-1907472]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0306) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2023.0306). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.