Local Graph Partitions for Approximation and Testing
Local Graph Partitions for Approximation and Testing
复制标题
用于近似和测试的本地图分区
DOI：
10.1109/focs.2009.77
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Krzysztof Onak
中科院分区：
文献类型：
--
作者：
Avinatan Hassidim;Jonathan A. Kelner;H. N. Nguyen;Krzysztof Onak
我们引入了一种用于近似和测试算法的新工具，称为划分预言机（partitioning oracles）。我们开发了一些方法，针对任何具有排除子图（excluded minor）的有界度图类，以及一般而言，针对任何有界度的超有限图类来构建它们。这些预言机仅利用局部计算来一致地回答关于一种全局划分的查询，这种划分通过仅移除一小部分边将图分解为小的连通分量。我们通过使用这种技术来扩展和简化许多先前针对稀疏图的近似和测试结果，并提供现有技术无法实现的新结果，从而展示了这种技术的强大威力。例如：
1. 对于任何具有排除子图的图类，我们给出了最小顶点覆盖大小、最小支配集以及最大独立集的常数时间近似算法。
2. 我们给出了一个简单的证明，即在有界度模型中，任何子图封闭的图性质都可以在常数时间内进行测试。
3. 我们证明，在任何有界度的遗传图族中，有可能近似到几乎任何遗传性质的距离。感兴趣的遗传性质包括二分性、k -可着色性和完美性。
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:1. 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.2. We show a simple proof that any minor-closed graph property is testable in constant time in the bounded degree model.3. 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.