2026-08-15T16:30:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12939 2024-03-06T10:51:08Z ddc:004 open_access

Approximating k-Connected m-Dominating Sets Nutov, Zeev k-connected graph m-dominating set approximation algorithm rooted subset k-connectivity subset k-connectivity A subset S of nodes in a graph G is a k-connected m-dominating set ((k,m)-cds) if the subgraph G[S] induced by S is k-connected and every v ∈ V⧵S has at least m neighbors in S. In the k-Connected m-Dominating Set ((k,m)-CDS) problem the goal is to find a minimum weight (k,m)-cds in a node-weighted graph. For m ≥ k we obtain the following approximation ratios. For general graphs our ratio O(k ln n) improves the previous best ratio O(k² ln n) of [Z. Nutov, 2018] and matches the best known ratio for unit weights of [Z. Zhang et al., 2018]. For unit disk graphs we improve the ratio O(k ln k) of [Z. Nutov, 2018] to min{m/(m-k),k^{2/3}} ⋅ O(ln² k) - this is the first sublinear ratio for the problem, and the first polylogarithmic ratio O(ln² k)/ε when m ≥ (1+ε)k; furthermore, we obtain ratio min{m/(m-k), √k} ⋅ O(ln² k) for uniform weights. These results are obtained by showing the same ratios for the Subset k-Connectivity problem when the set of terminals is an m-dominating set. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zeev Nutov 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.73 urn:nbn:de:0030-drops-129392 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.73 eng https://creativecommons.org/licenses/by/3.0/legalcode