Estimating Streaming Maximum Matching in Planar Graphs and Beyond

Morteza Monemizadeh

University of Maryland

Abstract

We consider the problem of estimating the size of a maximum matching when the edges are revealed in a streaming fashion. Consider a graph G = (V, E) with n vertices and m edges. The input stream is a permutation of edges S=(e1,...,em} chosen by an adversary. The goal is to output an estimation of the size of a maximum matching. The algorithm is only allowed to use a small amount of memory (much smaller than n). When the underlying graph is planar, we present a simple and elegant streaming algorithm that with high probability estimates the size of a maximum matching within a constant factor using O~(n^{2/3}) memory space. The same guarantee generalizes to the family of graphs that have a constant arboricity. Graphs with bounded arboricity include, among other families of graphs, the graphs that exclude a constant-size minor. To the best of our knowledge, this is the first result