Time-Optimal Sublinear Algorithms for Matching and Vertex Cover
Author:
- 1 February 2022
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 873-884
Abstract
We study the problem of estimating the size of maximum matching and minimum vertex cover in sub linear time. Denoting the number of vertices by $n$ and the average degree in the graph by $\overline{d}$ , we obtain the following results for both problems which are all provably time-optimal up to polylogarithmic factors: 1 1 The $\tilde{O}(\cdot)$ notation hides polylog $n$ factors throughout the paper. •A multiplicative $(2+\varepsilon)$ -approximation that takes $\tilde{O}(n/\varepsilon^{2})$ time using adjacency list queries. •A multiplicative-additive $(2,\ \varepsilon n)$ -approximation that takes $\tilde{O}((\overline{d}+1)/\varepsilon^{2})$ time using adjacency list queries. •A multiplicative-additive $(2,\ \varepsilon n)$ -approximation that takes $\tilde{O}(n/\varepsilon^{3})$ time using adjacency matrix queries. Our main contribution and the key ingredient of the bounds above is a near-tight analysis of the average query complexity of randomized greedy maximal matching which improves upon a seminal result of Yoshida, Yamamoto, and Ito $[\text{STOC}^{\prime} 09]$ .
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Approximating matching size from random streams2013
- Space-efficient Local Computation Algorithms2012
- A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size2012
- A Model of Computation for MapReduce2010
- Sublinear-time Algorithms2010
- Estimating the Weight of Metric Minimum Spanning Trees in Sublinear TimeSIAM Journal on Computing, 2009
- Approximating average parameters of graphsRandom Structures & Algorithms, 2008
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithmsTheoretical Computer Science, 2007
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a GraphSIAM Journal on Computing, 2006
- Approximating the Minimum Spanning Tree Weight in Sublinear TimeSIAM Journal on Computing, 2005