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²/α²) 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 this type of optimality result 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³ n) bits of space is necessary while Ahn, Guha, and McGregor SODA 2012 have shown that O(n log³ 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²/α³) bits is sufficient while Dark and Konrad CCC 2020 have shown that Ω(n²/α³) bits is necessary. The space complexity, however, remains unresolved for many other dynamic graph streaming problems where further improvements can still be made.
Naidu et al. (Thu,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: