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 \(\mathcal {O}(\log n)\) for any fixed k. Underlying these algorithms is a method to execute a breadth-first search in \(\mathcal {O}(k)\) passes and \(\mathcal {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 \(\Omega (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, \(\Omega (n \log n)\) bits of memory lower bounds. We also prove a much stronger \(\Omega (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 \(\mathcal {O}(k^2)\) edges) produced as a stream in \(\text {poly}(k)\) passes and only \(\mathcal {O}(k \log n)\) bits of memory.
