We study the expressive power of first-order logic with counting quantifiers, especially the $k$-variable and quantifier-rank-$q$ fragment, using homomorphism indistinguishability. Recently, Dawar, Jakl, and Reggio~(2021) proved that two graphs satisfy the same $k$-variable and quantifier-rank-$q$ sentences if and only if they are homomorphism indistinguishable over the class of graphs admitting a $k$-pebble forest cover of depth $q$. After reproving this result using elementary means, we provide a graph-theoretic analysis of this graph class. This allows us to separate it from the intersection of the class of all graphs of treewidth at most $k-1$ and the class of all graphs of treedepth at most $q$, provided that $q$ is sufficiently larger than $k$. We are able to lift this separation to a (semantic) separation of the respective homomorphism indistinguishability relations. We do this by showing that the graph classes of all graphs of treedepth at most $q$ and of graphs admitting a $k$-pebble forest cover of depth $q$ are homomorphism distinguishing closed, as conjectured by Roberson~(2022). In order to prove Roberson's conjecture for the class of graphs admitting a $k$-pebble forest cover of depth $q$ we characterise the class in terms of a monotone Cops-and-Robber game.The crux is to prove that if Cop has a winning strategy then Cop also has a winning strategy that is monotone.To that end, we show how to transform Cop's winning strategy into a pre-tree-decomposition, which is inspired by decompositions of matroids, and then applying an intricate breadth-first `cleaning up' procedure along the pre-tree-decomposition (which may temporarily lose the property of representing a strategy), in order to achieve monotonicity while controlling the number of rounds simultaneously across all branches of the decomposition via a vertex exchange argument. arXiv admin note: text overlap with arXiv:2308.06044

We study a variation of the cops and robber game characterising treewidth, where in each round at most one cop may be placed and in each play at most q rounds are played, where q is a parameter of the game. We prove that if k cops have a winning strategy in this game, then k cops have a monotone winning strategy. As a corollary we obtain a new characterisation of bounded depth treewidth, and we give a positive answer to an open question by Fluck, Seppelt and Spitzer (2024), thus showing that graph classes of bounded depth treewidth are homomorphism distinguishing closed. Our proof of monotonicity substantially reorganises a winning strategy by first transforming it into a pre-tree decomposition, which is inspired by decompositions of matroids, and then applying an intricate breadth-first "cleaning up" procedure along the pre-tree decomposition (which may temporarily lose the property of representing a strategy), in order to achieve monotonicity while controlling the number of rounds simultaneously across all branches of the decomposition via a vertex exchange argument. We believe this can be useful in future research.

Abstract. We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that is defined by a formula with quantifier prefix [Formula: see text] is testable (i.e., testable with constant query complexity), while there exists an FO property that is expressible by a formula with quantifier prefix [Formula: see text] that is not testable. In the dense graph model, a similar picture has long been known [N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Combinatorica, 20 (2000), pp. 451–476] despite the very different nature of the two models. In particular, we obtain our lower bound by an FO formula that defines a class of bounded-degree expanders, based on zig-zag products of graphs. We expect this to be of independent interest. We then use our class of FO definable bounded-degree expanders to answer a long-standing open problem for proximity-oblivious testers (POTs). POTs are a class of particularly simple testing algorithms, where a basic test is performed a number of times that may depend on the proximity parameter, but the basic test itself is independent of the proximity parameter. In their seminal work, Goldreich and Ron [STOC 2009; SIAM J. Comput., 40 (2011), pp. 534–566] show that the graph properties that are constant-query proximity-oblivious testable in the bounded-degree model are precisely the properties that can be expressed as a generalized subgraph freeness (GSF) property that satisfies the non-propagation condition. It is left open whether the non-propagation condition is necessary. Indeed, calling properties expressible as a generalized subgraph freeness property GSF-local properties, they ask whether all GSF-local properties are non-propagating. We give a negative answer by showing that our FO definable property is GSF-local and propagating. Hence, in particular, our property does not admit a POT, despite being GSF-local. For this result we establish a new connection between FO properties and GSF-local properties via neighborhood profiles.

Property testing algorithms are highly efficient algorithms that come with probabilistic accuracy guarantees. For a property P , the goal is to distinguish inputs that have P from those that are far from having P with high probability correctly, by querying only a small number of local parts of the input. In property testing on graphs, the distance is measured by the number of edge modifications (additions or deletions) that are necessary to transform a graph into one with property P . Much research has focused on the query complexity of such algorithms, i. e., the number of queries the algorithm makes to the input, but in view of applications, the running time of the algorithm is equally relevant. In (Adler, Harwath, STACS 2018), a natural extension of the bounded degree graph model of property testing to relational databases of bounded degree was introduced, and it was shown that on databases of bounded degree and bounded tree-width, every property that is expressible in monadic second-order logic with counting (CMSO) is testable with constant query complexity and sublinear running time. It remains open whether this can be improved to constant running time. In this article we introduce a new model, which is based on the bounded degree model, but the distance measure allows both edge (tuple) modifications and vertex (element) modifications. We show that every property that is testable in the classical model is testable in our model with the same query complexity and running time, but the converse is not true. Our main theorem shows that on databases of bounded degree and bounded tree-width, every property that is expressible in CMSO is testable with constant query complexity and constant running time in the new model. Our proof methods include the semilinearity of the neighborhood histograms of databases having the property and a result by Alon (Proposition 19.10 in Lovász, Large networks and graph limits, 2012) that states that for every bounded degree graph \(\mathcal {G}\) there exists a constant size graph \(\mathcal {H}\) that has a similar neighborhood distribution to \(\mathcal {G}\) . It can be derived from a result in (Benjamini et al., Advances in Mathematics 2010) that hyperfinite hereditary properties are testable with constant query complexity and constant running time in the classical model (and hence in the new model). Using our methods, we give an alternative proof that hyperfinite hereditary properties are testable with constant query complexity and constant running time in the new model. We argue that our model is natural and our meta-theorem showing constant-time CMSO testability supports this.

In Property Testing, proximity-oblivious testers (POTs) form a class of particularly simple testing algorithms, where a basic test is performed a number of times that may depend on the proximity parameter, but the basic test itself is independent of the proximity parameter. In their seminal work, Goldreich and Ron [STOC 2009; SICOMP 2011] show that the graph properties that allow constant-query proximity-oblivious testing in the bounded-degree model are precisely the properties that can be expressed as a generalised subgraph freeness (GSF) property that satisfies the non-propagation condition. It is left open whether the non-propagation condition is necessary. Indeed, calling properties expressible as a generalised subgraph freeness property GSF-local properties, they ask whether all GSF-local properties are non-propagating. We give a negative answer by exhibiting a property of graphs that is GSF-local and propagating. Hence in particular, our property does not admit a POT, despite being GSF-local. We prove our result by exploiting a recent work of the authors which constructed a first-order (FO) property that is not testable [SODA 2021], and a new connection between FO properties and GSF-local properties via neighbourhood profiles.

We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that is defined by a formula with quantifier prefix ∃∗∀∗ is testable (i.e., testable with constant query complexity), while there exists an FO property that is expressible by a formula with quantifier prefix ∀∗∃∗ that is not testable. In the dense graph model, a similar picture is long known (Alon, Fischer, Krivelevich, Szegedy, Combinatorica 2000), despite the very different nature of the two models. In particular, we obtain our lower bound by a first-order formula that defines a class of bounded-degree expanders, based on zig-zag products of graphs. We expect this to be of independent interest. We then prove testability of some first-order properties that speak about isomorphism types of neighbourhoods, including testability of 1-neighbourhood-freeness, and r-neighbourhood-freeness under a mild assumption on the degrees.

Property testing algorithms are highly efficient algorithms, that come with probabilistic accuracy guarantees. For a property P, the goal is to distinguish inputs that have P from those that are far from having P with high probability correctly, by querying only a small number of local parts of the input. In property testing on graphs, the distance is measured by the number of edge modifications (additions or deletions), that are necessary to transform a graph into one with property P. Much research has focussed on the query complexity of such algorithms, i. e. the number of queries the algorithm makes to the input, but in view of applications, the running time of the algorithm is equally relevant. In (Adler, Harwath STACS 2018), a natural extension of the bounded degree graph model of property testing to relational databases of bounded degree was introduced, and it was shown that on databases of bounded degree and bounded tree-width, every property that is expressible in monadic second-order logic with counting (CMSO) is testable with constant query complexity and sublinear running time. It remains open whether this can be improved to constant running time. In this paper we introduce a new model, which is based on the bounded degree model, but the distance measure allows both edge (tuple) modifications and vertex (element) modifications. Our main theorem shows that on databases of bounded degree and bounded tree-width, every property that is expressible in CMSO is testable with constant query complexity and constant running time in the new model. We also show that every property that is testable in the classical model is testable in our model with the same query complexity and running time, but the converse is not true. We argue that our model is natural and our meta-theorem showing constant-time CMSO testability supports this.

The node search game against a lazy (or, respectively, agile) invisible robber has been introduced as a search-game analogue of the treewidth parameter (and, respectively, pathwidth). In the connected variants of the above two games, we additionally demand that, at each moment of the search, the clean territories are connected. The connected search game against an agile and invisible robber has been extensively examined. The monotone variant (where we also demand that the clean territories are progressively increasing) of this game, corresponds to the graph parameter of connected pathwidth. It is known that the price of connectivty to search for an agile robber is bounded by 2, that is the connected pathwidth of a graph is at most twice (plus some constant) its pathwidth. In this paper, we investigate the connected search game against a lazy robber. A lazy robber moves only when the searchers' strategy threatens the location that he currently occupies. We introduce two alternative graph-theoretic formulations of this game, one in terms of connected tree decompositions, and one in terms of (connected) layouts, leading to the graph parameter of connected treewidth. We observe that connected treewidth parameter is closed under contractions and prove that for every k >= 2, the set of contraction obstructions of the class of graphs with connected treewidth at most k is infinite. Our main result is a complete characterization of the obstruction set for k=2. One may observe that, so far, only a few complete obstruction sets are explicitly known for contraction closed graph classes. We finally show that, in contrast to the agile robber game, the price of connectivity is unbounded.

Aiming at extremely efficient algorithms for big data sets, we introduce property testing of relational databases of bounded degree. Our model generalises the bounded degree model for graphs (Goldreich and Ron, STOC 1997). We prove that in this model, if the databases have bounded tree-width, then every query definable in monadic second-order logic with modulo counting is testable with a constant number of oracle queries and polylogarithmic running time. This is the first logical meta-theorem in property testing of sparse models. Furthermore, we discuss conditions for the existence of uniform and non-uniform testers.

Conjunctive query (CQ) evaluation on relational databases is NP-complete in general. Several restrictions, like bounded and bounded hypertree-width, allow polynomial time evaluations.We extend the framework in the presence of functional dependencies. Our exteAnded CQ evaluation problem has a concise equivalent formulation in terms of the homomorphism problem (HOM) for non-relational structures. We introduce the notions of tree-width and tree-width for arbitrary structures, and we prove that HOM (and hence CQ) restricted to bounded (hyper)closure becomes tractable. There are classes of structures with bounded closure but unbounded tree-width. Similar statements hold for hyperclosure and hypertree-width, and for hyperclosure and closure tree-width.It follows from a result by Gottlob, Miklos, and Schwentick that for fixed k ≥ 2, deciding whether a given structure has hyperclosure at most k, is NP-complete. We prove an analogous statement for closure tree-width. Nevertheless, for given k we can approximate k-bounded closure in polynomial time.

A hypergraph pair is a pair $(G,H)$ where G and H are hypergraphs on the same set of vertices. We extend the definitions of hypertree-width [G. Gottlob, N. Leone, and F. Scarcello, J. Comput. System Sci., 64 (2002), pp. 579–627] and generalized hypertree-width [G. Gottlob, N. Leone, and F. Scarcello, J. Comput. System Sci., 66 (2003), pp. 775–808] from hypergraphs to hypergraph pairs. We show that for constant k the problem of deciding whether a hypergraph pair has generalized hypertree-width $\leq k$, is equivalent to the hypergraph sandwich problem (HSP) [A. Lustig and O. Shmueli, J. Algorithms, 30 (1999), pp. 400–422]. It was recently proved in [G. Gottlob, Z. Miklós, and Th. Schwentick, Proceedings of the Symposium on Principles of Database Systems $(PODS\/07)$] that the HSP is NP-complete. For constant k there is a polynomial time algorithm that decides whether a given hypergraph pair has hypertree-width $\leq k$. (For hypertree-width of hypergraphs, this was shown in [G. Gottlob, N. Leone, and F. Scarcello, J. Comput. System Sci., 64 (2002), pp. 579–627].) It follows that the HSP is solvable in polynomial time for inputs $(G,H)$ satisfying: $\operatorname{ghw}(G,H)\leq 1$ if and only if $\operatorname{hw}(G,H)\leq 1$. Besides this practical interest, hypergraph pairs serve as a tool for giving a common proof for the game theoretic characterizations of tree-width [P. D. Seymour and R. Thomas, J. Combin. Theory Ser. B, 58 (1993), pp. 22–33] and hypertree-width [G. Gottlob, N. Leone, and F. Scarcello, J. Comput. System Sci., 66 (2003), pp. 775–808]. Furthermore, they enable us to show a compactness property of generalized hypertree-width for a large class of hypergraphs, the hypergraphs with finite character. Finally, we present two examples showing that neither hypertree-width of hypergraph pairs nor hypertree-width of hypergraphs has the compactness property.