The Library
Kernelization via sampling with applications to dynamic graph streams
Tools
Tools
Tools
Chitnis, Rajesh, Cormode, Graham, Esfandiari, Hossein, Hajiaghayi, Mohammad Taghi, McGregor, Andrew, Monemizadeh, Morteza and Vorotnikova, Sofya (2016) Kernelization via sampling with applications to dynamic graph streams. In: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016, Arlington, Virginia, 10-12 Jan 2016. Published in: Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms pp. 1326-1344. ISBN 9781611974331. doi:10.1137/1.9781611974331.ch92
![[img]](https://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
WRAP_vcsampling_.pdf - Accepted Version - Requires a PDF viewer. Download (1335Kb) |
Official URL: https://doi.org/10.1137/1.9781611974331.ch92
Abstract
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 an O~(k2) space algorithm that returns the edges of a maximum matching on the assumption the cardinality is at most k. The best previous algorithm used O~(kn) space where n is the number of vertices in the graph and we prove our result is optimal up to logarithmic factors. Our algorithm has O~(1) update time. We also show that there exists an O~(n2/α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 an O~(kd) space algorithm that solves the minimum hitting set problem where d is the cardinality of the input sets and k is an upper bound on the size of the minimum hitting set. We prove this is optimal up to logarithmic factors. Our algorithm has O~(1) update time. The case d=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.
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
| Library of Congress Subject Headings (LCSH): | Graph theory, Kernel functions | ||||||
| Journal or Publication Title: | Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms | ||||||
| Publisher: | SIAM | ||||||
| ISBN: | 9781611974331 | ||||||
| Official Date: | 2016 | ||||||
| Dates: |
|
||||||
| Page Range: | pp. 1326-1344 | ||||||
| DOI: | 10.1137/1.9781611974331.ch92 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Date of first compliant deposit: | 3 December 2015 | ||||||
| Date of first compliant Open Access: | 3 December 2015 | ||||||
| Funder: | Israeli Centers of Research Excellence (I-CORE), European Research Council (ERC), Yahoo! Research Labs, Royal Society (Great Britain). Wolfson Research Merit Award (RSWRMA), National Science Foundation (U.S.) (NSF), United States. Office of Naval Research, United States. Defense Advanced Research Projects Agency (DARPA), United States. Air Force. Office of Scientific Research (AFOSR), Google (Firm), Czech Science Foundation (CSF) | ||||||
| Grant number: | ERC-2014-CoG 647557 (ERC), 1053605 (NSF), CCF-1161626 (NSF), IIS-1546108 (NSF), N000141110662 (ONR), FA9550-12-1-0423 (DAPRA/AFOSR), CCF-0953754 (NSF), CCF-1320719 (NSF), 14-10003S (CSF) | ||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016 | ||||||
| Type of Event: | Conference | ||||||
| Location of Event: | Arlington, Virginia | ||||||
| Date(s) of Event: | 10-12 Jan 2016 | ||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
