Testable Bounded Degree Graph Properties Are Random Order Streamable

Thursday, December 8, 2016 - 4:00pm to 5:00pm
Morteza Monemizadeh
Rutgers University

We study graph streaming problems. We transform known property testing algorithms into streaming ones. In particular, our main result is that for bounded degree graphs, any property that is constant-query testable in the adjacent list model can be solved with constant space in single-pass random order model. Our results are obtained by estimating the distribution of what are known as k-discs used in property testing methods, directly on a random order graph stream with constant space.

We also apply this approach to constant time approximation algorithms in the adjacency list model and get single-pass random order streaming algorithms for all of them. For example, we get constant-space single-pass random order streaming algorithms for (1,eps n)-approximating maximal matching to additive eps n error.

Our results are among the first known truly sublinear space graph streaming algorithms, while Omega(n) space is needed for many graph streaming problems (n is the number of nodes) and previous results typically use the semi-streaming model of O(n polylog(n)) space.

Joint work with S. Muthukrishnan, Pan Peng, Christian Sohler.