Towards a Theory of Parameterized Streaming Algorithms

Rajesh Chitnis, Graham Cormode

TL;DR

This paper introduces a theoretical framework for analyzing parameterized streaming algorithms, bridging the gap between parameterized complexity (handling computationally hard problems by focusing on specific parameters) and streaming algorithms (handling massive datasets with limited memory). The authors define new complexity classes and provide tight classifications for several graph problems, offering a more nuanced understanding of their space requirements.

What Problem Does This Paper Address?

Traditionally, algorithm efficiency is measured by time complexity. However, many problems are intractable even with unlimited time, and some are also difficult to handle due to massive input sizes that don't fit into memory. Parameterized complexity offers a way to analyze problems by considering not just input size but also specific parameters, leading to efficient algorithms for many NP-hard problems. Streaming algorithms, on the other hand, focus on minimizing memory usage when processing data that cannot be stored entirely.

This paper addresses the challenge of designing algorithms that are efficient in both space (streaming) and parameterized time. The authors aim to build a "theory of parameterized streaming algorithms" by defining a hierarchy of space complexity classes and classifying well-known graph problems within this hierarchy. This work seeks to unify insights from both parameterized algorithms and streaming algorithms.

Methods

The paper introduces a hierarchy of space complexity classes for parameterized streaming algorithms:

  • FPS (Fixed-Parameterized Streaming): Solvable using $O(f(k))$ bits.
  • SubPS (Sublinear Parameterized Streaming): Solvable using $O(f(k) \cdot n^{1-\epsilon})$ bits.
  • SemiPS (Parameterized Semi-Streaming): Solvable using $O(f(k) \cdot n)$ bits.
  • SupPS (Superlinear Parameterized Streaming): Solvable using $O(f(k) \cdot n^{1+\epsilon})$ bits.
  • BrutePS (Brute-Force Parameterized Streaming): Solvable using $O(n^2)$ bits.

The authors employ techniques from the FPT world, such as:

  • Branching: Used to design a 2k-pass algorithm for k-Vertex Cover (k-VC) with $O(k \log n)$ bits.
  • Iterative Compression: Utilized to design a more complex algorithm for k-VC with $O(k \log n)$ bits but $O(k \cdot 2^{2k})$ passes.
  • Bidimensionality: Applied to show that minor-bidimensional problems belong to the SemiPS class, offering $O(k^{10} \cdot n)$ space algorithms.

For lower bounds, they use novel reductions from communication complexity problems like PERM and INDEX.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of graph problems and does not involve empirical evaluation on specific datasets.

Key Insights and Ideas

  • Bridging two worlds: The paper successfully connects the theoretical frameworks of parameterized complexity and streaming algorithms, suggesting a fruitful area for future research.
  • Hierarchy of space complexity: The proposed hierarchy of FPS, SubPS, SemiPS, SupPS, and BrutePS provides a structured way to classify parameterized streaming problems.
  • FPT techniques in streaming: Demonstrating that techniques like branching and iterative compression, traditionally used for time complexity, can be adapted for space-bounded streaming algorithms is a significant contribution.
  • Tight classifications: The paper achieves tight classifications for several fundamental graph problems, showing where they naturally fit within the defined complexity classes.
  • Lower bounds from communication complexity: Using reductions from communication complexity problems is a powerful technique for establishing lower bounds in the streaming setting.

Key Results

The paper presents a comprehensive set of results, including:

  • Algorithms:
    • $O(k \log n)$ bit, 2k-pass algorithm for k-VC.
  • $O(k \log n)$ bit, $O(k \cdot 2^{2k})$-pass algorithm for k-VC.
  • $O(k^{10} \cdot n)$ space algorithms for minor-bidimensional problems (e.g., k-Treewidth, k-FVS) in insertion-only and insertion-deletion streams.
  • Lower Bounds:
    • $\Omega(n \log n)$ bit lower bounds for k-Path, k-Treewidth, and k-FVS (for constant k), showing they are tight for SemiPS.
  • $\Omega(n^2)$ bit lower bounds for k-Dominating Set and k-Girth (for constant k), showing they are tight for BrutePS.
  • $\Omega(n)$ bit lower bound for approximating the minimum dominating set size on graphs of bounded arboricity.
  • $\Omega((N/d)^d)$ bit lower bound for d-SAT, indicating that all clauses must essentially be stored.

Limitations and Future Work

  • Passes vs. Space: While algorithms with optimal space complexity are presented, some require a large number of passes (e.g., the 2k-pass k-VC algorithm). A key open question is whether the number of passes can be reduced for these algorithms, or if lower bounds can be established for algorithms with limited passes and optimal space.
  • k-OCT problem: The paper highlights the k-OCT problem as a potential candidate for applying iterative compression in the streaming setting, but a concrete algorithm is not presented.
  • Generalization of d-SAT: The paper proves a lower bound for d-SAT, but the focus is on 2-SAT, with a mention that generalization to d-SAT is simple. Further exploration of this result could be valuable.
  • Conditional lower bounds: The paper discusses how conditional lower bounds from FPT and kernelization translate to parameterized streaming algorithms, suggesting this as a direction for future research.

Summary updated

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 paper for full abstract)
BibTeX
@inproceedings{chitnis2019towards,
  author = {Rajesh Chitnis and Graham Cormode},
  title = {{Towards a Theory of Parameterized Streaming Algorithms}},
  booktitle = {IPEC},
  year = {2019},
  doi = {10.4230/lipics.ipec.2019.7},
}
Figure