Constant time testability of first-order logic with modulo counting on finitary graphs
For property testing in bounded-degree graphs, this provides a constant-time testability result for a rich logical fragment on a natural class of graphs, addressing an open problem.
The paper proves that first-order logic with modulo counting (FOMOD) is testable in constant time on graph classes with bounded degree and bounded component size, improving from previous polylogarithmic bounds. The result extends to CMSO via known expressive power results.
This paper studies algorithmic meta theorems for property testing with \emph{constant running time} in the bounded degree model. In (Adler, Harwath 2018) it was shown that on graph classes $\mathcal C^{w}_d$ consisting of all graphs with both degree at most $d$ and treewidth at most $w$, every problem expressible in monadic second-order logic with counting (CMSO) is testable with \emph{polylogarithmic} running time (where $d,w\in \mathbb N$ are fixed). It was left open whether this can be improved to \emph{constant} running time. In this paper we give a positive answer for testing CMSO on classes $\mathcal C^{c}_d$, where $d$ bounds the degree and $c$ bounds the component size. Our main result shows constant time testability of first-order logic with modulo counting (FOMOD) on $\mathcal C^{c}_d$. For our proof we tailor Hanf normal form of FOMOD to our setting, and we exhibit a number-theoretic `patchability' condition that allows to infer global information on the input graph from a local sample of constant size. We believe that our `patchability' might be of independent interest. The step from FOMOD to CMSO then follows from a result by (Eickmeyer, Elberfeld, Harwath, 2017) on the expressive power of order invariant monadic second-order logic on classes of bounded treedepth.