## 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 Ω(n^{2}/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(k^{2}) edges) produced as a stream in poly(k) passes and only O(klogn) bits of memory.

Original language | English |
---|---|

Number of pages | 44 |

Journal | Algorithmica |

DOIs | |

Publication status | E-pub ahead of print - 19 Jun 2024 |

## Keywords

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