Mohammad Hajiaghayi
University of Maryland – College Park

Title: Parameterized and Promised Streaming: Matching and Vertex Cover

Abstract:
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 (often NP-hard) problems over such dynamic graph streams.

In this talk, we introduce a new approach to handling graph streams,
by instead seeking solutions for the parameterized (and promised) 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 combining
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.