Constant time testability of first-order logic with modulo counting on finitary graphs

Isolde Adler, Jenny Stimpson · 2026

Read Constant time testability of first-order logic with modulo counting on finitary graphs by Isolde Adler, Jenny Stimpson (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-10841.txt.

Introduction

Isolde Adler and Jenny Stimpson settle a question about testing graph properties in constant time. Earlier work showed that properties written in a rich counting logic could be tested in polylogarithmic time on graphs of bounded degree and treewidth, leaving open whether constant time was possible.

The pair answers yes for first-order logic with modulo counting on graph classes where both degree and component size stay bounded. Their proof adapts Hanf normal form to the setting and leans on a number-theoretic patchability condition that reads global facts from a constant-size local sample. The step up to the richer counting logic follows from an earlier expressiveness result.

Catalog record

CREATORIsolde Adler, Jenny Stimpson
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62522
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.10841

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Constant time testability of first-order logic with modulo counting on finitary graphs Isolde Adler, Jenny Stimpson Abstract This paper studies algorithmic meta theorems for property testing with constant running time in the bounded degree model. In (Adler, Harwath 2018) it was shown that on graph classes 𝒞 d w \mathcal{C}^{w}_{d} consisting of all graphs with both degree at most d d and treewidth at most w w , every problem expressible in monadic second-order logic with counting ( CMSO \operatorname{CMSO} ) is testable with polylogarithmic running time (where d , w ∈ ℕ d,w\in\mathbb{N} are fixed). It was left open whether this can be improved to constant running time. In this paper we give a positive answer for testing CMSO \operatorname{CMSO} on classes 𝒞 d c \mathcal{C}^{c}_{d} , where d d bounds the degree and c c bounds the component size. Our main result shows constant time testability of first-order logic with modulo counting ( FOMOD \operatorname{FOMOD} ) on 𝒞 d c \mathcal{C}^{c}_{d} . For our proof we tailor Hanf normal form of FOMOD \operatorname{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 \operatorname{FOMOD} to CMSO \operatorname{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. Keywords: Property testing, constant time algorithms, bounded degree model, algorithmic meta-theorems, first-order logic with modulo counting, monadic second-order logic. 1 Introduction The past decades have seen a tremendous increase in the volume of stored data, posing a huge challenge to computational power. Moreover, the data is often stored remotely, making access costly. In this context, even just reading the whole input once may be infeasible. Property Testing addresses this by the design of algorithms that derive global information on the structure of the input by only exploring a small number of local parts of it. These algorithms are randomised and allow for a small error. A property testing algorithm is required to distinguish inputs that satisfy a given property from inputs that are \varepsilon -far from satisfying the property with high probability correctly. Intuitively, an input is called \varepsilon -far from satisfying a property if more than an \varepsilon -fraction of the input needs to be modified in order to make it satisfy the property. The exact definition of the distance measure depends on the model. Our work is based on the bounded degree graph model of property testing introduced by Goldreich and Ron [ 11 ] . This model considers graphs whose degree ( i. e. the number of edges incident to any vertex) is bounded from above by a constant d\in\mathbb{N} . Formally, a property P is a class of graphs that is closed under isomorphism. Let \varepsilon\in(0,1) . Two d -bounded degree graphs G and H , both on n vertices, are called \varepsilon -close , if they can be made isomorphic by modifying (adding or deleting) at most \varepsilon dn edges. If G and H are not \varepsilon -close they are called \varepsilon -far . For a property P of d -bounded degree graphs, a graph G is \varepsilon -close to P , if G is \varepsilon -close to some member of P . Otherwise G is \varepsilon -far from P . The algorithms have oracle access to an input graph G of maximum degree d . Here we assume that the vertex set of G is \{1,2,\ldots,n\} . More precisely, an algorithm gets the number n as input, and it can access G via neighbour queries to an oracle, i. e. for any specified vertex v and index i\in\{1,2,\ldots,d\} , the oracle returns the i -th neighbour of v if it exists, and a special symbol \bot otherwise, in constant time. A property P is testable with query complexity q(n) in the bounded degree model, if for every \varepsilon\in(0,1) and every input size n there is a probabilistic algorithm A_{\varepsilon,n} (called an \varepsilon -tester ), that accepts G with probability at least 2/3 , if G\in P , and rejects G with probability at least 2/3 if G is \varepsilon -far from P , while using at most q(n) oracle queries. If q is independent of n , then P is constant-query testable . (Here q may depend on \varepsilon , d and P .) Until now, despite some effort, a characterisation of the properties that are constant-query testable in the bounded degree model is still elusive. Towards this goal, Newman and Sohler [ 15 ] proved a general result, showing that every property of planar graphs (and, more generally, of hyperfinite graphs) is constant-query testable. This theorem is a meta-theorem in the sense that it treats many properties simultaneously. In this paper we are interested in the running time , which is measured as usual in terms of n . For many individual properties is it easy to see that the query complexity of a tester dominates its running time. However, while a bound on the running time is also a bound on the query complexity, the converse is not true in general. Indeed, using the Newman-Sohler theorem it is not hard to see that there are undecidable properties that are constant query testable, as is noted in [ 2 ] ; the idea is to let the number of vertices of edgeless graphs represent the Goedel numbering of Turing machines, and to let the property be the class of graphs representing a Turing machine that halts on empty input. Since this property is a class of edgeless graphs it is hyperfinite and thus constant-query testable. In practice, sublinear running time is highly desirable . This motivates our aim of providing meta-theorems for property testing with constant running time . Towards this we use the framework of logic, which allows to treat many properties simultaneously. First-order logic on graphs (\textsc{FO}) speaks about the edge relation and allows quantification over vertices as usual. The logic \operatorname{FOMOD} extends FO by additional modulo counting quantifiers. Monadic second-order logic (\operatorname{MSO}) extends FO by quantification over subsets of vertices, and \operatorname{CMSO} extends \operatorname{MSO} by modulo counting quantifiers. The following result was shown in [ 2 ] . (Indeed, it was shown in the slightly more general setting of relational structures.) Theorem 1 ( [ 2 ] ) . Let d,w\in\mathbb{N} . On classes \mathcal{C}^{w}_{d} containing all graphs with both degree at most d and treewidth at most w every problem expressible in \operatorname{CMSO} is testable with polylogarithmic running time. In [ 2 ] it was stated as a open problem whether this can be improved to constant running time. 1 1 1 More precisely, this was asked for relational structures instead of graphs. In this paper we approach this question by considering finitary graph classes ( i. e. graph classes with a uniform upper bound on the component size). Results. By the classical Feferman-Vaught Theorem [ 10 ] it is known that satisfaction of a first-order formula only depends on the formulas that are satisfied by the connected components. Our contribution goes further by

Read the complete text