Testable bounded degree graph properties are random order streamable

DOI10.4230/LIPICS.ICALP.2017.131MaRDI QIDQ5111463zbMATH OpenOpenAlexFDO

Authors

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1707.07334

zbMATH Keywords

bounded-degree graphsgraph property testingconstant-time approximation algorithmsgraph-streaming algorithms

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25)

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 $epsilonn$ ($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.

Recommendations

• Estimating graph parameters from random order streams
• Approximating matching size from random streams
• scientific article; zbMATH DE number 1559556
• Property testing in bounded degree graphs
• Streaming Lower Bounds for Approximating MAX-CUT

Cited in

(5)

• Best-order streaming model
• Estimating graph parameters from random order streams
• Structural results on matching estimation with applications to streaming
• scientific article; zbMATH DE number 7758318 (Why is no real title available?)
• (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond

This page was built for publication: Testable bounded degree graph properties are random order streamable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111463)