2026-07-23T13:56:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15689 2024-03-06T10:55:57Z ddc:004 open_access

Optimal Bounds for Dominating Set in Graph Streams Khanna, Sanjeev Konrad, Christian Streaming algorithms communication complexity information complexity dominating set We resolve the space complexity of one-pass streaming algorithms for Minimum Dominating Set (MDS) in both insertion-only and insertion-deletion streams (up to poly-logarithmic factors) where an input graph is revealed by a sequence of edge updates. Recently, streaming algorithms for the related Set Cover problem have received significant attention. Even though MDS can be viewed as a special case of Set Cover, it is however harder to solve in the streaming setting since the input stream consists of individual edges rather than entire vertex-neighborhoods, as is the case in Set Cover. We prove the following results (n is the number of vertices of the input graph): 1) In insertion-only streams, we give a one-pass semi-streaming algorithm (meaning Õ(n) space) with approximation factor Õ(√n). We also prove that every one-pass streaming algorithm with space o(n) has an approximation factor of Ω(n/log n). Combined with a result by [Assadi et al., STOC'16] for Set Cover which, translated to MDS, shows that space Θ̃(n² / α) is necessary and sufficient for computing an α-approximation for every α = o(√n), this completely settles the space requirements for MDS in the insertion-only setting. 2) In insertion-deletion streams, we prove that space Ω(n² / (α log n)) is necessary for every approximation factor α ≤ Θ(n / log³ n). Combined with the Set Cover algorithm of [Assadi et al., STOC'16], which can be adapted to MDS even in the insertion-deletion setting to give an α-approximation in Õ(n² / α) space, this completely settles the space requirements for MDS in the insertion-deletion setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sanjeev Khanna and Christian Konrad 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.93 urn:nbn:de:0030-drops-156894 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.93 eng https://creativecommons.org/licenses/by/4.0/legalcode