Testing H-freeness on sparse graphs, the case of bounded expansion
Samuel Humeau, Mamadou Moustapha Kanté, Daniel Mock, Timothé Picavet, Alexandre Vigny
在属性测试中,测试人员对(一个神谕)进行查询,并且在具有或远离属性P的图形上,它以很高的概率决定图形是否满足P。 通常,测试人员被限制为恒定数量的查询。 虽然存在这种测试器的图形属性在致密图模型中的特征有些很好,但对于稀疏图形来说并非如此。 在这一领域,Czumaj和Sohler(FOCS'19)证明,H-freeness(即排除图H作为子图的属性)可以通过平面图以及不包括未成年人的图形类的不断查询进行测试。 使用稀疏工具包的结果,我们提出了一个简单的替代方案,以证明Czumaj和Sohler,用于一个概括为更广泛的边界扩展概念的声明。 也就是说,我们证明对于任何具有边界扩展和任何图形H的类C,测试H自由度可以在C中的任何图形G上以恒定的查询复杂性完成,其中常量依赖于H和C,但独立于G。 虽然排除未成年人的类是具有边界扩展的类的主要示例,例如,立方图,具有边界最大度的图形类,边界书厚度的图形或边界平均度的随机图形也是如此。
In property testing, a tester makes queries to (an oracle for) a graph and, on a graph having or being far from having a property P, it decides with high probability whether the graph satisfies P or not. Often, testers are restricted to a constant number of queries. While the graph properties for which there exists such a tester are somewhat well characterized in the dense graph model, it is not the case for sparse graphs. In this area, Czumaj and Sohler (FOCS'19) proved that H-freeness (i.e. th...