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.
In the framework of @math -bounded graph property testing, it is now known that many interesting properties are constant-query testable in the adjacency list model, including @math -edge connectivity, cycle-freeness, subgraph-freeness @cite_11 , @math -vertex connectivity @cite_28 , minor-freeness @cite_2 @cite_5 , matroids related properties @cite_30 @cite_0 , hyperfinite properties @cite_24 , subdivision-freeness @cite_13 . Constant-time approximation algorithms in @math -bounded graphs are known to exist for a number of fundamental optimization problems, including @math -approximating the weight of minimum spanning tree @cite_15 , @math -approximating the size of maximal maximum matching @cite_17 @cite_3 , @math -approximating the minimum vertex cover size @cite_12 @cite_29 @cite_1 , @math -approximating the minimum dominating set size @cite_12 @cite_17 . For @math -bounded minor-free graphs, there are constant-time @math -approximation algorithms for the size of minimum vertex cover, minimum dominating set and maximum independent set @cite_2 .
@cite_30 @cite_28 @cite_29 @cite_1 @cite_17 @cite_3 @cite_0 @cite_24 @cite_2 @cite_5 @cite_15 @cite_13 @cite_12 @cite_11
2950966800 2116953739 2109330224 2072015757 1997480274 2022140055 2082227928 2902263058 1980155175 1980816908
A graph @math is called @math -full if @math contains a subgraph @math of @math edges such that, for any non-empty @math , @math holds. Here, @math denotes the set of vertices incident to @math . It is known that the family of edge sets of @math -full graphs forms a family of matroid, known as the sparsity matroid of @math . In this paper, we give a constant-time approximation algorithm for the rank of the sparsity matroid of a degree-bounded undirected graph. This leads to a constant-time tester for @math -fullness in the bounded-degree model, (i.e., we can decide with high probability whether an input graph satisfies a property @math or far from @math ). Depending on the values of @math and @math , it can test various properties of a graph such as connectivity, rigidity, and how many spanning trees can be packed. Based on this result, we also propose a constant-time tester for @math -edge-connected-orientability in the bounded-degree model, where an undirected graph @math is called @math -edge-connected-orientable if there exists an orientation @math of @math with a vertex @math such that @math contains @math arc-disjoint dipaths from @math to each vertex @math and @math arc-disjoint dipaths from each vertex @math to @math . A tester is called a one-sided error tester for @math if it always accepts a graph satisfying @math . We show, for @math and (proper) @math , any one-sided error tester for @math -fullness and @math -edge-connected-orientability requires @math queries. We give a nearly optimal sublinear-time algorithm for approximating the size of a minimum vertex cover in a graph G. The algorithm may query the degree deg(v) of any vertex v of its choice, and for each 1 ≤ i ≤ deg(v), it may ask for the ith neighbor of v. Letting VCopt(G) denote the minimum size of vertex cover in G, the algorithm outputs, with high constant success probability, an estimate [EQUATION] such that [EQUATION], where e is a given additive approximation parameter. We refer to such an estimate as a (2, e)-estimate. The query complexity and running time of the algorithm are O([EQUATION] · poly(1 e)), where d denotes the average vertex degree in the graph. The best previously known sublinear algorithm, of (STOC 2009), has query complexity and running time O(d4 e2), where d is the maximum degree in the graph. Given the lower bound of Ω(d) (for constant e) for obtaining such an estimate (with any constant multiplicative factor) due to Parnas and Ron (TCS 2007), our result is nearly optimal. In the case that the graph is dense, that is, the number of edges is Θ(n2), we consider another model, in which the algorithm may ask, for any pair of vertices u and v, whether there is an edge between u and v. We show how to adapt the algorithm that uses neighbor queries to this model and obtain an algorithm that outputs a (2, e)-estimate of the size of a minimum vertex cover whose query complexity and running time are O(n) · poly(1 e). We present a technique for transforming classical approximation algorithms into constant-time algorithms that approximate the size of the optimal solution. Our technique is applicable to a certain subclass of algorithms that compute a solution in a constant number of phases. The technique is based on greedily considering local improvements in random order.The problems amenable to our technique include vertex cover, maximum matching, maximum weight matching, set cover, and minimum dominating set. For example, for maximum matching, we give the first constant-time algorithm that for the class of graphs of degree bounded by d, computes the maximum matching size to within epsivn, for any epsivn > 0, where n is the number of nodes in the graph. The running time of the algorithm is independent of n, and only depends on d and epsiv. We study constant-time approximation algorithms for bounded-degree graphs, which run in time independent of the number of vertices @math . We present an algorithm that decides whether a vertex is contained in a some fixed maximal independent set with expected query complexity @math , where @math is the degree bound. Using this algorithm, we show constant-time approximation algorithms with certain multiplicative error and additive error @math for many other problems, e.g., the maximum matching problem, the minimum vertex cover problem, and the minimum set cover problem, that run exponentially faster than existing algorithms with respect to @math and @math . Our approximation algorithm for the maximum matching problem can be transformed to a two-sided error tester for the property of having a perfect matching. On the contrary, we show that every one-sided error tester for the property requires at least @math queries. For a function @math on a finite set V with f(?)=f(V)=0, a digraph D=(V,A) is called f-connected if it satisfies the f-cut condition, that is, ? D (X)?f(X) for any X⊆V, where ? D (X) is the number of arcs from X to V?X. We show that, for any crossing supermodular function f, the f-connectivity can be tested with a constant number of queries in the general digraph model with average degree bound. As immediate corollaries, we obtain constant-time testers for k-edge-connectivity, rooted-(k,l)-edge-connectivity, and the property of having k arc-disjoint arborescences. We also give a corresponding result for the undirected case. We present an algorithm for testing the k-vertex-connectivity of graphs with the given maximum degree. The time complexity of the algorithm is independent of the number of vertices and edges of graphs. Fixed degree bound d, a graph G with n vertices and a maximum degree at most d is called e-far from k-vertex-connectivity when at least @math edges must be added to or removed from G to obtain a k-vertex-connected graph with a maximum degree at most d. The algorithm always accepts every graph that is k-vertex-connected and rejects every graph that is e-far from k-vertex-connectivity with a probability of at least 2 3. The algorithm runs in @math time (c>1 is a constant) for (k−1)-vertex-connected graphs, and in @math time (c>1 is a constant) for general graphs. It is the first constant-time k-vertex-connectivity testing algorithm for general k≥4. We present a probabilistic algorithm that, given a connected graph G (represented by adjacency lists) of average degree d, with edge weights in the set 1,...,w , and given a parameter @math , estimates in time @math the weight of the minimum spanning tree (MST) of G with a relative error of at most @math . Note that the running time does not depend on the number of vertices in G. We also prove a nearly matching lower bound of @math on the probe and time complexity of any approximation algorithm for MST weight. The essential component of our algorithm is a procedure for estimating in time @math the number of connected components of an unweighted graph to within an additive error of @math . (This becomes @math for @math .) The time bound is shown to be tight up to within the @math factor. Our connected-components algorithm picks @math vertices in the graph and then grows "local spanning trees" whose sizes are specified by a stochastic process. From the local information collected in this way, the algorithm is able to infer, with high confidence, an estimate of the number of connected components. We then show how estimates on the number of components in various subgraphs of G can be used to estimate the weight of its MST. For a given graph G over n vertices, let OPT"G denote the size of an optimal solution in G of a particular minimization problem (e.g., the size of a minimum vertex cover). A randomized algorithm will be called an @a-approximation algorithm with an additive error for this minimization problem if for any given additive error parameter @e>0 it computes a value [email protected]? such that, with probability at least 2 3, it holds that OPT"[email protected][email protected][email protected][email protected]@?OPT"[email protected] Assume that the maximum degree or average degree of G is bounded. In this case, we show a reduction from local distributed approximation algorithms for the vertex cover problem to sublinear approximation algorithms for this problem. This reduction can be modified easily and applied to other optimization problems that have local distributed approximation algorithms, such as the dominating set problem. We also show that for the minimum vertex cover problem, the query complexity of such approximation algorithms must grow at least linearly with the average degree [email protected]? of the graph. This lower bound holds for every multiplicative factor @a and small constant @e as long as [email protected]?=O(n @a). In particular this means that for dense graphs it is not possible to design an algorithm whose complexity is o(n). We further develop the study of testing graph properties as initiated by Goldreich, Goldwasser and Ron. Loosely speaking, given an oracle access to a graph, we wish to distinguish the case when the graph has a pre-determined property from the case when it is far from having this property. Whereas they view graphs as represented by their adjacency matrix and measure the distance between graphs as a fraction of all possible vertex pairs, we view graphs as represented by bounded-length incidence lists and measure the distance between graphs as a fraction of the maximum possible number of edges. Thus, while the previous model is most appropriate for the study of dense graphs, our model is most appropriate for the study of bounded-degree graphs. In particular, we present randomized algorithms for testing whether an unknown bounded-degree graph is connected, k-connected (for k > 1), cycle-free and Eulerian. Our algorithms work in time polynomial in 1 e, always accept the graph when it has the tested property, and reject with high probability if the graph is s-far from having the property. For example, the 2-connectivity algorithm rejects (with high probability) any N-vertex d-degree graph for which more than edN edges need to be added in order to make the graph 2-edge-connected. In addition we prove lower bounds of Ω(√N) on the query complexity of testing algorithms for the bipartite and expander properties.