In this paper, we study the problem of testing some first-order logic properties on sparse graphs under the adjacency list model, including k-dominating set property, k-vertex cover property and diameter \( \le k \) property. (1) For the k-dominating set property, we give a tester with query complexity \( O\left( \frac{(kC)^{k+1}}{\varepsilon ^{k+2}}\log \left( \frac{kC}{\varepsilon }\right) \right) \) on n-vertex graphs with at most Cn edges. Furthermore, if the input graph is planar, we improve the query complexity to \( O\left( \frac{k^{6}}{\varepsilon ^3}\log (\frac{k^2}{\varepsilon })\right) \) . (2) For the k-vertex cover property, we give a tester whose query complexity is \( O\left( \frac{\alpha ^3k^2\log k}{\varepsilon ^2}\right) \) on graphs with arboricity bounded by \( \alpha \) . Previously, these properties were known to be testable with constant query complexity on general graphs under a stronger model with random edge sampling queries. By leveraging edge sampling simulation techniques, one can achieve \( \textrm{poly}(\log n) \) query complexity in the adjacency model for bounded arboricity graphs. In contrast, our algorithms achieve constant query complexity (for fixed \(\varepsilon \) and k) on a broader class of sparse graphs or the same class of bounded arboricity graphs. (3) For the diameter \( \le k \) property, we can distinguish whether a sparse graph has a diameter at most k or is \( \varepsilon \) -far from any graph that has a diameter at most \( k+2 \) with query complexity \( O\left( \frac{C^{\lfloor k/2\rfloor +1}}{\varepsilon ^{\lfloor k/2\rfloor +2}}\right) \) . Previously, a tester was known for general graphs that distinguishes between having a diameter at most k and being \(\varepsilon \) -far from any graph with diameter at most \(\beta (k)\) , where \(\beta (k)\) ranges from \(k+4\) to \(4k+2\) . We improve the upper bound on \(\beta (k)\) to at most \(k+2\) for sparse graphs, though at the cost of slightly higher query complexity.

Testing Some First-Order Logic Properties on Sparse Graphs

会议论文
发表日期：

2026年

查看全文

Pan Peng,
Kefan Yu

摘要

In this paper, we study the problem of testing some first-order logic properties on sparse graphs under the adjacency list model, including k-dominating set property, k-vertex cover property and diameter \( \le k \) property. (1) For the k-dominating set property, we give a tester with query complexity \( O\left( \frac{(kC)^{k+1}}{\varepsilon ^{k+2}}\log \left( \frac{kC}{\varepsilon }\right) \right) \) on n-vertex graphs with at most Cn edges. Furthermore, if the input graph is planar, we improve the query complexity to \( O\left( \frac{k^{6}}{\varepsilon ^3}\log (\frac{k^2}{\varepsilon })\right) \) . (2) For the k-vertex cover property, we give a tester whose query complexity is \( O\left( \frac{\alpha ^3k^2\log k}{\varepsilon ^2}\right) \) on graphs with arboricity bounded by \( \alpha \) . Previously, these properties were known to be testable with constant query complexity on general graphs under a stronger model with random edge sampling queries. By leveraging edge sampling simulation techniques, one can achieve \( \textrm{poly}(\log n) \) query complexity in the adjacency model for bounded arboricity graphs. In contrast, our algorithms achieve constant query complexity (for fixed \(\varepsilon \) and k) on a broader class of sparse graphs or the same class of bounded arboricity graphs. (3) For the diameter \( \le k \) property, we can distinguish whether a sparse graph has a diameter at most k or is \( \varepsilon \) -far from any graph that has a diameter at most \( k+2 \) with query complexity \( O\left( \frac{C^{\lfloor k/2\rfloor +1}}{\varepsilon ^{\lfloor k/2\rfloor +2}}\right) \) . Previously, a tester was known for general graphs that distinguishes between having a diameter at most k and being \(\varepsilon \) -far from any graph with diameter at most \(\beta (k)\) , where \(\beta (k)\) ranges from \(k+4\) to \(4k+2\) . We improve the upper bound on \(\beta (k)\) to at most \(k+2\) for sparse graphs, though at the cost of slightly higher query complexity.