Toward Tight Space-Approximation Tradeoffs for Dominating Set in Adjacency-List Streaming

Abstract

We study the minimum dominating set MDS problem in the adjacency-list arrival streaming model (AL), in which vertices arrive one at a time, revealing their entire closed neighborhood at arrival. The MDS has been studied in the classical edge-arrival streaming model by Khanna and Konrad (2022), building on Assadi, Khanna, and Li (2016), who establish a sharp threshold at \tilde O(\sqrt{n})-approximation in semi-streaming space for any n-vertex graph G. However, the AL model is more informative and its space complexity has not yet been understood. We show that the \tilde O(\sqrt{n}) threshold does not persist in AL and present a space-approximation tradeoff. Specifically, we prove the following: (1) For any space budget t \in [n], there is a one-pass AL algorithm using O(t \log \log n) space that outputs a dominating set of size O(n \log^2 n/t \cdot \OPT(G)). For t = n, there is a randomized one-pass semi-streaming AL algorithm which outputs a dominating set of size O(\log^2n \cdot \OPT(G)) together with a valid cover certificate. (2) Any exact one-pass AL algorithm for MDS requires \Omega(n) space. We also develop the notion of AL-realizable reductions to prove lower bounds, and establish exact one-pass algorithms for structured graph families. Together, these results show that AL has algorithmic consequences different from other classical streaming models. The thesis presents initial results for AL space-approximation and directions for future work.