TY - GEN
T1 - Testable bounded degree graph properties are random order streamable
AU - Monemizadeh, Morteza
AU - Muthukrishnan, S.
AU - Peng, Pan
AU - Sohler, Christian
N1 - Publisher Copyright:
© Morteza Monemizadeh, S. Muthukrishnan, Pan Peng, and Christian Sohler;.
PY - 2017/7/1
Y1 - 2017/7/1
N2 - 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.
AB - 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.
KW - Constant-time approximation algorithms
KW - Graph property testing
KW - Graph streaming algorithms
UR - http://www.scopus.com/inward/record.url?scp=85027275236&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85027275236&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2017.131
DO - 10.4230/LIPIcs.ICALP.2017.131
M3 - Conference contribution
AN - SCOPUS:85027275236
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
A2 - Muscholl, Anca
A2 - Indyk, Piotr
A2 - Kuhn, Fabian
A2 - Chatzigiannakis, Ioannis
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
Y2 - 10 July 2017 through 14 July 2017
ER -