  The study of parameterized streaming complexity on graph problems was
initiated by Fafianie et al. (MFCS'14) and Chitnis et al. (SODA'15 and
SODA'16). Simply put, the main goal is to design streaming algorithms for
parameterized problems such that $O\left(f(k)\log^{O(1)}n\right)$ space is
enough, where $f$ is an arbitrary computable function depending only on the
parameter $k$. However, in the past few years, very few positive results have
been established. Most of the graph problems that do have streaming algorithms
of the above nature are ones where localized checking is required, like Vertex
Cover or Maximum Matching parameterized by the size $k$ of the solution we are
seeking. Many important parameterized problems that form the backbone of
traditional parameterized complexity are known to require $\Omega(n)$ bits for
any streaming algorithm; e.g., Feedback Vertex Set, Even/Odd Cycle Transversal,
Triangle Deletion or the more general ${\cal F}$-Subgraph Deletion when
parameterized by solution size $k$.
  Our main conceptual contribution is to overcome the obstacles to efficient
parameterized streaming algorithms by utilizing the power of parameterization.
To the best of our knowledge, this is the first work in parameterized streaming
complexity that considers structural parameters instead of the solution size as
a parameter. We focus on the vertex cover size $K$ as the parameter for the
parameterized graph deletion problems we consider. At the same time, most of
the previous work in parameterized streaming complexity was restricted to the
EA (edge arrival) or DEA (dynamic edge arrival) models. In this work, we
consider the above mentioned graph deletion problems in the four most
well-studied streaming models, i.e., the EA, DEA, VA (vertex arrival) and AL
(adjacency list) models.
