Maximal Matching in Bounded-deletion Streams

We study the maximal matching problem in bounded-deletion graph streams. In this setting, a graph $G$ is revealed as an arbitrary sequence of edge insertions and deletions, where the number of insertions is unrestricted but the number of deletions is guaranteed to be at most $K$, for some given parameter $K$. The single-pass streaming space complexity of this problem is known to be $\Theta(n^2)$ when $K$ is unrestricted, where $n$ is the number of vertices of the input graph. We present a new algorithm and a matching lower bound result that together give a tight understanding (up to poly-log factors) of how the space complexity of maximal matching evolves as a function of the parameter $K$.