.png){kind=icon}
.png){kind=icon}
Return
Testing Some First-Order Logic Properties on Sparse Graphs
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-0218-9_8.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 <= k property. (1) For the k-dominating set property, we give a tester with query complexity O((kC)(k+1)/epsilon(k+2) log (kC/epsilon) on n-vertex graphs with at most Cn edges. Furthermore, if the input graph is planar, we improve the query complexity to O (k(6)/epsilon(3) log( k(2)/epsilon). (2) For the k-vertex cover property, we give a tester whose query complexity is O(alpha(3)k(2)/log k/e epsilon(2)) 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 poly(log n) query complexity in the adjacency model for bounded arboricity graphs. In contrast, our algorithms achieve constant query complexity (for fixed epsilon and k) on a broader class of sparse graphs or the same class of bounded arboricity graphs. (3) For the diameter <= k property, we can distinguish whether a sparse graph has a diameter at most k or is e-far from any graph that has a diameter at most k + 2 with query complexity O (Cleft perpendicular k/2 right perpendicular+1 epsilon(left perpendicular k/2 right perpendicular+2)). Previously, a tester was known for general graphs that distinguishes between having a diameter at most k and being epsilon-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.
Keywords:
EVERY PROPERTY
Journal
C
IF:
0
Papers:
24
Citations:
0