Testing Some First-Order Logic Properties on Sparse Graphs

doi:10.1007/978-981-95-0218-9_8

2026-01-01

PRE

Pan Peng

Yu, Kefan *

DOI：10.1007/978-981-95-0218-9_8

原文链接

原文求助

摘要

En 中文

本文研究了在邻接表模型下对稀疏图进行一些一阶逻辑性质测试的问题，包括k支配集性质、k顶点覆盖性质和直径≤k性质。(1) 对于k支配集性质，我们在边数不超过Cn的n顶点图上给出一个查询复杂度为O((kC)(k+1)/ε(k+2) log (kC/ε)的测试器。此外，如果输入图是平面图，我们将查询复杂度改进为O(k^6/ε^3 log(k^2/ε))。(2) 对于k顶点覆盖性质，我们在度数界为α的图中给出一个查询复杂度为O(α^3k^2/log k/ε ε^2)的测试器。先前已知这些性质在带有随机边采样查询的更强模型下可在一般图上以常数查询复杂度进行测试。通过利用边采样模拟技术，可在邻接模型中对度数界图实现poly(log n)查询复杂度。相比之下，我们的算法在更广泛的一类稀疏图或相同度数界图中实现了常数查询复杂度（固定ε和k）。(3) 对于直径≤k性质，我们可在查询复杂度O(C⌈k/2⌉+1 ε⌈k/2⌉+2)下区分稀疏图是否具有直径至多为k，或与任何直径至多为k+2的图相差ε远。先前已知在一般图上存在一个测试器，可区分直径至多为k与与任何直径至多为β(k)的图相差ε远（β(k)范围从k+4到4k+2）。我们改进了稀疏图上β(k)的上界至至多为k+2，尽管查询复杂度略有提高。

Keyword:

EVERY PROPERTY