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.