A Characterization of Graph Properties Testable for General Planar Graphs with one-Sided Error (It's all About Forbidden Subgraphs)
A Characterization of Graph Properties Testable for General Planar Graphs with one-Sided Error (It's all About Forbidden Subgraphs)
复制标题
具有单边误差的一般平面图的可测试图属性的表征（都是关于禁止子图）
DOI：
10.1109/focs.2019.00089
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
C. Sohler
中科院分区：
文献类型：
--
作者：
A. Czumaj;C. Sohler
表征可测试图属性（可以使用与输入大小无关的多个查询进行测试的属性）的问题是属性测试领域的一个基本问题。虽然之前有一些广泛的研究描述了密集图模型中可测试的图属性，并且我们对有界度图模型有很好的理解，但对于没有度界限的一般图，还没有类似的特征。在本文中，我们应对这一重大挑战，并考虑表征一般平面图中所有可测试图属性的问题。我们考虑这样一个模型，其中一般平面图可以通过随机邻居预言来访问，该随机邻居预言允许访问任何给定顶点以及访问给定顶点的随机邻居。我们非正式地表明，当且仅当测试 P 可以简化为测试有限族的有限禁止子图时，图属性 P 才可以在一般平面图的单边误差下进行测试。虽然我们的演示重点是平面图，但我们的方法可以轻松扩展到一般的无次要图。我们对必要条件的分析依赖于随机邻居预言模型中规范测试器的最新构造，该模型在此应用于平面图中测试的单边误差模型。表征中的充分条件将问题简化为测试平面图中 H 无性的任务，这是本文主要且最具挑战性的技术贡献：我们证明，对于平面图（具有任意度数），在随机邻居预言模型中，对于每个有限图 H，H 无性的属性是可测试的，且具有单边误差。
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.
平面图：随机游走和二分测试
DOI：
10.1109/focs.2011.69
发表时间：
2011
期刊：
--
影响因子：
--
作者：
Czumaj A
通讯作者：
Czumaj A