  We optimally resolve the space complexity for the problem of finding an
$\alpha$-approximate minimum vertex cover ($\alpha$MVC) in dynamic graph
streams. We give a randomised algorithm for $\alpha$MVC which uses
$O(n^2/\alpha^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
$\alpha$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 $\Omega(n \log^3 n)$ bits of space is necessary
while Ahn, Guha, and McGregor [SODA 2012] have shown that $O(n \log^3 n)$ bits
is sufficient. For finding an $\alpha$-approximate maximum matching, the upper
bound was improved by Assadi and Shah [ITCS 2022] showing that
$O(n^2/\alpha^3)$ bits is sufficient while Dark and Konrad [CCC 2020] have
shown that $\Omega(n^2/\alpha^3)$ bits is necessary. The space complexity,
however, remains unresolved for many other dynamic graph streaming problems
where further improvements can still be made. \end{abstract}
