Testable bounded degree graph properties are random order streamable

Morteza Monemizadeh, S. Muthukrishnan, Pan Peng, Christian Sohler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

We study which property testing and sublinear time algorithms can be transformed into graph streaming algorithms for random order streams. Our main result is that for bounded degree graphs, any property that is constant-query testable in the adjacency list model can be tested with constant space in a single-pass in random order streams. Our result is obtained by estimating the distribution of local neighborhoods of the vertices on a random order graph stream using constant space. We then show that our approach can also be applied to constant time approximation algorithms for bounded degree graphs in the adjacency list model: As an example, we obtain a constant-space single-pass random order streaming algorithms for approximating the size of a maximum matching with additive error ∈n (n is the number of nodes). Our result establishes for the first time that a large class of sublinear algorithms can be simulated in random order streams, while Ω (n) space is needed for many graph streaming problems for adversarial orders.

Original languageEnglish (US)
Title of host publication44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
EditorsAnca Muscholl, Piotr Indyk, Fabian Kuhn, Ioannis Chatzigiannakis
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770415
DOIs
StatePublished - Jul 1 2017
Event44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 - Warsaw, Poland
Duration: Jul 10 2017Jul 14 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume80
ISSN (Print)1868-8969

Other

Other44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
Country/TerritoryPoland
CityWarsaw
Period7/10/177/14/17

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Constant-time approximation algorithms
  • Graph property testing
  • Graph streaming algorithms

Fingerprint

Dive into the research topics of 'Testable bounded degree graph properties are random order streamable'. Together they form a unique fingerprint.

Cite this