The Library
Towards a theory of parameterized streaming algorithms
Tools
Chitnis, Rajesh and Cormode, Graham (2019) Towards a theory of parameterized streaming algorithms. In: International Symposium on Parameterized and Exact Computation, Munich, Germany, 9-13 Sep 2019. Published in: 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), 148 7:1-7:15. ISBN 9783959771290. doi:10.4230/LIPIcs.IPEC.2019.7
|
PDF
WRAP-towards-theory-parameterized-streaming-algorithms-Cormode-2019.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1004Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.IPEC.2019.7
Abstract
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 Figure 1 and Table 1). 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.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Parameter estimation, Computer algorithms, Computer science -- Mathematics, Kernel functions | ||||
Journal or Publication Title: | 14th International Symposium on Parameterized and Exact Computation (IPEC 2019) | ||||
Publisher: | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | ||||
ISBN: | 9783959771290 | ||||
Official Date: | 15 July 2019 | ||||
Dates: |
|
||||
Volume: | 148 | ||||
Page Range: | 7:1-7:15 | ||||
DOI: | 10.4230/LIPIcs.IPEC.2019.7 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Open Access (Creative Commons) | ||||
Date of first compliant deposit: | 6 August 2019 | ||||
Date of first compliant Open Access: | 13 August 2019 | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | International Symposium on Parameterized and Exact Computation | ||||
Type of Event: | Other | ||||
Location of Event: | Munich, Germany | ||||
Date(s) of Event: | 9-13 Sep 2019 | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year