DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2018.39

Deterministic Algorithms for Maximum Matching on General Graphs in the Semi-Streaming Model

Authors: Sumedh Tirodkar

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract

We present an improved deterministic algorithm for Maximum Cardinality Matching on general graphs in the Semi-Streaming Model. In the Semi-Streaming Model, a graph is presented as a sequence of edges, and an algorithm must access the edges in the given sequence. It can only use O(n polylog n) space to perform computations, where n is the number of vertices of the graph. If the algorithm goes over the stream k times, it is called a k-pass algorithm. In this model, McGregor [McGregor, 2005] gave the currently best known randomized (1+epsilon)-approximation algorithm for maximum cardinality matching on general graphs, that uses (1/epsilon)^{O(1/epsilon)} passes. Ahn and Guha [Ahn and Guha, 2013] later gave the currently best known deterministic (1+epsilon)-approximation algorithms for maximum cardinality matching: one on bipartite graphs that uses O(log log(1/epsilon)/epsilon^2) passes, and the other on general graphs that uses O(log n *poly(1/epsilon)) passes (note that, for general graphs, the number of passes is dependent on the size of the input). We present the first deterministic algorithm that achieves a (1+epsilon)-approximation on general graphs in only a constant number ((1/epsilon)^{O(1/epsilon)}) of passes.

Cite as

Sumedh Tirodkar. Deterministic Algorithms for Maximum Matching on General Graphs in the Semi-Streaming Model. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 39:1-39:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{tirodkar:LIPIcs.FSTTCS.2018.39,
  author =	{Tirodkar, Sumedh},
  title =	{{Deterministic Algorithms for Maximum Matching on General Graphs in the Semi-Streaming Model}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{39:1--39:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.39},
  URN =		{urn:nbn:de:0030-drops-99383},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.39},
  annote =	{Keywords: Semi Streaming, Maximum Matching}
}

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.15

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

Authors: Sagar Kale and Sumedh Tirodkar

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

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/(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 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.

Cite as

Sagar Kale and Sumedh Tirodkar. Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 15:1-15:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kale_et_al:LIPIcs.APPROX-RANDOM.2017.15,
  author =	{Kale, Sagar and Tirodkar, Sumedh},
  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:1--15:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.15},
  URN =		{urn:nbn:de:0030-drops-75645},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.15},
  annote =	{Keywords: Semi Streaming, Maximum Matching}
}

Search Results

Documents authored by Tirodkar, Sumedh

Deterministic Algorithms for Maximum Matching on General Graphs in the Semi-Streaming Model

Abstract

Cite as

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

Abstract

Cite as

Thanks for your feedback!

Could not send message