Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Standard

Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. / Chitnis, Rajesh; Cormode, Graham; Esfandiari, Hossein; Hajiaghayi, MohammadTaghi; McGregor, Andrew; Monemizadeh, Morteza; Vorotnikova, Sofya.

Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms. ed. / Robert Krauthgamer . Society for Industrial and Applied Mathematics (SIAM), 2016. p. 1326-1344 (The Annual ACM - SIAM Symposium on Discrete Algorithms. Proceedings).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Harvard

Chitnis, R, Cormode, G, Esfandiari, H, Hajiaghayi, M, McGregor, A, Monemizadeh, M & Vorotnikova, S 2016, Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. in R Krauthgamer (ed.), Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms. The Annual ACM - SIAM Symposium on Discrete Algorithms. Proceedings, Society for Industrial and Applied Mathematics (SIAM), pp. 1326-1344, Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, VA, United States, 10/01/16. https://doi.org/10.1137/1.9781611974331.ch92

APA

Chitnis, R., Cormode, G., Esfandiari, H., Hajiaghayi, M., McGregor, A., Monemizadeh, M., & Vorotnikova, S. (2016). Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. In R. Krauthgamer (Ed.), Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1326-1344). (The Annual ACM - SIAM Symposium on Discrete Algorithms. Proceedings). Society for Industrial and Applied Mathematics (SIAM). https://doi.org/10.1137/1.9781611974331.ch92

Vancouver

Chitnis R, Cormode G, Esfandiari H, Hajiaghayi M, McGregor A, Monemizadeh M et al. Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. In Krauthgamer R, editor, Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics (SIAM). 2016. p. 1326-1344. (The Annual ACM - SIAM Symposium on Discrete Algorithms. Proceedings). https://doi.org/10.1137/1.9781611974331.ch92

Author

Chitnis, Rajesh ; Cormode, Graham ; Esfandiari, Hossein ; Hajiaghayi, MohammadTaghi ; McGregor, Andrew ; Monemizadeh, Morteza ; Vorotnikova, Sofya. / Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms. editor / Robert Krauthgamer . Society for Industrial and Applied Mathematics (SIAM), 2016. pp. 1326-1344 (The Annual ACM - SIAM Symposium on Discrete Algorithms. Proceedings).

Bibtex

@inproceedings{f6fcb26f5e034791b605c126c309d04d,
title = "Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams",
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. (SODA 2016) proved this approximation algorithm is optimal and provided an alternative algorithm. We generalize our exact and approximate algorithms to weighted matching. For graphs with low arboricity such as planar graphs, the space required for constant approximation can be further reduced. While there has been a substantial amount of work on approximate matching in insert-only graph streams, these are the first nontrivial 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.",
author = "Rajesh Chitnis and Graham Cormode and Hossein Esfandiari and MohammadTaghi Hajiaghayi and Andrew McGregor and Morteza Monemizadeh and Sofya Vorotnikova",
year = "2016",
month = jan,
day = "10",
doi = "10.1137/1.9781611974331.ch92",
language = "English",
series = "The Annual ACM - SIAM Symposium on Discrete Algorithms. Proceedings",
publisher = "Society for Industrial and Applied Mathematics (SIAM)",
pages = "1326--1344",
editor = "{Krauthgamer }, Robert",
booktitle = "Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms",
note = "Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016) ; Conference date: 10-01-2016 Through 12-01-2016",

}

RIS

TY - GEN

T1 - Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams

AU - Chitnis, Rajesh

AU - Cormode, Graham

AU - Esfandiari, Hossein

AU - Hajiaghayi, MohammadTaghi

AU - McGregor, Andrew

AU - Monemizadeh, Morteza

AU - Vorotnikova, Sofya

PY - 2016/1/10

Y1 - 2016/1/10

N2 - 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 Õ(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 Õ(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 Õ(1) update time. We also show that there exists an Õ(n2/α3) space algorithm that returns an α-approximation for matchings of arbitrary size. In independent work, Assadi et al. (SODA 2016) proved this approximation algorithm is optimal and provided an alternative algorithm. We generalize our exact and approximate algorithms to weighted matching. For graphs with low arboricity such as planar graphs, the space required for constant approximation can be further reduced. While there has been a substantial amount of work on approximate matching in insert-only graph streams, these are the first nontrivial results in the dynamic setting.•Vertex Cover and Hitting Set: There exists an Õ(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 Õ(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.

AB - 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 Õ(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 Õ(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 Õ(1) update time. We also show that there exists an Õ(n2/α3) space algorithm that returns an α-approximation for matchings of arbitrary size. In independent work, Assadi et al. (SODA 2016) proved this approximation algorithm is optimal and provided an alternative algorithm. We generalize our exact and approximate algorithms to weighted matching. For graphs with low arboricity such as planar graphs, the space required for constant approximation can be further reduced. While there has been a substantial amount of work on approximate matching in insert-only graph streams, these are the first nontrivial results in the dynamic setting.•Vertex Cover and Hitting Set: There exists an Õ(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 Õ(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.

U2 - 10.1137/1.9781611974331.ch92

DO - 10.1137/1.9781611974331.ch92

M3 - Conference contribution

T3 - The Annual ACM - SIAM Symposium on Discrete Algorithms. Proceedings

SP - 1326

EP - 1344

BT - Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Krauthgamer , Robert

PB - Society for Industrial and Applied Mathematics (SIAM)

T2 - Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)

Y2 - 10 January 2016 through 12 January 2016

ER -