Conference: The 50th Annual IEEE Symposium on Foundations
of Computer Science (FOCS 2009).

Abstract:
We introduce a new tool for approximation and testing algorithms called *partitioning oracles*. We develop methods for constructing them for any class of bounded-degree graphs with an excluded minor, and in general, for any hyperfinite class of bounded-degree graphs. These oracles utilize only *local* computation to consistently answer queries about a *global* partition that breaks the graph into small connected components by removing only a small fraction of the edges.

We illustrate the power of this technique by using it to extend and simplify a number of previous approximation and testing results for sparse graphs, as well as to provide new results that were unachievable with existing techniques. For instance:

- We give constant-time approximation algorithms for the size of the minimum vertex cover, the minimum dominating set, and the maximum independent set for any class of graphs with an excluded minor.
- We show a simple proof that any minor-closed graph property is testable in constant time in the bounded degree model.
- We prove that it is possible to approximate the distance to almost any hereditary property in any bounded degree hereditary families of graphs. Hereditary properties of interest include bipartiteness,
*k*-colorability, and perfectness.

BibTeX:
[DBLP]