Parameterized Complexity of Streaming Diameter and Connectivity Problems
Jelle J. Oostveen, Erik Jan van Leeuwen · arXiv (Cornell University) · 2022
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(\log n)$ for any fixed $k$. Underlying these algorithms is a method to execute a breadth-first search in $O(k)$ passes and $O(k \log n)$ 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, $Ω(n \log n)$ 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 $\text{poly}(k)$ passes and only $O(k \log n)$ bits of memory.