We study constant-time approximation algorithms for bounded-degree graphs, which run in time independent of the number of vertices $n$. We present an algorithm that decides whether a vertex is contained in a some fixed maximal independent set with expected query complexity $O(d^2)$, where $d$ is the degree bound. Using this algorithm, we show constant-time approximation algorithms with certain multiplicative error and additive error $\epsilon n$ for many other problems, e.g., the maximum matching problem, the minimum vertex cover problem, and the minimum set cover problem, that run exponentially faster than existing algorithms with respect to $d$ and $\frac{1}{\epsilon}$. Our approximation algorithm for the maximum matching problem can be transformed to a two-sided error tester for the property of having a perfect matching. On the contrary, we show that every one-sided error tester for the property requires at least $\Omega(n)$ queries.

This paper studies approximation algorithms for problems on degree-bounded graphs. Let n and d be the number of vertices and the degree bound, respectively. This paper presents an algorithm to approximate the size of some maximal independent set with additive error ε n whose running time is O(d2). Using this algorithm, it also shows that there are approximation algorithms for many other problems, e.g., the maximum matching problem, the minimum vertex cover problem, and the minimum set cover problem, that run exponentially faster than existing algorithms with respect to d and 1/ε. Its approximation algorithm for the maximum matching problem can be transformed to a testing algorithm for the property of having a perfect matching with two-sided error. On the contrary, it also shows that every one-sided error tester for the property requires at least Ω(n) queries.