Space Optimal Vertex Cover in Dynamic Streams
Authors:
Kheeran K. Naidu, Vihan Shah.
Conference:
International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'22)
Abstract:
We optimally resolve the space complexity for the problem of finding an α-approximate minimum vertex cover (αMVC) in dynamic graph streams.
We give a randomised algorithm for αMVC which uses O(n^2/α^2) bits of space matching Dark and Konrad's lower bound [CCC 2020] up to constant factors.
By computing a random greedy matching, we identify `easy' instances of the problem which can trivially be solved by returning the entire vertex set. The
remaining `hard' instances, then have sparse induced subgraphs which we exploit to get our space savings and solve αMVC.
Achieving these types of optimality results is crucial for providing a complete understanding of a problem, and it has been gaining interest within the dynamic graph streaming community. For connectivity, Nelson and Yu [SODA 2019] improved the lower bound showing that Ω(n log^3 n) bits of space is necessary while Ahn, Guha, and McGregor [SODA 2012] has shown that O(n log^3 n) bits is sufficient. For finding an α-approximate maximum matching, the upper bound was improved by Assadi and Shah [ITCS 2022] showing that O(n^2/α^3) bits is sufficient while Dark and Konrad [CCC 2020] has shown that Ω(n^2/α^3) bits is necessary. The space complexity, however, still remains unresolved for many other dynamic graph streaming problems where further improvements can still be made.
Achieving these types of optimality results is crucial for providing a complete understanding of a problem, and it has been gaining interest within the dynamic graph streaming community. For connectivity, Nelson and Yu [SODA 2019] improved the lower bound showing that Ω(n log^3 n) bits of space is necessary while Ahn, Guha, and McGregor [SODA 2012] has shown that O(n log^3 n) bits is sufficient. For finding an α-approximate maximum matching, the upper bound was improved by Assadi and Shah [ITCS 2022] showing that O(n^2/α^3) bits is sufficient while Dark and Konrad [CCC 2020] has shown that Ω(n^2/α^3) bits is necessary. The space complexity, however, still remains unresolved for many other dynamic graph streaming problems where further improvements can still be made.
Conference version:
[PDF]
Full version:
[arXiv]
Youtube video:
[Full Version]
Slides:
[Full Version]
[Conference Version]
BibTex:
[DBLP]