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 @math ( @math 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 @math space is needed for many graph streaming problems for adversarial orders.
@cite_27 initiated the study of property testing in streaming model, and they gave efficient testers for some properties of a sequence of data items (rather than graphs as we consider here). Bury and Schwiegelshohn @cite_16 gave a lower bound of @math on the space complexity of any algorithm that @math -approximates the size of maximum matching in adversarial streams. @cite_10 showed that in random streams, @math space is necessary to distinguish if a graph is bipartite or @math -far from being bipartite. Previous work has extensively studied streaming graph algorithms in both the insertion-only and dynamic models, see the recent survey @cite_18 .
@cite_27 @cite_16 @cite_10 @cite_18
1558846832 1617753329 1824295098 2016289973
We consider the tasks of testing and spot-checking for data streams . These testers and spot-checkers are potentially useful in real-time or near real-time applications that process huge data sets. Crucial aspects of the computational model include the space complexity of the testers and spot-checkers (ideally much lower than the size of the input stream) and the number of passes that the tester or spot-checker must make over the input stream (ideally one, because the original stream may be too large to store for a second pass). This paper presents an algorithm for estimating the weight of a maximum weighted matching by augmenting any estimation routine for the size of an unweighted matching. The algorithm is implementable in any streaming model including dynamic graph streams. We also give the first constant estimation for the maximum matching size in a dynamic graph stream for planar graphs (or any graph with bounded arboricity) using ( O (n^ 4 5 ) ) space which also extends to weighted matching. Using previous results by Kapralov, Khanna, and Sudan (2014) we obtain a polylog(n) approximation for general graphs using polylog(n) space in random order streams, respectively. In addition, we give a space lower bound of Ω(n1 − e) for any randomized algorithm estimating the size of a maximum matching up to a 1 + O(e) factor for adversarial streams. We consider the problem of estimating the value of max cut in a graph in the streaming model of computation. At one extreme, there is a trivial 2-approximation for this problem that uses only O(log n) space, namely, count the number of edges and output half of this value as the estimate for max cut value. On the other extreme, if one allows O(n) space, then a near-optimal solution to the max cut value can be obtained by storing an O(n)-size sparsifier that essentially preserves the max cut. An intriguing question is if poly-logarithmic space suffices to obtain a non-trivial approximation to the max-cut value (that is, beating the factor 2). It was recently shown that the problem of estimating the size of a maximum matching in a graph admits a non-trivial approximation in poly-logarithmic space. Our main result is that any streaming algorithm that breaks the 2-approximation barrier requires [EQUATION] space even if the edges of the input graph are presented in random order. Our result is obtained by exhibiting a distribution over graphs which are either bipartite or 1 2-far from being bipartite, and establishing that [EQUATION] space is necessary to differentiate between these two cases. Thus as a direct corollary we obtain that [EQUATION] space is also necessary to test if a graph is bipartite or 1 2-far from being bipartite. We also show that for any e > 0, any streaming algorithm that obtains a (1 + e)-approximation to the max cut value when edges arrive in adversarial order requires n1−O(e) space, implying that Ω(n) space is necessary to obtain an arbitrarily good approximation to the max cut value. Over the last decade, there has been considerable interest in designing algorithms for processing massive graphs in the data stream model. The original motivation was two-fold: a) in many applications, the dynamic graphs that arise are too large to be stored in the main memory of a single machine and b) considering graph problems yields new insights into the complexity of stream computation. However, the techniques developed in this area are now finding applications in other areas including data structures for dynamic graphs, approximation algorithms, and distributed and parallel computation. We survey the state-of-the-art results; identify general techniques; and highlight some simple algorithms that illustrate basic ideas.