Parameterized Algorithms in a Streaming Setting

Abstract

Saving large graphs in memory can be problematic. Streaming the graph provides a solution, where the graph arrives as a stream of edges. Different streaming models can be used to assume a variable amount of information present in the stream. In combination with parameterized complexity, we can find algorithms using sublinear memory, where for non-parameterized algorithms it can be proven that we require linear memory. In this work, we investigate a broad range of problems in the streaming setting, including varying approaches to solve them. Different approaches can lead to an interesting trade-off in the number of times we inspect the stream and the memory usage. Hence, we explore both kernelization and direct algorithmic approaches for solving problems such as Pi-free Deletion, Pi-free Editing, Vertex Cover, and Edge Dominating Set. In terms of parameterization, we focus on using the parameter vertex cover, but we will also see solution size and tree-depth being used. We will see a range of upper bound results, which are partially direct adaptations of non-streaming algorithms, and partially new work. We will also see some lower bounds on the memory use given the number of passes we make over the stream.