License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.131
URN: urn:nbn:de:0030-drops-74782
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7478/
Go to the corresponding LIPIcs Volume Portal

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

Testable Bounded Degree Graph Properties Are Random Order Streamable

pdf-format:
LIPIcs-ICALP-2017-131.pdf (0.5 MB)

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 epsilon 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 Omega(n) space is needed for many graph streaming problems for adversarial orders.

BibTeX - Entry

@InProceedings{monemizadeh_et_al:LIPIcs:2017:7478,
  author =	{Morteza Monemizadeh and S. Muthukrishnan and Pan Peng and Christian Sohler},
  title =	{{Testable Bounded Degree Graph Properties Are Random Order Streamable}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{131:1--131:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7478},
  URN =		{urn:nbn:de:0030-drops-74782},
  doi =		{10.4230/LIPIcs.ICALP.2017.131},
  annote =	{Keywords: Graph streaming algorithms, graph property testing, constant-time approximation algorithms}
}

Keywords: Graph streaming algorithms, graph property testing, constant-time approximation algorithms
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

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