Approximate Matchings in Graph Streams and in the Simultaneous Communication Model

The maximum matching problem is among the most well-studied problems in combinatorial optimization with many applications. We consider the problem of approximating a maximum matching in graph streams where the input graph is revealed as a stream of edge updates that may include both edge insertions and deletions. The goal is to design a streaming algorithm that computes an approximate matching in sublinear space, that is, using space that is substantially smaller than the space needed to store all the edges in the graph.
In this talk, we will describe some progress on this problem that precisely characterizes the tradeoff between the space available to the algorithm and the quality of the matching approximation. As it turns out, the study of sublinear space algorithms for matchings is intimately connected to understanding communication complexity of solving the matching problem in a distributed model of computation, called the simultaneous communication model. We will also present some very recent developments on the matching problem in the simultaneous model which show that a simple assumption on how the graph is partitioned completely alters the tractability of the problem.