Parameterized Complexity of Streaming Diameter and Connectivity Problems

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

We initiate the investigation of the parameterized complexity of Diameter and Connectivity in the streaming paradigm. On the positive end, we show that knowing a vertex cover of size k allows for algorithms in the Adjacency List (AL) streaming model whose number of passes is constant and memory is O(logn) for any fixed k. Underlying these algorithms is a method to execute a breadth-first search in O(k) passes and O(klogn) bits of memory. On the negative end, we show that many other parameters lead to lower bounds in the AL model, where Ω(n/p) bits of memory is needed for any p-pass algorithm even for constant parameter values. In particular, this holds for graphs with a known modulator (deletion set) of constant size to a graph that has no induced subgraph isomorphic to a fixed graph H, for most H. For some cases, we can also show one-pass, Ω(nlogn) bits of memory lower bounds. We also prove a much stronger Ω(n2/p) lower bound for Diameter on bipartite graphs. Finally, using the insights we developed into streaming parameterized graph exploration algorithms, we show a new streaming kernelization algorithm for computing a vertex cover of size k. This yields a kernel of 2k vertices (with O(k2) edges) produced as a stream in poly(k) passes and only O(klogn) bits of memory.

Original languageEnglish
Number of pages44
JournalAlgorithmica
DOIs
Publication statusE-pub ahead of print - 19 Jun 2024

Keywords

  • Complexity
  • Connectivity
  • Diameter
  • Disjointness
  • Graphs
  • Parameter
  • Permutation
  • Stream
  • Streaming
  • Vertex cover

Fingerprint

Dive into the research topics of 'Parameterized Complexity of Streaming Diameter and Connectivity Problems'. Together they form a unique fingerprint.

Cite this