Post Doctoral Fellow, School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai, India

Maximum Matching on graphs in the semi-streaming model

Maximum Matching in simple undirected graphs is a subset of maximum number of edges such that at most one edge is incident on any vertex. We study this problem in the semi-streaming model, in which edges are presented as a stream, and the goal is to output a matching of maximum size while only using $O(n\polylog n)$ space (where $n$ is the number of vertices in the graph). A $k$-pass algorithm can go over the stream $k$ times.

In this work, we present a two pass algorithm which produces a matching of size at least (1/2+1/16) times that of maximum matching. We also present a $2/(3\epsilon)$-pass algorithm which gives a matching of size at least $2/3-\epsilon$ times that of maximum matching.