The sparse awakens: streaming algorithms for matching size estimation in sparse graphs

DOI10.4230/LIPICS.ESA.2017.29zbMATH Open1442.68273arXiv1608.03118OpenAlexW2963373149MaRDI QIDQ5111716FDOQ5111716

Author name not available (Why is that?)

Publication date: 27 May 2020

Abstract: Estimating the size of the maximum matching is a canonical problem in graph algorithms, 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(c log^2 n) space and approximates the size of the maximum matching in graphs with arboricity c within a factor of O(c). This improves significantly on the state-of-the-art O~(cn^{2/3})-space streaming algorithms. * Dynamic Streams: Given a dynamic graph stream (i.e., inserts and deletes) of edges of an underlying c-bounded arboricity graph, we present a one-pass algorithm that uses space O~(c^{10/3}n^{2/3}) and returns an O(c)-estimator for the size of the maximum matching. This algorithm improves the state-of-the-art O~(cn^{4/5})-space algorithms, where the O~(.) notation hides logarithmic in $n$ dependencies. In contrast to the previous works, 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.

Full work available at URL: https://arxiv.org/abs/1608.03118

Recommendations

• Structural results on matching estimation with applications to streaming
• A simple, space-efficient, streaming algorithm for matchings in low arboricity graphs
• On estimating maximum matching size in graph streams
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• Streaming algorithms for estimating the matching size in planar graphs and beyond

zbMATH Keywords

streaming algorithmsmatching size

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Matching theory
• Title not available (Why is that?)
• Edge-Disjoint Spanning Trees of Finite Graphs
• AdWords and generalized online matching
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Decomposition of Finite Graphs Into Forests
• Lower bound of the Hadwiger number of graphs by their average degree
• Linear-Time Approximation for Maximum Weight Matching
• On graph problems in a semi-streaming model
• Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
• Weighted matching in the semi-streaming model
• Bipartite matching in the semi-streaming model
• Maximum Matching in Semi-streaming with Few Passes
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Better bounds for matchings in the streaming model
• Title not available (Why is that?)
• Spectral Sparsification in Dynamic Graph Streams
• Matching for Graphs of Bounded Degree
• On Estimating Maximum Matching Size in Graph Streams
• Title not available (Why is that?)
• Title not available (Why is that?)
• A (2 + ∊)-Approximation for Maximum Weight Matching in the Semi-Streaming Model
• Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• Approximating matching size from random streams
• Title not available (Why is that?)
• Planar Matching in Streams Revisited
• The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs
• On Unifying the Space of ℓ₀-Sampling Algorithms

Cited In (13)

• An estimator for matching size in low arboricity graphs with two applications
• Fixed parameter tractability of graph deletion problems over data streams
• Structural results on matching estimation with applications to streaming
• Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs
• Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams
• Improved bounds for matching in random-order streams
• Title not available (Why is that?)
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond
• Almost-smooth histograms and sliding-window graph algorithms
• The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs
• Title not available (Why is that?)
• Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model

This page was built for publication: The sparse awakens: streaming algorithms for matching size estimation in sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111716)