Finding Large Matchings in Semi-Streaming

One of the most appealing open problems in the graph streaming area (see Problem 60 in [1]) is to close the gap between the approximation factor (i.e., lower bound) of 0.5 (achieved by a simple greedy algorithm) [2] and the hardness result (i.e., upper bound) of 1 - 1/e similar or equal to 0.63 [3], [4] for the classical problem of the maximum matching in the semistreaming model. Interestingly, for a long time closing this gap even using 2 passes over an adversarial stream was open until very recently that Konrad, Magniez, and Mathieu in [5] made progress toward answering this question. We develop a 0.583-approximation 2-pass streaming algorithm to find the maximum matching in bipartite graphs, using O(n) space. Using the same technique we give a 0.605-approximation 3-pass streaming algorithm to find the maximum matching in bipartite graphs, using O(n) space. Our results improve upon the 0.505-approximation 2-pass algorithm proposed in [5]. Our 3-pass algorithm is the first 3-pass streaming algorithm that achieves an approximation factor better than 0.6. In the first pass of our algorithm we find a maximal matching M. In the second pass, for every unmatched vertex we keep a small number of edges (so-called, golden edges) incident to distinct matched vertices in M. Every matched vertex of M is incident to at most one golden edge. At the end of second pass, we invoke an optimal matching algorithm on the union of matched and golden edges. For the analysis, let M* be a maximum cardinality matching of G. We show that golden edges help to find a good fraction of augmenting paths of length 3 in M boolean OR M* and also they build many new augmenting paths of length 3 using augmenting paths of length at least 5 and other alternating paths of M boolean OR M*. Our 3-pass algorithm simply repeats the process of the second pass.