Every Property of Hyperfinite Graphs is Testable
Loading...
Date
2013-06-13
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Society for Industrial and Applied Mathematics
Abstract
A k-disc around a vertex v of a graph G=(V,E) is the subgraph induced by all vertices of distance at most k from v. We show that the structure of a planar graph on n vertices, and with constant maximum degree d, is determined, up to the modification (insertion or deletion) of at most εdn edges, by the frequency of k-discs for certain k=k(ε,d) that is independent of the size of the graph. We can replace planar graphs by any hyperfinite class of graphs, which includes, for example, every graph class that does not contain a set of forbidden minors. A pure combinatorial consequence of this result is that two d-bounded degree graphs that have similar frequency vectors (that is, the l_1 difference between the frequency vectors is small) are close to isomorphic (where close here means that by inserting or deleting not too many edges in one of them, it becomes isomorphic to the other). We also obtain the following new results in the area of property testing, which are essentially equivalent to the above statement. We prove that (a) graph isomorphism is testable for every class of hyperfinite graphs, (b) every graph property is testable for every class of hyperfinite graphs, (c) every hyperfinite graph property is testable in the bounded degree graph model, (d) A large class of graph parameters is approximable for hyperfinite graphs. Our results also give a partial explanation of the success of motifs in the analysis of complex networks.
Description
Table of contents
Keywords
property testing, graph properties