Optimal Bounds for Dominating Set in Graph Streams
| Autor: | Khanna, Sanjeev, Konrad, Christian |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: | |
| DOI: | 10.4230/lipics.itcs.2022.93 |
| Popis: | 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 O��(n) space) with approximation factor O��(���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 O��(n�� / ��) space, this completely settles the space requirements for MDS in the insertion-deletion setting. LIPIcs, Vol. 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 93:1-93:23 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|