  Parameterized complexity attempts to give a more fine-grained analysis of the
complexity of problems: instead of measuring the running time as a function of
only the input size, we analyze the running time with respect to additional
parameters. This approach has proven to be highly successful in delineating our
understanding of \NP-hard problems. Given this success with the TIME resource,
it seems but natural to use this approach for dealing with the SPACE resource.
First attempts in this direction have considered a few individual problems,
with some success: Fafianie and Kratsch [MFCS'14] and Chitnis et al. [SODA'15]
introduced the notions of streaming kernels and parameterized streaming
algorithms respectively. For example, the latter shows how to refine the
$\Omega(n^2)$ bit lower bound for finding a minimum Vertex Cover (VC) in the
streaming setting by designing an algorithm for the parameterized $k$-VC
problem which uses $O(k^{2}\log n)$ bits.
  In this paper, we initiate a systematic study of graph problems from the
paradigm of parameterized streaming algorithms. We first define a natural
hierarchy of space complexity classes of FPS, SubPS, SemiPS, SupPS and BrutePS,
and then obtain tight classifications for several well-studied graph problems
such as Longest Path, Feedback Vertex Set, Dominating Set, Girth, Treewidth,
etc. into this hierarchy.
  (see paper for full abstract)
