Abstract
We resolve the space complexity of onepass streaming algorithms for Minimum Dominating Set (MDS) in both insertiononly and insertiondeletion streams (up to polylogarithmic 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 vertexneighborhoods, as is the case in Set Cover.
We prove the following results (n is the number of vertices of the input graph):
1) In insertiononly streams, we give a onepass semistreaming algorithm (meaning Õ(n) space) with approximation factor Õ(√n). We also prove that every onepass 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 insertiononly setting.
2) In insertiondeletion 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 insertiondeletion setting to give an αapproximation in Õ(n² / α) space, this completely settles the space requirements for MDS in the insertiondeletion setting.
BibTeX  Entry
@InProceedings{khanna_et_al:LIPIcs.ITCS.2022.93,
author = {Khanna, Sanjeev and Konrad, Christian},
title = {{Optimal Bounds for Dominating Set in Graph Streams}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {93:193:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15689},
URN = {urn:nbn:de:0030drops156894},
doi = {10.4230/LIPIcs.ITCS.2022.93},
annote = {Keywords: Streaming algorithms, communication complexity, information complexity, dominating set}
}
Keywords: 

Streaming algorithms, communication complexity, information complexity, dominating set 
Collection: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022) 
Issue Date: 

2022 
Date of publication: 

25.01.2022 