## R. Chitnis and G. Cormode.
Towards a theory of parameterized streaming algorithms.
In *International Symposium on Parameterized and Exact
Computation*, 2019.

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 Ω(*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 BPS, 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.
On the algorithmic side, our parameterized streaming algorithms use
techniques from the FPT world such as bidimensionality, iterative compression and
bounded-depth search trees. On the hardness side, we obtain lower bounds for the parameterized streaming complexity of various problems via novel reductions from problems in communication complexity.
We also show a general (unconditional) lower bound for space complexity of parameterized streaming algorithms for a large class of problems inspired by the recently developed frameworks for showing (conditional) kernelization lower bounds.
Parameterized algorithms and streaming algorithms are approaches to
cope with TIME and SPACE intractability respectively. It is our hope
that this work on parameterized streaming algorithms leads to two-way
flow of ideas between these two previously separated areas of theoretical computer science.

[ bib |
.pdf ]
Back

*This file was generated by
bibtex2html 1.92.*