License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.9
URN: urn:nbn:de:0030-drops-156054
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15605/
Go to the corresponding LIPIcs Volume Portal

Assadi, Sepehr ; Shah, Vihan

An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams

pdf-format:
LIPIcs-ITCS-2022-9.pdf (0.9 MB)

Abstract

We present an algorithm for the maximum matching problem in dynamic (insertion-deletions) streams with asymptotically optimal space: for any n-vertex graph, our algorithm with high probability outputs an α-approximate matching in a single pass using O(n²/α³) bits of space.

A long line of work on the dynamic streaming matching problem has reduced the gap between space upper and lower bounds first to n^{o(1)} factors [Assadi-Khanna-Li-Yaroslavtsev; SODA 2016] and subsequently to polylog factors [Dark-Konrad; CCC 2020]. Our upper bound now matches the Dark-Konrad lower bound up to O(1) factors, thus completing this research direction.

Our approach consists of two main steps: we first (provably) identify a family of graphs, similar to the instances used in prior work to establish the lower bounds for this problem, as the only "hard" instances to focus on. These graphs include an induced subgraph which is both sparse and contains a large matching. We then design a dynamic streaming algorithm for this family of graphs which is more efficient than prior work. The key to this efficiency is a novel sketching method, which bypasses the typical loss of polylog(n)-factors in space compared to standard L₀-sampling primitives, and can be of independent interest in designing optimal algorithms for other streaming problems.

BibTeX - Entry

@InProceedings{assadi_et_al:LIPIcs.ITCS.2022.9,
  author =	{Assadi, Sepehr and Shah, Vihan},
  title =	{{An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{9:1--9:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15605},
  URN =		{urn:nbn:de:0030-drops-156054},
  doi =		{10.4230/LIPIcs.ITCS.2022.9},
  annote =	{Keywords: Graph streaming algorithms, Sketching, Maximum matching}
}

Keywords: Graph streaming algorithms, Sketching, Maximum matching
Collection: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Issue Date: 2022
Date of publication: 25.01.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI