DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.10

An Estimator for Matching Size in Low Arboricity Graphs with Two Applications

Authors: Hossein Jowhari

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

Abstract

In this paper, we present a new degree-based estimator for the size of maximum matching in bounded arboricity graphs. When the arboricity of the graph is bounded by α, the estimator gives a α+2 factor approximation of the matching size. For planar graphs, we show the estimator does better and returns a 3.5 approximation of the matching size. Using this estimator, we get new results for approximating the matching size of planar graphs in the streaming and distributed models of computation. In particular, in the vertex-arrival streams, we get a randomized O((√n)/(ε²)log n) space algorithm for approximating the matching size of a planar graph on n vertices within (3.5+ε) factor. Similarly, we get a simultaneous protocol in the vertex-partition model for approximating the matching size within (3.5+ε) factor using O((n^{2/3})/(ε²)log n) communication from each player. In comparison with the previous estimators, the estimator in this paper does not need to know the arboricity of the input graph and improves the approximation factor in the case of planar graphs.

Cite as

Hossein Jowhari. An Estimator for Matching Size in Low Arboricity Graphs with Two Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{jowhari:LIPIcs.APPROX/RANDOM.2021.10,
  author =	{Jowhari, Hossein},
  title =	{{An Estimator for Matching Size in Low Arboricity Graphs with Two Applications}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{10:1--10:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.10},
  URN =		{urn:nbn:de:0030-drops-147039},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.10},
  annote =	{Keywords: Data Stream Algorithms, Maximum Matching, Planar Graphs}
}

Document

DOI: 10.4230/LIPIcs.ESA.2017.29

The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs

Authors: Graham Cormode, Hossein Jowhari, Morteza Monemizadeh, and S. Muthukrishnan

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract

Estimating the size of the maximum matching is a canonical problem in graph analysis, and one that has attracted extensive study over a range of different computational models. We present improved streaming algorithms for approximating the size of maximum matching with sparse (bounded arboricity) graphs. * (Insert-Only Streams) We present a one-pass algorithm that takes O(alpha log n) space and approximates the size of the maximum matching in graphs with arboricity alpha within a factor of O(alpha). This improves significantly upon the state-of-the-art tilde{O}(alpha n^{2/3})-space streaming algorithms, and is the first poly-logarithmic space algorithm for this problem. * (Dynamic Streams) Given a dynamic graph stream (i.e., inserts and deletes) of edges of an underlying alpha-bounded arboricity graph, we present an one-pass algorithm that uses space tilde{O}(alpha^{10/3}n^{2/3}) and returns an O(alpha)-estimator for the size of the maximum matching on the condition that the number edge deletions in the stream is bounded by O(alpha n). For this class of inputs, our algorithm improves the state-of-the-art tilde{O}(\alpha n^{4/5})-space algorithms, where the \tilde{O}(.) notation hides logarithmic in n dependencies. In contrast to prior work, our results take more advantage of the streaming access to the input and characterize the matching size based on the ordering of the edges in the stream in addition to the degree distributions and structural properties of the sparse graphs.

Cite as

Graham Cormode, Hossein Jowhari, Morteza Monemizadeh, and S. Muthukrishnan. The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cormode_et_al:LIPIcs.ESA.2017.29,
  author =	{Cormode, Graham and Jowhari, Hossein and Monemizadeh, Morteza and Muthukrishnan, S.},
  title =	{{The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.29},
  URN =		{urn:nbn:de:0030-drops-78499},
  doi =		{10.4230/LIPIcs.ESA.2017.29},
  annote =	{Keywords: streaming algorithms, matching size}
}

Search Results

Documents authored by Jowhari, Hossein

An Estimator for Matching Size in Low Arboricity Graphs with Two Applications

Abstract

Cite as

The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message