In this paper we present a simple but powerful subgraph sampling primitive that is applicable in a variety of computational models including dynamic graph streams (where the input graph is defined by a sequence of edge/hyperedge insertions and deletions) and distributed systems such as MapReduce. In the case of dynamic graph streams, we use this primitive to prove the following results:*

Matching:Our main result for matchings is that there exists anO~(k^{2}) space algorithm that returns the edges of a maximum matching on the assumption the cardinality is at mostk. The best previous algorithm usedO~(kn) space wherenis the number of vertices in the graph and we prove our result is optimal up to logarithmic factors. Our algorithm hasO~(1) update time. We also show that there exists anO~(n^{2}/α^{3}) space algorithm that returns an α-approximation for matchings of arbitrary size. In independent work, Assadi et al. (arXiv 2015) proved this is optimal and provided an alternative algorithm. We generalize our exact and approximate algorithms to weighted matching. While there has been a substantial amount of work on approximate matching in insert-only graph streams, these are the first non-trivial results in the dynamic setting.*

Vertex Cover and Hitting Set:There exists anO~(k^{d}) space algorithm that solves the minimum hitting set problem wheredis the cardinality of the input sets andkis an upper bound on the size of the minimum hitting set. We prove this is optimal up to logarithmic factors. Our algorithm hasO~(1) update time. The cased=2 corresponds to minimum vertex cover.Finally, we consider a larger family of parameterized problems (including

b-matching, disjoint paths, vertex coloring among others) for which our subgraph sampling primitive yields fast, small-space dynamic graph stream algorithms. We then show lower bounds for natural problems outside this family.

[ bib | Alternate Version | .pdf ] Back

*This file was generated by
bibtex2html 1.92.*