Dominating set in graph streams and beyond

13^th October 2022, 16:15
Christian Konrad
University of Bristol

Abstract

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, where entire sets arrive one-by-one, have received significant attention. Even though MDS can be viewed as a special case of Set Cover, MDS is harder to solve in the streaming setting since the input stream consists of individual edges rather than entire vertex-neighbourhoods, as in the case of Set Cover.

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.

We will also discuss recent developments regarding the edge-arrival version of the Set Cover problem, i.e., where sets are revealed as a sequence of tuples (S_i, u) in arbitrary order, indicating that element u is contained in set S_i.

This is based on joint work with Sanjeev Khanna and Cezar-Mihail Alexandru.