Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams

Abstract

We consider the maximum matching problem in the semi-streaming model formalized by Feigenbaum, Kannan, McGregor, Suri, and Zhang that is inspired by giant graphs of today. As our main result, we give a two-pass $(1/2+1/16)$-approximation algorithm for triangle-free graphs and a two-pass $(1/2+1/32)$-approximation algorithm for general graphs; these improve the approximation ratios of $1/2+1/52$ for bipartite graphs and $1/2+1/140$ for general graphs by Konrad, Magniez, and Mathieu. In three passes, we achieve approximation ratios of $1/2+1/10$ for triangle-free graphs and $1/2+1/19.753$ for general graphs. We also give a multi-pass algorithm where we bound the number of passes precisely---we give a $(2/3-\epsilon )$-approximation algorithm that uses $2/(3\epsilon )$ passes for triangle-free graphs and $4/(3\epsilon )$ passes for general graphs. Our algorithms are simple and combinatorial, use $O(n\log n)$ space, and have $O(1)$ update time per edge. For general graphs, our multi-pass algorithm improves the best known deterministic algorithms in terms of the number of passes: --Ahn and Guha give a $(2/3-\epsilon )$-approximation algorithm that uses $O(\log (1/\epsilon )/{\epsilon }^2)$ passes, whereas our $(2/3-\epsilon )$-approximation algorithm uses $4/(3\epsilon )$ passes; --they also give a $(1-\epsilon )$-approximation algorithm that uses $O(\log n\cdot \mathrm{poly}(1/\epsilon ))$ passes, where $n$ is the number of vertices of the input graph; although our algorithm is $(2/3-\epsilon )$-approximation, our number of passes do not depend on $n$. Earlier multi-pass algorithms either have a large constant inside big-$O$ notation for the number of passes or the constant cannot be determined due to the involved analysis, so our multi-pass algorithm should use much fewer passes for approximation ratios bounded slightly below $2/3$.

22 pages, 8 figures

References in corpus (3)

• On Estimating Maximum Matching Size in Graph Streams
• Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
• Streaming Algorithms for Submodular Function Maximization

Cited by in corpus (6)

• Improved Bound for Matching in Random-Order Streams
• On Two-Pass Streaming Algorithms for Maximum Bipartite Matching
• Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams
• Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms
• Constructing Large Matchings via Query Access to a Maximal Matching Oracle
• A Two-Pass Lower Bound for Semi-Streaming Maximum Matching