A Characterization of Graph Properties Testable for General Planar Graphs with one-Sided Error (It's all About Forbidden Subgraphs)
Open Access
- 1 November 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1525-1548
Abstract
The problem of characterizing testable graph properties (properties that can be tested with a number of queries independent of the input size) is a fundamental problem in the area of property testing. While there has been some extensive prior research characterizing testable graph properties in the dense graphs model and we have good understanding of the bounded degree graphs model, no similar characterization has been known for general graphs, with no degree bounds. In this paper we take on this major challenge and consider the problem of characterizing all testable graph properties in general planar graphs. We consider the model in which a general planar graph can be accessed by the random neighbor oracle that allows access to any given vertex and access to a random neighbor of a given vertex. We show that, informally, a graph property P is testable with one-sided error for general planar graphs if and only if testing P can be reduced to testing for a finite family of finite forbidden subgraphs. While our presentation focuses on planar graphs, our approach extends easily to general minor-free graphs. Our analysis of the necessary condition relies on a recent construction of canonical testers in the random neighbor oracle model that is applied here to the one-sided error model for testing in planar graphs. The sufficient condition in the characterization reduces the problem to the task of testing H-freeness in planar graphs, and is the main and most challenging technical contribution of the paper: we show that for planar graphs (with arbitrary degrees), the property of being H-free is testable with one-sided error for every finite graph H, in the random neighbor oracle model.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Every minor-closed property of sparse graphs is testableAdvances in Mathematics, 2010
- Approximating the distance to properties in bounded-degree and general sparse graphsACM Transactions on Algorithms, 2009
- Testing Hereditary Properties of Nonexpanding Bounded-Degree GraphsSIAM Journal on Computing, 2009
- A separation theorem in property testingCombinatorica, 2008
- Every Monotone Graph Property Is TestableSIAM Journal on Computing, 2008
- Network Motifs: Simple Building Blocks of Complex NetworksScience, 2002
- Testing the diameter of graphsRandom Structures & Algorithms, 2002
- Property Testing in Bounded Degree GraphsAlgorithmica, 2002
- A Sublinear Bipartiteness Tester for Bounded Degree GraphsCombinatorica, 1999
- Property testing and its connection to learning and approximationJournal of the ACM, 1998