Every minor-closed property of sparse graphs is testable |
| |
Authors: | Itai Benjamini Oded Schramm |
| |
Institution: | a The Weizmann Institute, Israel b Microsoft Research, United States c School of Mathematics and School of Computer Science, Georgia Institute of Technology, Atlanta, GA 30332, United States |
| |
Abstract: | Suppose G is a graph of bounded degree d, and one needs to remove ?n of its edges in order to make it planar. We show that in this case the statistics of local neighborhoods around vertices of G is far from the statistics of local neighborhoods around vertices of any planar graph G′. In fact, a similar result is proved for any minor-closed property of bounded degree graphs.The main motivation of the above result comes from theoretical computer-science. Using our main result we infer that for any minor-closed property P, there is a constant time algorithm for detecting if a graph is “far” from satisfying P. This, in particular, answers an open problem of Goldreich and Ron STOC 1997] 20], who asked if such an algorithm exists when P is the graph property of being planar. The proof combines results from the theory of graph minors with results on convergent sequences of sparse graphs, which rely on martingale arguments. |
| |
Keywords: | Minor closed Property testing Sparse graphs Hyper finite |
本文献已被 ScienceDirect 等数据库收录! |
|