Abstract
We consider the maximum matching problem in the semistreaming model formalized by Feigenbaum, Kannan, McGregor, Suri, and Zhang that is inspired by giant graphs of today. As our main result, we give a twopass (1/2 + 1/16)approximation algorithm for trianglefree graphs and a twopass (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 trianglefree graphs and 1/2 + 1/19.753 for general graphs. We also give a multipass algorithm where we bound the number of passes precisely  we give a (2/3  epsilon)approximation algorithm that uses 2/(3 epsilon) passes for trianglefree 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 multipass 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/(epsilon) passes;
* they also give a (1  epsilon)approximation algorithm that uses O(log(n) 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 multipass algorithms either have a large constant inside bigO notation for the number of passes or the constant cannot be determined due to the involved analysis, so our multipass algorithm should use much fewer passes for approximation ratios bounded slightly below 2/3.
BibTeX  Entry
@InProceedings{kale_et_al:LIPIcs:2017:7564,
author = {Sagar Kale and Sumedh Tirodkar},
title = {{Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
pages = {15:115:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770446},
ISSN = {18688969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7564},
URN = {urn:nbn:de:0030drops75645},
doi = {10.4230/LIPIcs.APPROXRANDOM.2017.15},
annote = {Keywords: Semi Streaming, Maximum Matching}
}
Keywords: 

Semi Streaming, Maximum Matching 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) 
Issue Date: 

2017 
Date of publication: 

11.08.2017 