BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260918T082829Z
UID:Seminar-NESTiD-1156@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Othon Michail:MAILTO:Othon.Michail@liverpool.ac.uk
DTSTART:20221013T161500
DTEND:20221013T171500
SUMMARY:Durham-Liverpool synergy Series
DESCRIPTION:Christian Konrad: Dominating set in graph streams and beyond\n\nWe 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.\n \n1) 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.\n \n2) 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.\n \nWe 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.\n \nThis is based on joint work with Sanjeev Khanna and Cezar-Mihail Alexandru.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1156
LOCATION:
END:VEVENT
END:VCALENDAR