Parameterized Streaming: Maximal Matching and Vertex Cover∗
Rajesh Chitnis, Graham Cormode, MohammadTaghi Hajiaghayi, Morteza Monemizadeh · 2016
As graphs continue to grow in size, we seek ways to effectively process such data at scale. The model of streaming graph processing, in which a compact summary is maintained as each edge insertion/deletion is observed, is an attractive one. However, few results are known for optimization problems over such dynamic graph streams. In this paper, we introduce a new approach to han-dling graph streams, by instead seeking solutions for the parameterized versions of these problems. Here, we are given a parameter k and the objective is to decide whether there is a solution bounded by k. By com-bining kernelization techniques with randomized sketch structures, we obtain the first streaming algorithms for the parameterized versions of Maximal Matching and Vertex Cover. We consider various models for a graph stream on n nodes: the insertion-only model where the edges can only be added, and the dynamic model where edges can be both inserted and deleted. More formally, we show the following results: • In the insertion only model, there is a one-pass deterministic algorithm for the parameterized Ver-tex Cover problem which computes a sketch using ∗An earlier draft of this paper was made available online as