A characterization of one-sided error testable graph properties in bounded degeneracy graphs Oded Lachish, Amit Levi, Ilan Newman, Felix Reidl Abstract We consider graph property testing in p p -degenerate graphs under the random neighbor oracle model (Czumaj and Sohler, FOCS 2019). In this framework, a tester explores a graph by sampling uniform neighbors of vertices, and a property is testable with one-sided error if its query complexity is independent of the graph size. It is known that one-sided error testable properties for minor-closed families are exactly those that can be defined by forbidden subgraphs of bounded size. However, the much broader class of p p -degenerate graphs allows for high-degree “hubs” that can structurally hide forbidden subgraphs from local exploration. In this work, we provide a complete structural characterization of all properties testable with one-sided error in p p -degenerate graphs. We show that testability is fundamentally determined by the connectivity of the forbidden structures: a property is testable if and only if its violations cannot be fragmented across disjoint high-degree neighborhoods. Our results define the exact structural boundary for testability under these constraints, accounting for both the connectivity of individual forbidden subgraphs and the collective behavior of the properties they define. 1 Introduction The framework of graph property testing centers on randomized algorithms that, given query access to an input graph G , must distinguish between graphs satisfying a property \mathcal{P} and those that are \epsilon -far from it. A graph is considered \epsilon -far if an \epsilon -fraction of its representation must be modified to satisfy \mathcal{P} . The primary objective is to design algorithms whose query complexity is independent of the size of the graph. If the tester accepts any input satisfying the property with probability 1 , it is said to have one-sided error. The field was initiated by the seminal work of Goldreich, Goldwasser, and Ron [ GGR98 ] in the dense graph model. In this regime, graphs are represented by adjacency matrices, and testers can query any potential edge (u,v) . This line of research eventually led to a profound characterization of all testable graph properties in the dense graph model [ AFNS06 , AS05 , AS08 ] , both in general (with two-sided error) and for one-sided error testers. Another model that has received significant attention is the bounded-degree model, initially formulated in [ GR02 ] . Several significant results have been directed toward characterizing all testable properties within this model [ FPS19 , IKN20 , AKP24 ] . However, the question of a full characterization of all testable properties in this model remains open. Beyond the dense and bounded-degree regimes, graph property testing has been extensively studied over the past two decades in the general graph model, and more specifically for sparse graphs [ GR02 , PR02 , KKR04 , AKKR08 , NS11 , KY14 , BKN16 , CS19 , ELR24 , ELRR25 ] . There are several distinct models for the sparse graph regime, varying with respect to the allowed query types. The general graph model enables the study of properties in graphs with a bounded average degree. However, this strengthening comes at a price: even simple properties such as triangle-freeness [ AKKR08 ] and bipartiteness are no longer testable with a constant number of queries; rather, they require a query complexity that scales as a fractional power of the graph’s size. By contrast, both of these properties are testable in the dense- and bounded-degree models. These results indicated that the approach for this model should inherently differ from that of the dense and bounded-degree models. One solution was to restrict the family of input graphs, leading to new results that we discuss later. Czumaj and Sohler [ CS19 ] , who provided a characterization of the testable graph properties for minor-free graphs in the random neighbor oracle model, took a major step further. In this framework, the tester interacts with the graph by querying a vertex v and receiving a neighbor \boldsymbol{u} selected uniformly at random. This demonstrated that in a model slightly weaker than the general graph model, full characterizations are possible when the input is a member of the restricted family of minor-free graphs. This is to be contrasted with the fact that characterization of the testable graph properties (one- or two sided error) is not known, even for planar graphs. It is important to note that Czumaj and Sohler’s characterization of testable properties in this model is inherently tied to the nature of one-sided error. A one-sided error tester must accept any graph that satisfies the property \mathcal{P} with probability 1 . Consequently, it can reject an input graph only if it finds evidence of a violation: a set of edges that exist in the graph and explicitly forbid it from satisfying \mathcal{P} . Because the random neighbor oracle can only confirm the existence of edges (and never their absence), it is impossible for a constant-query tester to certify that a graph is, for instance, an induced cycle or a complete bipartite graph. This leads to the fundamental observation that every one-sided testable property in this model is equivalent to a monotone property characterized by a finite family of forbidden subgraphs \mathcal{F} . If a graph is \epsilon -far from being \mathcal{F} -free, the tester must be able to find a copy of at least one H\in\mathcal{F} with high probability. These observations gave rise to the main tool that Czumaj and Sohler used for their result: proving that H -freeness is testable for every graph H in the family of interest. Our paper focuses on understanding what happens in much larger graph families where we know that H -freeness is not testable for every graph in the family. The goal of this line of research is to discover the tools required to characterize the testable properties of natural graph families in the random neighbor oracle model. In this paper, we study properties of p -degenerate graphs for a constant p (also known as (p,1) -admissible graphs, and bounded-arboricity graphs). A graph is p -degenerate if its vertices can be ordered so that every vertex has at most p neighbors preceding it in the ordering. Note that while the average degree of a p -degenerate graph is bounded, such a graph may still contain vertices of any arbitrarily high degree. The structural definition of p -degenerate graphs is robust, as it admits several equivalent characterizations. In particular, it is related to bounded arboricity , where the arboricity of the graph is \Theta(p) . p -degenerate graphs significantly generalize planar graphs and all minor-free classes, 1 1 1 The class of bounded-arboricity graphs contains an infinite nested collection of subfamilies—the family of (p,r) -admissible graphs, r\in\mathbb{N} —each of which contains all minor-free graphs. providing a rich landscape for studying properties in graphs with unbounded degrees. Indeed, much of the recent study on graph property testing and local algorithms has focused on this family [ ERR19 , ERS20 , Lev21 , EMR22 , ERR22 , ELR24 ] . 1.1 Our results In this work, we provide a complete structural characterization of the one-sided error testable properties for bounded-degeneracy graphs under the random neighbor oracle model. The logical progression of our proof proceeds as follows: • Reduction to a forbidden family: It is standard to note that any one-sided error testable graph property is equivalent to being \mathcal{H} -free for a finite family of forbidden subgraphs \mathcal{H} . Hence, we only consider testing \mathcal{H} -freeness, for a finite fixed set of forbidden graphs \mathcal{H} . • Characterization of H -freeness: We start with \mathcal{H}=\{H\} , namely a unique forbidden graph H , and characterize those H ’s for which H -freeness is one-sided error testable in the random neighbor model. The characterization is essentially about the connectedness of H . While the testability of each individual H\in\mathcal{H} is a sufficient condition for the testability of the family \mathcal{H} , this condition is not necessary . As a motivating example (discussed further in Section 4 ), consider the property of forbidding the 4 -cycle C_{4} , and the star with 10 leaves \mathrm{ST}_{10} . While C_{4} -freeness is non-testable in general p -degenerate graphs [ ELR24 ] , the property of \mathcal{H}=\{C_{4},\mathrm{ST}_{10}\} -freeness is testable. The inclusion of the star in the forbidden set ensures that any graph satisfying the property has a maximum degree of at most 9 . In this bounded-degree regime, the structural “blind spots” that would normally hide C_{4} are prohibited, rendering the collective property to be testable. The fact that individual testability is not necessary forces us to look deeper at the interaction between the forbidden subgraphs and the specific input graphs that attempt to hide them. This leads to our next two core results: • Sufficient conditions of testable input instances: We further characterize some specific classes of p -degenerate graphs \mathcal{G} for which H -freeness is testable, even when H is not generally testable. • Characterization of testable families of forbidden graphs: Testing \mathcal{H} -freeness may be possible even if \mathcal{H} contains a graph H that is not testable in general. We show that this occurs because, if an input graph G is far from being \mathcal{H} -free, it must fall into one of two scenarios: (i) G is far from H^{\prime} -freeness for a graph H^{\prime}\in\mathcal{H} , and for which H^{\prime} -freeness is testable (for an easy and obvious reason). (ii) G is far from being H -free for H\in\mathcal{H} for which H -freeness is not testable in general, but, either H -freeness is testable for the particular graph G , or — the fact that G has many copies of H implies that it also has many copies of some H^{\prime}\in\mathcal{H} for which H^{\prime} -freeness is testable. Using the sufficient condition above of testable input instances, we provide a final characterization for general families \mathcal{H} . We show that a family is testable if every configuration that is “hard” to test for one member H_{i}\in\mathcal{H} is effectively prohibited or ’exposed’ by the presence of another member H_{j}\in\mathcal{H} for which H_{j} -freeness is testable. 1.2 Technical Overview We begin with the standard observation that any tester in the random neighbor oracle model can be simplified to a canonical tester. This tester selects a set of initial nodes at random and initiates a local graph exploration (of constant depth) from each. Its decision to accept or reject is based solely on the subgraph discovered during this exploration (see Section 2 ). Crucially, a tester in this model only knows for sure that there exist edges between a queried vertex and a random vertex returned by the oracle; it cannot verify the non-existence of an edge in this model, and hence a one-sided error tester can only reject if it discovers a set of edges that form a forbidden subgraph. Therefore, a property is one-sided error testable in this model only if it is \mathcal{H} -free for some fixed size set \mathcal{H} of forbidden graphs. Next, we start (a main part of the paper) with the characterization of properties defined by a single forbidden subgraph H . So, for a fixed graph H , we say that H is testable if H -freeness is testable for every bounded degeneracy graph, and otherwise we say that H is not testable. A first and relatively simple observation is that H is testable if and only if each 2-connected block (maximal 2 -connected subgraph) of it is testable. This reduces the general characterization task to that of 2 -connected H ’s. We prove the following theorem (formally referred to as Theorem 4 ). Theorem 1 . H -freeness is one-sided error testable for a 2 -connected graph H if and only if for every independent set S\subseteq V(H), the subgraph induced by V(H)\setminus S is connected. In order to better understand our necessary condition, it is illuminating to consider the special case where H is a labeled C_{4}=\{a,b,c,d\} with separator S=\{a,c\} that is an independent set. The reason why H is not testable follows from the following distribution on “hard-to-test” graphs. We construct a 2 -degenerate graph G on 2n+2\sqrt{n} vertices as follows: A and C are two disjoint sets of \sqrt{n} vertices of high degree, called “hubs”. In addition L_{1},L_{2} are two n -sized disjoint sets of degree 2 vertices. Each vertex v\in L_{1} is connected to a unique pair of hubs (i,j)\in A\times C . Similarly, the same is done for each u\in L_{2} . Hence, every pair (i,j)\in A\times C is connected by a 2 -path through L_{1} and another 2 -path through L_{2} forming a copy of C_{4} . Altogether, the graph G is 2 -degenerate (with the order of A,C first, followed by L_{1}\cup L_{2} ). Further, G contains n edge-disjoint copies of C_{4} (one for each unique pair of hubs). This ensures that the graph is \Omega(1) -far from being C_{4} -free. The difficulty of finding a C_{4} where the vertices are randomly permuted is due to the fact that in order to find a C_{4} -copy one needs to find a specific pair (i,j)\in A\times C , and the two corresponding u\in L_{1},~v\in L_{2} that are a “matched” pair, each connected to the same i,j . Because the oracle returns a random neighbor, a tester querying a hub vertex i is essentially pulling a “random ticket” for a path to some hub j . The core of the lower bound lies in the independence of L_{1} and L_{2} and the large degree of the vertices of A and C . The probability of finding such a match u,v is vanishingly small (with respect to n ). Specifically, after \ell queries, we show that the probability of finding a C_{4} is only O(\ell^{2}/\sqrt{n}) - this is essentially by the birthday-paradox argument. Hence, a lower bound of \Omega(n^{1/4}) is obtained for the number of queries. This argument is generalized to every H for which there is a separating independent set S as stated in the theorem. To prove the sufficient condition for testability, we note that if the graph G has degree bound h for any constant h , then H -freeness is testable (for any H ) 2 2 2 this is quite standard - if G is bounded degree, then sampling a vertex v , v will be in a H -appearance w.h.p. Then, running a depth |H| BFS starting from v will find this H -appearance. . Hence, we define for an input graph G , the set of heavy vertices; these are vertices of degree higher than some suitable constant h . We then employ a two-stage “cleaning” procedure. Since a one-sided tester only rejects upon finding an explicit copy of H , we can conceptually “remove” edges that are difficult to sample without significantly changing the graph’s distance from being H -free (if the original graph G is \epsilon -far from H -freeness, the resulting graph remains \Omega(\epsilon) -far). • Degree-based cleaning: We first remove all edges between high-degree vertices (“heavy” nodes). • Density cleaning: We further refine the graph to ensure that any heavy vertex that participates in an H -copy actually participates in a large number of such copies. This step ensures that the random neighbor oracle has a non-negligible probability of sampling a “useful” neighbor from a random heavy vertex. The above conceptual process allows us to prove that if a 2 -connected H has no independent sets that are separating (unlike a C_{4} ), and G is far from H -freeness, then at least one of the following is true: (a) G contains many H -copies in which all of its vertices are non-heavy; in this case, finding an H -copy is easy, as in a bounded degree graph; (b) G contains many H -copies in which there are some heavy vertices, but that are not separating — then, again as in the bounded degree case, an H copy can be found by making a suitable BFS induced only on non-heavy vertices. Such a search will find an H copy, as H is not separated by the heavy vertices that it might contain. Next, we move to the characterization of when \mathcal{H} -freeness is testable, for a family of forbidden graphs \mathcal{H} (the other main part of the paper). An easy observation is that if all members in \mathcal{H} are testable, then \mathcal{H} -freeness is testable. However, the converse is not generally correct. The non-testability of a graph H_{1}\in\mathcal{H} does not necessarily “doom” the testability of a family \mathcal{H} containing it. The inclusion of additional forbidden subgraphs \{H_{2},\ldots,H_{\ell}\} can “rescue” the property by fundamentally altering the structural regime in which the tester operates. As we saw in the lower bound construction, hiding C_{4} ’s requires the existence of high-degree vertices. Let \mathrm{ST}_{10} be the star with 10 leaves. If we consider the example discussed above where \mathcal{H}=\{C_{4},\mathrm{ST}_{10}\} , the canonical tester rejects in the case of the lower bound construction described, because with high probability it discovers \mathrm{ST}_{10} . The crux of our work is to generalize this to any family \mathcal{H} . The above example turns out to be just a simple example that does not exhibit the real complexity of the problem. The full characterization of when \mathcal{H} -freeness is testable is stated in Theorem 7 . It is not stated right here as it requires some preliminary technical preparations. However, the logic that we apply is the following. Let H_{1}\in\mathcal{H} be non-testable. As we construct some specific graphs that are far from H_{1} -free and are hard to test for H_{1} -freeness, to be able to test \mathcal{H} -freeness it must be that for some H\in\mathcal{H} that is testable, the specific hard to test graphs that we design must have many copies of H . This already places some restrictions on the possible testable members of \mathcal{H} . This motivates our definition of the cactus-representation relative to a non-testable H_{1} and its separating independent set S (Definition 10 ). Intuitively, a cactus is a “thin” structure where the components are subgraphs of H_{1} (petals) that are attached to each other at a single articulation point. We first identify a sufficient condition under which for a graph G that is far from H_{1} -free, H_{1} -appearance can be found in O(1) -queries. Conversely, for cases where H_{1} -freeness is not generally testable, we demonstrate that G must contain many copies of some testable H\in\mathcal{H} , provided that H admits the appropriate cactus representation. Ultimately, we prove that a family \mathcal{H} is testable if and only if for every non-testable H_{i} , there exists a cactus H_{j}\in\mathcal{H} that is structurally forced to be exposed. In this regime, a p -degenerate graph cannot be far from \mathcal{H} -freeness without creating a detectable trail of these cactus structures, which the random neighbor oracle will discover with high probability. 1.3 Related work Testing properties of sparse graph has been studied extensively under different models of access. In the general graph model [ PR02 , KKR04 , AKKR08 ] , the algorithm can only use queries of these three types: degree query where for an input v the oracle returns \deg(v) , neighbor query where for an input v and i\in[n] it returns the i -th neighbor (or a special character \bot if \deg(v)0 and random neighbor oracle access to a graph G with n vertices. The algorithm makes at most q random neighbor queries to the input and satisfies the following. If the graph is \epsilon -far from \mathcal{P} , then the algorithm rejects with probability at least 2/3 . If G\in\mathcal{P} , then the algorithm accepts with probability at least 2/3 . The tester has one-sided error if it accepts every G\in\mathcal{P} with probability 1 , and otherwise it has a two-sided error . Our focus in this work is on one-sided error testers in the random-neighbor model. In this model, the oracle access to the graph is by the random neighbor oracle, where an algorithm may query any vertex v\in V(G) and the oracle returns a vertex \boldsymbol{u} chosen uniformly at random from the set of neighbors of v in G . Thus, for non-bounded degree graphs, a degree of a vertex, as well as the existence or non-existence of an edge between a pair of vertices cannot be determined in constant time. An O(1) -query tester can only discover a constant size subgraph of the input graphs and form its decision only on this subgraph. A one-sided error tester in the model can thus reject only on discovering a forbidden subgraph, and hence can accept only downwards monotone properties. We say that a property \mathcal{P} is testable if it has a tester with query complexity which is independent on the graph size n , but may depend on \epsilon and possibly some structural parameters of the input graphs (such as the degeneracy p ). We sometimes use the notion of an \epsilon -test, referring to a (non-uniform) property tester in which the proximity parameter \epsilon is fixed in advance, as opposed to the standard uniform setting where \epsilon is given as input to the tester. Canonical Testers The following result from [ CS19 ] provides a canonical way of describing any tester in the random neighbor oracle model. To analyze the local structure around a vertex v , we use a specialized Bounded-BFS subroutine. The procedure explores the graph up to a fixed depth t using a random-neighbor oracle. To remain query-efficient, the algorithm uses a fixed sampling parameter s : at each vertex encountered, the search probes exactly s neighbors chosen uniformly at random. The value of s is chosen specifically to ensure that if a vertex is “light” (its degree is below a certain threshold h ), the algorithm will have sampled all of its neighbors with high probability. This allows the search to behave like a standard BFS for low-degree regions while providing a representative sparse sample of higher-degree neighborhoods. A formal description of the Bounded-BFS procedure and the derivation of the sampling parameter s are provided in Appendix A . Theorem 2 . Let \mathcal{P}=(\mathcal{P}_{n})_{n\in\mathbb{N}} be a graph property that can be tested in the random neighbor oracle model with q queries and error probability at most 1/3 . Then, for every \epsilon>0 , there exists q^{\prime}=\Theta(q) and a sequence \mathcal{Q}=(\mathcal{Q}_{n})_{n\in\mathbb{N}} such that for every n\in\mathbb{N} , \mathcal{Q}_{n} is a set of bounded q -size graphs. The property \mathcal{P}_{n} (of n vertex graphs) can be tested with error probability at most 1/3 by the following canonical tester that uses q^{O(q)} queries: (1) Sample a multi-set \mathbf{S} of q^{\prime} vertices uniformly at random. (2) For each sampled vertex \boldsymbol{v}\in\mathbf{S} run Bounded-BFS (G,v,q^{\prime},q^{\prime}) and obtain the explored subgraph G^{\prime}_{\boldsymbol{v}} . (3) If the union of explored \{G^{\prime}_{\boldsymbol{v}}\}_{\boldsymbol{v}\in\mathbf{S}} contains an element Q\in\mathcal{Q}_{n} , then the tester rejects and otherwise it accepts. Additionally, if \mathcal{P} can be tested with one sided error in the random neighbor oracle model, then the canonical tester for \mathcal{P} also has one-sided error. We refer to such a tester as a q^{\prime} -canonical tester . The above shows that, without loss of generality, one can assume that any testable property can be tested by a canonical tester with constant (independent of the input size) query complexity. In particular, this implies that for one-sided error testers, the test can reject only upon discovering a forbidden subgraph. This implies the following definitions. We say that a graph G is H -free if G does not contain H as a subgraph and denote by \mathcal{P}_{H} the family of all such graphs. Correspondingly, G is said to be \epsilon -far from being H -free (alternatively, H -freeness) if more than \epsilon|V(G)| edges must be deleted from G in order to make it H -free. These definitions extend naturally to families of forbidden graphs. If \mathcal{H} is a finite family of finite graphs, G is \mathcal{H} -free if it is H -free for every H\in\mathcal{H} . We denote by \mathcal{P}_{\mathcal{H}} the property of all graphs that are \mathcal{H} -free, and define the distance analogously. We note that \mathcal{P}_{\mathcal{H}} is a downwards monotone graph property for any collection \mathcal{H} . Moreover, every downwards monotone property can be described by \mathcal{P}_{\mathcal{H}} for some (possibly infinite) collection of forbidden graphs \mathcal{H} . It is standard (see also [ CS19 , CFPS20 ] ) that only properties of the form \mathcal{P}_{\mathcal{H}} for a finite collection of bounded size forbidden graphs \mathcal{H} are one-sided error testable in the random-neighbor model. Our goal is to characterize these families \mathcal{P}_{\mathcal{H}} for which \mathcal{P}_{\mathcal{H}} -freeness is one-sided error testable. As a one-sided error test rejects only if it finds an H -appearance in the input graph G , for H\in\mathcal{P}_{\mathcal{H}} , we may assume in what follows that the input graph G is always \epsilon -far from being \mathcal{P}_{\mathcal{H}} -free, and will characterize these family for which such a graph H\in\mathcal{P}_{\mathcal{H}} can be found with \Omega(1) probability. The following standard fact relates G being \epsilon -far from being \mathcal{P}_{\mathcal{H}} -free in the aforementioned Hamming metric to the presence of a linear number of edge-disjoint forbidden subgraphs in G . Lemma 2.2 . Let \mathcal{H} be a r -collection of k -size graphs. If graph G is \epsilon -far from \mathcal{H} -free then it has an edge-disjoint collection \mathcal{H}(G) , of size at least \epsilon n/krp of H -appearances, for some H\in{\mathcal{H}} (note that if k\geq p , then we have at least \epsilon n/rk^{2} such appearances). Proof. Let \mathcal{C} be any maximal collection of edge-disjoint appearances of \mathcal{H} -members in G . Removing all edges in every such appearance results in a H -free graph, and the lemma follows. ∎ An Important Note: In our characterization we think of the family of input graphs as p -degenerate for some p=O(1) . Namely, if we say that \mathcal{H} -freeness is testable for p -degenerate graphs, we mean that it so for any p=O(1) , with the test knowing p (and in particular, its query complexity may depend on p) . On the other hand, if \mathcal{H} -freeness is not testable, that means that for every p=O(1),~p\geq p^{*} , for some constant p^{*} that may depends on \mathcal{H} , no algorithm of constant query complexity can test \mathcal{H} -freeness against every p -degenerate graph. 3 Testing H -freeness for p -degenerate graphs Throughout, we fix H=(V(H),E(H)) to be an arbitrary simple, undirected graph. We start with the following simpler property of being H -free for a fixed graph of (constant) size k , H=(V(H),E(H)) . The following is a simple fact stated for the one-sided error testability of being H -free. In what follows, G is always an n -vertex p -degenerate graph that has a linear size collection \mathcal{H}(G) of H -appearances, as stated in Lemma 2.2 . Definition 6 (semi-bipartite structure) . Let G=(V,E) . For a natural number h\in\mathbb{N} (usually a fixed integer independent of n but may be a function of \epsilon and the graph H ) let \textrm{Heavy}_{h}=\{v\in V(G)\mid~\deg(v)\geq h\} and \textrm{Light}_{h}=V(G)\setminus\textrm{Heavy}_{h} . We say that G is semi-bipartite with respect to \textrm{Heavy}_{h} if \textrm{Heavy}_{h} is an independent set in G . Lemma 3.1 . Let p\in\mathbb{N} , \epsilon>0 and h\geq 4p^{2}/\epsilon . If G is p -degenerate and \epsilon -far from a monotone graph property \mathcal{P} , then there exists a spanning subgraph G^{\prime} of G , obtained by deleting at most \epsilon n/2 edges, which is semi-bipartite with respect to \textrm{Heavy}_{h} , and is \epsilon/2 -far from \mathcal{P} . In particular G^{\prime} contains a collection of edge-disjoint H -appearances as in Lemma 2.2 . Proof. By the assumption that G is p -degenerate, any size t subgraph of G has at most tp edges. By averaging (using that |E(G)|\leq pn ) we conclude that |\textrm{Heavy}_{h}|\leq 2pn/h . Hence, G[\textrm{Heavy}_{h}] has at most 2p^{2}n/h edges. Thus, since h\geq 4p^{2}/\epsilon , deleting these edges results in a graph G^{\prime} that is semi-bipartite with respect to \textrm{Heavy}_{h} and is \epsilon/2 -far from \mathcal{P} . ∎ We use G^{\prime} only as a conceptual object in the analysis. The tester is one-sided and rejects only upon discovering a constant-size forbidden subgraph. Since G^{\prime}\subseteq G , any forbidden subgraph found in G^{\prime} is also present in G , and therefore constitutes a valid witness for rejecting G . On no-instances, although deleting edges may remove some forbidden subgraphs, our analysis shows that if G is \epsilon -far from the property, then the resulting graph G^{\prime} still contains many forbidden subgraphs of the relevant type. In view of Lemma 3.1 and the discussion above, we may henceforth assume that the input graph G is semi-bipartite with respect to the appropriate parameter h . More specifically, we state the following: Remark 1 . As we consider only one-sided error tests of downward monotone properties, we may assume in what follows that all our input graphs are \epsilon -far from being H -free for some forbidden k -size graph H , and have the semi-bipartite property with respect to \textrm{Heavy}_{h} . In particular, the input graph G has an edge-disjoint collection \mathcal{H}(G) , of H -appearances of size at least \epsilon n/kp (note that if k\geq p , then we have at least \epsilon n/k^{2} such appearances). Our aim is to characterize the graphs H for which there is a test, under the above assumption, that can find an H -appearance with high probability. We first consider the easy case 5 5 5 This case is also treated in all previous studies of the bounded degree models. in which \mathcal{H}(G) contains at least \Omega(\epsilon n/kp) H -appearances H^{\prime} for which \textrm{Heavy}_{h}\cap V(H^{\prime})=\emptyset . Lemma 3.2 . Fix h\in\mathbb{N} and suppose G is semi-bipartite with respect to \textrm{Heavy}_{h} and \epsilon -far from \mathcal{P}_{H} . If all the H -appearances in \mathcal{H}(G) contain only vertices in \textrm{Light}_{h} , then there exists a one-sided error q_{H} -canonical \epsilon -tester for \mathcal{P}_{H} , where q_{H}=O(\max(kp/\epsilon,h)) . Proof. Since \mathcal{H}(G) contains \Omega(\epsilon n/kp) edge-disjoint appearances H^{\prime} containing only vertices in \textrm{Light}_{h} , a q_{H} -canonical tester finds a vertex v in such appearance H^{\prime} with high probability. Conditioned on this event, and the fact that all vertices in such appearance are light, the explored subgraph centered around v contains H^{\prime} as a subgraph, causing the tester to reject. ∎ In view of Lemma 3.2 , we assume in what follows that our input graphs G have the property that every H -appearance in \mathcal{H}(G) contains a \textrm{Heavy}_{h} vertex. We first argue that there exists a collection \mathcal{H}^{\prime}(G)\subseteq\mathcal{H}(G) of H -appearances, such that for every H^{\prime}\in\mathcal{H}^{\prime}(G) every vertex v\in V(H^{\prime})\cap\textrm{Heavy}_{h} participates in many other H -appearances. Definition 7 . Let G,\mathcal{H}(G) be as in Remark 1 . For \delta\in(0,1] , we say that v\in\textrm{Heavy}_{h} is \delta -good if at least \delta\deg(v) of its edges appear in an H -appearance in \mathcal{H}(G) . In that case we also call the edge that appears in an H -appearance \delta -good. Finally, we call an H -appearance in \mathcal{H}(G) \delta -good if all its edges adjacent to vertices in \textrm{Heavy}_{h} are \delta -good. Lemma 3.3 . Fix \delta\in(0,1] and let G=(V,E) be \epsilon -far from being H -free with properties as in Remark 1 . Then there are at least (\frac{\epsilon}{kp}-2\delta p)n \delta -good edges, and at least (\frac{\epsilon}{kp}-2\delta p)n \delta -good appearances in \mathcal{H}(G) . In particular, there exists a sub-collection \mathcal{H}^{\prime}(G)\subseteq\mathcal{H}(G) of size at least (\frac{\epsilon}{kp}-2\delta p)n where each member in the collection is \delta -good. Proof. Trivial, as there are at most \sum_{v\in\textrm{Heavy}_{h}}\delta\deg(v)\leq 2\delta pn edges that are not \delta -good. ∎ Theorem 3 . H -freeness is one-sided error testable for p -degenerate graphs if and only if for each 2-connected block H^{\prime} of H , H^{\prime} -freeness is one-sided error testable for p -degenerate graphs. The proof of Theorem 3 is a direct consequence of Lemma 3.4 and Lemma 3.5 below. We provide the proofs for both lemmas in Appendix B . Lemma 3.4 . Fix \epsilon>0 and q\in\mathbb{N} . Let H be a graph on k vertices and suppose that u\in V(H) is a separating vertex of H . Let H_{1} be a component of H\setminus\{u\} and H_{2}=H\setminus\{V(H_{1})\cup\{u\}) . If \mathcal{P}_{H_{1}} is not one-sided error \epsilon -testable with q queries on p -degenerate graphs, then \mathcal{P}_{H} is not one-sided error \epsilon/k -testable with q queries for p^{\prime} -degenerate graphs for p^{\prime}=O(p) . Lemma 3.5 . Suppose that H=(V(H),E(H)) is a connected graph on k vertices. Let \mathcal{B}=(H_{1},\ldots,H_{\ell}) be a 2-block decomposition of H (as given in Lemma 2.1 ). If for every 2-block H^{\prime}\in\mathcal{B} , the property \mathcal{P}_{H^{\prime}} is one-sided error \epsilon/k -testable with q_{H^{\prime}} queries for the family of p -degenerate graphs then \mathcal{P}_{H} has a one-sided error q_{H} -canonical \epsilon -tester where q_{H}=O\left(\sum_{H^{\prime}\in\mathcal{B}}\max\left(q_{H^{\prime}},\frac{(kp)^{2}}{\epsilon}\right)\right) . 3.1 Testing H -freeness for 2-connected H In what follows, we prove the main theorem that characterizes the 2-connected graphs H for which \mathcal{P}_{H} is one-sided error testable on the family of p -degenerate graphs. By Theorem 3 , this implies a full characterization of graphs H for which \mathcal{P}_{H} is testable. Theorem 4 . \mathcal{P}_{H} is one-sided error testable for a 2 -connected graph H if and only if H has the following property: for any independent set S\subseteq V(H) the subgraph induced by V(H)\setminus S is connected. To establish necessary condition of Theorem 4 , we define a distribution of p -degenerate graphs that are far from \mathcal{P}_{H} but difficult to distinguish from H -free graphs. The following definition will be useful for describing the lower bound. Definition 8 . Let H be a 2 -connected graph, S\subseteq V(H) an independent set in H . If S is a minimal-separating set, we call S an obstacle for H . Definition 9 (Lower bound construction) . Let H be a graph and S=\{v_{1},\ldots,v_{r}\} be an obstacle such that H\setminus S consists of t\geq 2 components C_{1},\ldots,C_{t} . Set m to be the largest integer such that 2m+(r-2)+m^{2}\sum_{\ell=1}^{t}|V(C_{\ell})|\leq n and note that m=\Theta\left(\sqrt{\frac{n}{k}}\right) . We define a graph G(H,S) as follows. • Let A , C be two disjoint sets of vertices of size m , and W be a set of r-2 fixed vertices. • For each component C_{\ell} of H\setminus S , we define a disjoint set of vertices L_{\ell} of size |V(C_{\ell})|\cdot m^{2} . • For every pair (i,j)\in A\times C , we form an edge disjoint copy of H where i takes the role of v_{1} , and j takes the role of v_{2} , the set W takes the roles of \{v_{3},\ldots,v_{r}\} and t unique, vertex-disjoint components from L_{1},\ldots,L_{t} take the roles of C_{1},\ldots,C_{t} (see Figure 1 for an illustration). • The distribution \mathcal{D} is generated by applying t independent uniform permutations \boldsymbol{\pi}_{1},\ldots,\boldsymbol{\pi}_{t} to the labels of the vertices within each L_{1},\ldots,L_{t} . Lemma 3.6 . Let H be a 2 -connected graph, S\subseteq V(H) an obstacle. Then there is a distribution \mathcal{D} on n -vertex graphs, each being p -degenerate and \epsilon -far from \mathcal{P}_{H} , such that any one-sided error test making q=o(n^{1/4}) queries finds a copy of H with probability o(1) . Proof. To better understand our lower bound construction, we start with the extremely simple case where H is the labeled C_{4}=(a,b,c,d) , with obstacle S=\{a,c\} . The construction in Definition 9 defines a graph F on 2m+2m^{2} vertices with two disjoint sets A,C of size m , and two disjoint sets L_{1},L_{2} of size m^{2} . For each (i,j)\in A\times C there is a unique v=v_{i,j}\in L_{1} that is connected to both i and j , and similarly, a unique v^{\prime}_{i,j}\in L_{2} that is connected to i,j . Note that for every pair (i,j)\in A\times C , \{i,j,v_{i,j},v^{\prime}_{i,j}\} form a C_{4} in F . Thus, there are m^{2} such C_{4} -copies that are edge disjoint. This construction implies that F is 2 -degenerate and 1/4 -far from \mathcal{P}_{H} . Now the distribution \mathcal{D} is generated by permuting the vertices in L_{1} and L_{2} via two independent random permutations \boldsymbol{\pi}_{1},\boldsymbol{\pi}_{2} of [m] . To prove the lower bound, we note that each query targets either a vertex v\in L_{1}\cup L_{2} or a vertex i\in A\cup C . In the first case, assuming without the loss of generality that v\in L_{1} , the oracle reveals the unique neighbors i\in A and j\in C such that \boldsymbol{\pi}_{1}(i,j)=v . In the second case, a random neighbor query to i\in A\cup C returns a vertex v\in L_{1}\cup L_{2} and its other neighbor j , which similarly identifies a triplet (i,v,j) . Since \boldsymbol{\pi}_{1} and \boldsymbol{\pi}_{2} are uniform and independent, the specific labels of vertices in L_{1}\cup L_{2} provide no information beyond identifying the 2 -path between i and j through either L_{1} or L_{2} . Thus, we may assume each query simply discovers a pair (i,j)\in A\times C connected via a vertex in one of the two sets. Let Q_{\ell} be the set of pairs discovered after \ell queries, partitioned into P_{1} , the pairs connected via L_{1} , and P_{2} - the pairs connected via L_{2} . A C_{4} is detected only if there exists some (i,j) such that v_{i,j}\in P_{1} and v_{i,j}\in P_{2} , both that are connected to the same two vertices i,j , are discovered. Consider the (\ell+1) -th query to a neighbor of i\in A , and note that there are 2m neighbors incident to i : m in L_{1} and m in L_{2} . If the oracle returns a vertex v=v_{i,j}\in L_{1} , a C_{4} is discovered only if the vertex v^{\prime}_{i,j} was already discovered in P_{2} . Because \boldsymbol{\pi}_{1} and \boldsymbol{\pi}_{2} are independent, the mapping of neighbors in L_{1} is unknown regardless of the vertices found in P_{2} . At step \ell+1 , there are at most |P_{2}|\leq\ell such “matching” vertices in L_{1} . Since the oracle selects from 2m total neighbors for vertex i , the probability that the query returns a neighbor completing a C_{4} is at most \frac{\ell}{2m} . The total success probability after \ell queries is bounded by: \sum_{j=1}^{\ell}\frac{j}{2m}=\frac{\ell(\ell+1)}{4m} . For this probability to be \Omega(1) , we require \ell=\Omega(\sqrt{m}) . Given n\approx 2m^{2} , we have m\approx\sqrt{n/2} , yielding a lower bound of \ell=\Omega(n^{1/4}) . Thus, any tester making o(n^{1/4}) queries fails to find a C_{4} with high probability. Consider now the case where the 2 -size obstacle S=\{a,b\} , and H\setminus S contains t components C_{1},\ldots,C_{t} of sizes c_{r} for r\in[t] . We will define \mathcal{D} in a similar conceptual way. We start with a fixed graph where A,C will contain m=\Theta(\sqrt{n}) nodes as before. We further will have t sets L_{1},\ldots,L_{t} each of size c_{r}\cdot m^{2} for r\in[t] , with the intention, as in the very simple case above, that for each (i,j)\in A\times C , taking the role of a,b respectively, we will form a unique H -appearance by forming t vertex disjoint components, C_{r}(i,j) isomorphic to C_{r} , ~r\in[t] , where for C_{r} we use vertices from L_{r} . Thus for each (i,j) we will get a disjoint copy of H except for the vertices i,j . Again for m=O(\sqrt{n}) we will have m^{2} such edge disjoint appearances on a graph of size 2m+km^{2} . Hence the graph constructed is \Omega(1/k) -far from being H -free, in addition to being 2 -degenerate. Now, the distribution is exactly as before by permuting independently the vertices in each L_{r} for r\in[t] . In order to reduce to the previous simple case, one can consider a augmented oracle which returns the whole component C_{\ell} for any query made to a node in the component. By the same reasoning as above, making o(n^{1/4}) queries will find a corresponding matching pair of H_{1},H_{2} with o(1) probability. Finally, for general S=\{v_{1},\ldots v_{r}\} in the labeled H , we use the construction in Definition 9 as follows: We again take two sets A,C of vertices where |A|=|C|=m=\Theta(\sqrt{n}) , with the intention that for each (i,j)\in[m]^{2} we will form an edge disjoint H -copy in the fixed graph. Now, every pair (i,j)\in[m]^{2} will take the role of v_{1},v_{2}\in V(H) , while W=\{v_{3},\ldots,v_{r}\} are fixed and are the same for all copies. Thus again, to find a copy one would need to find two (or more components of H\setminus S ) that with the known v_{3},\ldots,v_{r} but unknown i,j form an H copy. Note that the resulting graph is \Omega(1/k) -far from H and k -degenerate. See Figure 1 for such a construction for an example of 3-size S=\{a,b,c\} . The rest of the construction is as before: we permute the sets L_{1},....,L_{t} by uniform and independent permutations \boldsymbol{\pi}_{1},\ldots,\boldsymbol{\pi}_{t} , and the analysis is obtained similarly using the augmented oracle as before. ∎ Figure 1: The graph H has a separation set S=\{a,b,c\} . The graph F has m^{2} copies of H , one for every (i,j)\in[m^{2}] . Note that the vertex c is present in each of the above copies. Lemma 3.7 . Assume that for a 2 -connected H , no independent set is a separating set. Then \mathcal{P}_{H} is one-sided error testable for the family of p -degenerate graphs. Proof. Let H be a k vertex graph as in the lemma. Let G=(V,E) be a p -degenerate graph that is \epsilon -far from \mathcal{P}_{H} . By setting h\geq 4p^{2}/\epsilon and using Lemma 3.1 , there is a subgraph G^{\prime} of G which is semi-bipartite with respect to \textrm{Heavy}_{h} and is \epsilon/2 -far from \mathcal{P}_{H} . Since G^{\prime} is semi-bipartite, we can assume that any H appearance in G^{\prime} has at least one vertex of degree at most h . Let U be the union of all such vertices. By definition, if we remove from G^{\prime} every edge incident on a vertex from U , then the total number of edges removed from G^{\prime} is at most h\cdot|U| , and the resulting graph is H -free. Since G^{\prime} is \epsilon/2 -far from \mathcal{P}_{H} , we have h\cdot|U|\geq\epsilon n/2 , and hence |U|\geq\epsilon n/2h . The discussion above implies the following basic test. Choose \boldsymbol{v}\in V(G) uniformly at random and run Bounded-BFS (G,\boldsymbol{v},k,h\log(10\cdot\frac{h^{k+2}}{\epsilon}) . Reject if and only if an H appearance is discovered. Then, with probability at least \frac{\epsilon}{2h} this vertex \boldsymbol{v}\in U (and in particular participates in an H appearance). Since H\setminus S is connected, the BFS can traverse the entire “light” component of H\setminus S , by following only edges between low-degree vertices. Because these vertices have degree at most h , a Bounded-BFS can exhaustively explore their local neighborhoods. The heavy vertices S are then discovered naturally as neighbors of this light component, without the BFS ever needing to explore the neighborhood of heavy vertices 6 6 6 except only to conclude that a vertex is heavy. . By assumption, H\setminus S is connected for every independent set S\subseteq V(H) , running Bounded-BFS (G,\boldsymbol{v},k,h\log(10\cdot\frac{h^{k+2}}{\epsilon})) finds a copy of H with probability at least 9/10 . This basic test has query complexity \tilde{O}(h^{k+1}) , and will find an H -appearance with probability \Omega(\frac{\epsilon}{h}) . Repeating the test O(\frac{h}{\epsilon}) will find an H -appearance with success probability at least 2/3 and query complexity \tilde{O}(\frac{h^{k+2}}{\epsilon}) .∎ 4 Testing \mathcal{H} -freeness for a family \mathcal{H} of forbidden subgraphs As discussed in Section 1 , the only one-sided error testable properties in the random neighbor model are those characterized by \mathcal{H} -freeness for a family of constant-sized forbidden subgraphs \mathcal{H} . While we characterized testability for a single forbidden graph in Section 3 , it is important to note that the testability of each individual H\in\mathcal{H} is a sufficient, but not a necessary condition for the testability of \mathcal{H} -freeness. Consider, for example, the family \mathcal{H}=\{C_{4},\textrm{ST}_{10}\} , where \textrm{ST}_{10} denotes a star with 10 leaves. A graph is \mathcal{H} -free if it does not contain a C_{4} and has a maximum degree of at most 9 . While C_{4} -freeness is not testable on its own (as evidenced by the 2 -degenerate graph construction in Section 3 ), the combined property \mathcal{H} -freeness is testable. If G contains \Omega(\epsilon n) vertices of degree at least 10 , a violation of \textrm{ST}_{10} -freeness is discovered with high probability via uniform vertex sampling. If G does not contain many high-degree vertices, the graph is effectively 9 -bounded degree. In this bounded-degree regime, testing C_{4} -freeness is easy since G contains \Omega(\epsilon n) vertex-disjoint copies of C_{4} . The simple example above does not fully capture the complexity of determining whether \mathcal{H} -freeness is testable when \mathcal{H} contains a graph H_{1} that is individually non-testable. A clear necessary condition for \mathcal{H} -freeness to be testable is that any graph G that is \epsilon -far from H_{1} -freeness, and specifically chosen to be “hard” to test for H_{1} , must instead contain many copies of some other member H\in\mathcal{H} . This requirement forces us to characterize the family of input graphs that are hard to test with respect to a given H_{1} , but contain many copies of H . We approach this by first focusing on the specific “hard” constructions used to prove lower bounds for H_{1} -freeness. While these constructions do not represent all possible hard instances, they impose severe structural restrictions on any other H\in\mathcal{H} that could potentially render the collective property \mathcal{H} -freeness testable. Finally, we demonstrate that for any input graph G that is \epsilon -far from H_{1} -freeness, a tester can either efficiently find a copy of H_{1} , or find a copy of a suitably restricted member H\in\mathcal{H} . The remainder of this section is organized as follows. We first focus our analysis on two-member families \mathcal{H}=\{H_{1},H\} , where H_{1} is a 2 -connected graph for which H_{1} -freeness is non-testable, and H is a graph for which H -freeness is testable. These results can then be generalized to larger families using similar methods. For a fixed non-testable H_{1} , we characterize the structures of H that render the collective property \mathcal{H} -freeness testable. This characterization depends fundamentally on the structure of H_{1} , specifically the size and configuration of its obstacle separating sets S , as defined in Definition 8 . Consequently, for the ensuing discussion, we assume \mathcal{H}=\{H_{1},H\} where H_{1} -freeness is non-testable and H -freeness is testable. We begin by establishing a necessary structural restriction on H required to facilitate the testability of \mathcal{H} . Definition 10 (Cactus with respect to (H_{1},S) ) . Let H_{1} be a 2 -connected graph and S\subset V(H_{1}) an obstacle. Let \mathcal{C} be the components of H_{1}\setminus S . A cactus with respect to (H_{1},S) is a pair (H,\Phi) , where H is a graph and \Phi:V(H)\to V(H_{1}) is a homomorphism called “role mapping” , such that there exists a subset of vertices L\subseteq V(H) satisfying: 1. Articulation Points: L is a set of articulation points in H (not necessarily maximal), and their roles under \Phi are contained in the obstacle set, i.e., \Phi(L)\subseteq S . For each v\in L , \Phi(v) is referred to as its S -role . 2. Petal Structure: Every L -component of H is isomorphic to a subgraph of some S -component C\in\mathcal{C} of H_{1}\setminus S . These L -components are called petals . See Figure 2 for a 4 -petal cactus with respect to a non-testable H_{1} , with S=\{a,b\} , and Figure 3 for a more complicated cactus with respect to an non-testable H_{1} and S=\{a,b,c\} . We note that the decomposition of a cactus H into petals is not necessarily unique. As seen in Figure 2 , the combination of the petals P_{3},P_{4} can be reversed, so that P_{4} will connect to P_{2} via b , and P_{3} will connect to P_{4} via a . In Figure 3 the graph H has a decomposition into two different cacti, with the same petals, but with different role mapping \Phi . For the discussion and characterization that follows, the petal structure will not be of importance, but rather just the S -role of the L vertices as defined by \Phi . Figure 2: The graph H_{1} has an obstacle set S=\{a,b\} . The graph H is a 4 -petal cactus, where petal P_{1} is connected to petal P_{2} with a vertex taking the role of a , P_{2} is connected to P_{3} with a vertex taking the role of b , P_{3} is connected to P_{4} via a . Figure 3: The graph H_{1} has a separation set S=\{a,b,c\} . The graph H is a 5 -petal cactus, where petal P_{2} is connected to petal P_{1} with a vertex taking the role of a , to P_{3} with a vertex taking the role of b , and to P_{4} with c . Then, P_{4} is connected to P_{5} with a vertex with role a . Note that P_{1}, which is a subgraph of the component C_{1} , could also be considered a subgraph of the component C_{2} . Thus, the structure of H as a cactus is not unique. In particular, H^{\prime} is isomorphic to H , but its articulation points have different S -roles. Lemma 4.1 . Let H_{1} be a 2 -connected graph which is non-testable in the random neighbor model. If \{H_{1},H\} -freeness is testable, then for every obstacle S of H_{1} , there exists a role mapping \Phi such that (H,\Phi) is a cactus with respect to (H_{1},S) . Proof. Suppose that \mathcal{H}=\{H_{1},H\} -freeness is testable, and let S=\{v_{1},\ldots,v_{r}\} be an obstacle with respect to H_{1} . We consider a distribution \mathcal{D} on adversarial graphs \mathbf{G} on n vertices, constructed as in the proof of Lemma 3.6 . Specifically, every \mathbf{G} will have two sets A and C , each of size m=\Theta(\sqrt{n/k}) . These correspond to the roles v_{1} and v_{2} . A set F of constant size r-2 , corresponding to the remaining roles \{v_{3},\dots,v_{r}\} . For each component C_{t} of H_{1}\setminus S , we create a set L_{t} containing m^{2} copies of C_{t} . Using independent random permutations \boldsymbol{\pi}_{t} , each individual copy of a component is attached to a unique pair (i,j)\in A\times C . We have seen in Lemma 3.6 that an H_{1} copy cannot be found with constant probability using O(1) queries. Hence, the only way \mathcal{H} -freeness can be tested with respect to the distribution above, is by finding an H -subgraph. However, since H is testable, if an H -copy in G is separated by the S -role vertices, then each such S -role vertex is an articulation point for the H -copy (as otherwise, by Lemma 3.6 H will not be testable). We conclude that the S -role vertices L , in any H -appearance in G , is a set of articulation points for H , and that any L -component of H is a subgraph of an S -component of H_{1} . Hence H with the correspondence homomorphism defined by the S -role mapping, and the “subgraph mapping” above, forms a cactus with respect to (H_{1},S) . ∎ We note that Lemma 4.1 states a necessary condition which might not be sufficient for the testability of \mathcal{H} . In particular \{H_{1},H\} of Figure 3 is not testable, as shown by the graph G constructed in the lower bound of Lemma 3.6 where b is the fixed unique vertex in all copies. This is since in an H -appearance we must have two distinct vertices taking the role of b in any mapping \Phi , while in G , all copies of H_{1} share the same b . Thus we now need to characterize what cacti are testable. \mathcal{H}=\{H_{1},H\} -freeness could be testable for G for two reasons. It could be that for an input graph G , that is \epsilon -far from being H_{1} -free, G has linearly many edge disjoint copies of H . But, it could also be the case that G might be H -free, and while H_{1} -freeness is not testable in general, for the input graph G , one can find an H_{1} -copy easily. Thus we need, in a sense, to characterize such input graphs. This is done in the following section. 4.1 On G ’s that are testable with respect to a hard to test H_{1} Let G be \epsilon -far from being H_{1} -free. Recall that by using Lemma 3.1 for h\geq 4p^{2}/\epsilon , we may assume that G is semi-bipartite with respect to \textrm{Heavy}_{h} . Additionally, for \delta\leq\epsilon/4kp^{2} , Lemma 3.3 states that there is a collection of at least \Omega(\epsilon n/kp) edge-disjoint H_{1} appearances for which every edge incident to a vertex v\in\textrm{Heavy}_{h} participates in one of the appearances. While this property guarantees high-density of H_{1} -appearances, it does not ensure that a heavy vertex v\in\textrm{Heavy}_{h} plays a consistent role across difference appearances. To facilitate the discovery of H , we will strengthen the above property to ensure role consistency with respect to the obstacle S . Definition 11 (Role-Preserving Property) . Let H_{1} be a graph and S=\{v_{1},\dots,v_{r}\}\subset V(H_{1}) an obstacle. Let \mathcal{K}=\{(K,\phi)\} be a collection of appearances of H_{1} in a graph G , where each K\subseteq G is a subgraph and \phi:V(H_{1})\to V(K) is its corresponding role mapping (isomorphism). The collection \mathcal{K} is role-preserving with respect to S if there exists a global role assignment \rho:\textrm{Heavy}_{h}\to S such that for every appearance (K,\phi)\in\mathcal{K} and every vertex v\in V(K)\cap\textrm{Heavy}_{h} : \phi^{-1}(v)=\rho(v). We say that G is role-preserving with respect to S if there exists a role-preserving collection \mathcal{K} with respect to S . Lemma 4.2 . Let H_{1} be a graph and S=\{v_{1},\ldots,v_{r}\} be an obstacle in H_{1} . Let G=(V,E) be a graph which is \epsilon -far from H_{1} -freeness. Then, there exists a subgraph G^{\prime}\subseteq G and a collection of edge-disjoint H_{1} appearances (see Definition 7 ), \mathcal{K}^{\prime}=\{(K,\phi)\} in G^{\prime} of size |\mathcal{K}^{\prime}|\geq\frac{\epsilon n}{2kp\cdot r^{r}} that satisfy the role preserving property (Definition 11 ). Proof. Fix \delta=\frac{\epsilon}{4kp^{2}} , and consider a collection \mathcal{K}=\{(K,\phi)\} of at least \epsilon/2pk \delta -good edge-disjoint H_{1} -appearances in G as guaranteed by Lemma 3.3 and \phi:V(H_{1})\to V(K) is an isomorphism that assigns the roles to the vertices of K . To isolate a sub-collection where the appearances are roles-preserving, we use a probabilistic argument. We assign to every vertex v\in V(G) a color \boldsymbol{\ell}(v) chosen uniformly at random from the set [r] . An appearance (K,\phi) is distinctly colored if all the vertices in the obstacle S receive different colors. Since |S|=r , the probability that \{\boldsymbol{\ell}(\phi(v_{1})),\ldots,\boldsymbol{\ell}(\phi(v_{r}))\} are all distinct is \frac{r!}{r^{r}} . Let \mathbf{Z} be the number of distinctly colored appearances in \mathcal{K} . Then, \mathop{{\bf E}\/}[\mathbf{Z}]=|\mathcal{K}|\cdot\frac{r!}{r^{r}} . Fix a coloring \ell^{*} achieving this. In each such appearance, there are r! possible bijections between the r colors and the r roles in S . Therefore, there must exist a bijection \pi that is used by at least 1/r! -fraction of these appearances. Let \mathcal{K}^{\prime} be this collection whose size is |\mathcal{K}^{\prime}|\geq\frac{1}{r!}\left(\frac{\epsilon n}{2pk}\cdot\frac{r!}{r^{r}}\right)=\frac{\epsilon n}{2pk\cdot r^{r}} . Thus, for any v\in\textrm{Heavy}_{h} , setting \rho(v)=\pi(\ell^{*}(v)) ensures that \phi^{-1}(v)=\rho(v) for every (K,\phi)\in\mathcal{K}^{\prime} . ∎ We will need to apply an additional pruning step in order to ensure that each high degree vertex participate in many appearances in \mathcal{K} (this way our tester will be able to discover such appearances with sufficient probability). For a vertex v , we define the degree of v in \mathcal{K} as \deg_{\mathcal{K}}(v)=|\{(K,\phi)\in\mathcal{K}:v\in V(K)\}| . Lemma 4.3 . Fix \delta=\epsilon/4kp^{2} , h=4p^{2}/\epsilon and let H_{1} be a graph and S=\{v_{1},\ldots,v_{r}\} be an obstacle in H_{1} . Let G=(V,E) be a graph which is \epsilon -far from H_{1} -freeness. Then, for any 0<\gamma\leq\frac{\delta}{2k^{k}} , there exists a subgraph G^{\prime}\subseteq G and a collection of H_{1} appearances \mathcal{K}=\{(K,\phi)\} in G^{\prime} satisfying the following: 1. |\mathcal{K}|\geq\frac{\epsilon n}{4pk^{k+1}} . 2. \mathcal{K} is role preserving with respect to S . 3. If v\in\textrm{Heavy}_{h}\cap V(K) for some K\in\mathcal{K} , then \deg_{\mathcal{K}}(v)\geq\gamma\deg(v) . We call such a collection \gamma -good role-preserving . The proof of the above is obtained in the exact same manner as Lemma 3.3 . Assuming that every G that is \epsilon -far from being H_{1} -free has the role-preserving property with respect to (some) S , we make the following definition that will provide a sufficient condition under which we can find an H_{1} appearance in G although testing H_{1} -freeness is not testable in general. For this we need the following definition that is stronger than what is directly needed for the purpose above, but that will be needed to the testability of the family \{H_{1},H\} . Definition 12 (Dependency Digraph) . Let \mathcal{K}^{\prime}=\{(K,\phi)\} be a role-preserving collection of H_{1} -appearances with global role mapping \rho:\textrm{Heavy}_{h}\to S . For a fixed \gamma\in(0,1) , the Dependency Digraph D_{\gamma}(\mathcal{K}^{\prime}) is a directed graph on the vertex set S defined as follows: For any ordered pair of roles (s_{i},s_{j})\in S\times S , there exists a directed edge s_{i}\to s_{j} in D_{\gamma}(\mathcal{K}^{\prime}) if there exists a subset U_{i}\subseteq\{v\in\textrm{Heavy}_{h}:\rho(v)=s_{i}\} such that: 1. \sum_{u\in U_{i}}\deg_{\mathcal{K}^{\prime}}(u)\geq\gamma\sum_{\{v\in\textrm{Heavy}_{h}:\rho(v)=s_{i}\}}\deg_{\mathcal{K}^{\prime}}(v) 2. For every u\in U_{i} , there exists a partner v\in\textrm{Heavy}_{h} with \rho(v)=s_{j} such that |\{(K,\phi)\in\mathcal{K}^{\prime}:u\in V(K)\;\text{and }\phi(s_{j})=v\}|\geq\gamma\deg_{\mathcal{K}^{\prime}}(u). Definition 13 (locked edge) . Fix \gamma\in(0,1) and let \mathcal{K}^{\prime}=\{(K,\phi)\} be a role-preserving collection of H_{1} -appearances. We say that an edge s_{i}\to s_{j} in D_{\gamma}(\mathcal{K}) is locked if for every u\in U_{i} , there exists a partner v\in\textrm{Heavy}_{h} with \rho(v)=s_{j} such that |\{(K,\phi)\in\mathcal{K}^{\prime}:u\in V(K)\;\text{and }\phi(s_{j})=v\}|=\deg_{\mathcal{K}^{\prime}}(u). E.g., for a 2 -set S=\{a,b\} , the possible digraphs could be: (1) - the empty graph, (2) the graph that contains only one edge, say a\rightarrow b and (3) the graph that contains two anti-parallel edges. To see the significance of D_{\gamma}(\mathcal{K}^{\prime}) , consider the example of the 2 -size set S , and the graph H_{1} from Figure 2 . If G has just two fixed vertices a,b connected to n/3 components of size 2 , and n/3 additional distinct vertices, G will be 1/3 -free from being H_{1} -free. Further, its associate digraph is the type (3), as in all appearances a,b appear together, all edges of the digraph are locked. This graph is clearly testable for H_{1} , as finding one component C of (H_{1}\setminus\{a,b\}) , will find a,b and then all other components by taking neighbors of a or b and BFS from there. The extreme case is the type (1) digraph: this occurs e.g., in our lower bound graph as constructed in the proof of Lemma 3.6 . Thus in this case, we cannot find an H_{1} in G with high probability. The “in-between” case of type (2) is similar to type (3), and in which it is easy to find an H_{1} -appearance as follows: Finding a component C with a,b will let us find another component C^{\prime} attached to the same pair a,b , by making BFS from, say a if we have the edge a\rightarrow b . This will make sure that we find the same b (although b does not always appear with a ), since a appears mostly with the same b . The following theorem generalizes the observation that if the corresponding digraph is a tournament (possibly with some antiparallel edges), and in which all edges are locked, then a H_{1} -appearance can be easily found. The idea is that while in general, the relation formed by the digraph above may not be transitive. In the case where a\rightarrow b,~b\rightarrow c are two locked edges, it forces the existence of the locked edge a\rightarrow c . Lemma 4.4 . Fix \delta=\frac{\epsilon}{4kp^{2}} and 0<\gamma\leq\frac{\delta}{2k^{k}} . Let H_{1} be a 2 -connected graph with an obstacle S=\{s_{1},\ldots,s_{r}\} . Suppose that G is \epsilon -far from H_{1} -freeness and let \mathcal{K}=\{(K,\phi)\} be a \gamma -good role preserving collection with respect to S as guaranteed by Lemma 4.3 . If the dependency digraph D_{\gamma}(\mathcal{K}) is a tournament (with possibly anti-parallel directed edges) where all edges are locked, then there exists a constant (depending on k,p,\epsilon ) query tester that finds an H_{1} appearance in G with probability at least 2/3 . Proof. Consider the collection \mathcal{K}=\{(K,\phi)\} of edge-disjoint H_{1} -appearances that is good role-preserving with respect to S . By definition, there exists a global role mapping \rho:\textrm{Heavy}_{h}\to S , where each heavy vertex v appearing in \mathcal{K} is assigned a unique, fixed role \rho(v)\in S across all its appearances in the collection. By the assertion of the lemma D_{\gamma}(\mathcal{K}) is a tournament and every pair of roles (s_{i},s_{j}) is locked . Recall that h=\frac{4p^{2}}{\epsilon} and consider the set U of light vertices which participate in an appearance in \mathcal{K} . By the fact that the collection is edge-disjoint, |U|\geq\frac{|\mathcal{K}|}{h}\geq\frac{\epsilon n}{4phk^{k+1}}=\epsilon_{1}n . Therefore, with probability at least \epsilon_{1} a uniformly random vertex \boldsymbol{v}\sim V(G) belongs to U . Since D_{\gamma}(\mathcal{K}) is a tournament, it contains a spanning arborescence 7 7 7 An arborescence is a directed graph where there exists a vertex r (called the root) such that, for any other vertex v , there is exactly one directed path from r to v . rooted at some role s_{i}\in S (specifically, the arborescence is an Hamiltonian path). By transitivity, for any physical vertex x\in V(G) satisfying \phi(s_{i})=x , the entire obstacle \Phi=\{\phi(s_{1}),\dots,\phi(s_{r})\} is uniquely determined. Specifically, for any role s_{j}\in S , the physical vertex v_{j}=\phi(s_{j}) is uniquely fixed by the composition of the mappings f along the unique directed path from s_{i} to s_{j} in the arborescence. In order to show that the canonical tester finds a copy of H_{1} , suppose \boldsymbol{v} belongs to an S -component C of an appearance (K,\phi) . By the 2 -connectivity of H_{1} and the minimality of S , there exists a path of length at most k from \boldsymbol{v} to the specific hub x=\phi(s_{i}) . By \gamma -goodness, at each step, the probability of staying within \mathcal{K} is at least \gamma . Therefore, a Bounded-BFS identifies this root x with probability at least \gamma^{k} . Once x is identified, the physical separator \Phi is fixed for all appearances in \mathcal{K} containing x as role s_{i} . When the tester queries a random neighbor of x , with probability at least \gamma , it hits an appearance (K^{\prime},\phi^{\prime})\in\mathcal{K} where \phi^{\prime}(s_{i})=x . Since the tournament is locked, we have \phi^{\prime}(S)=\Phi . Since H_{1}\setminus S has constant number of components, then by performing O(\gamma^{-k}) queries from x , the tester identifies physical subgraphs isomorphic to all m components. Since all such components share the identical physical separator \Phi , their union in G forms a valid copy of H_{1} . ∎ For cases where the dependency graph D_{\gamma}(\mathcal{K}) is not a locked tournament graph (when |S|>2 ), we apply an additional pruning to the set \mathcal{K} . Lemma 4.5 . Let \mathcal{K}_{0} be a \gamma_{0} -good role-preserving collection of H_{1} appearances as guaranteed by Lemma 4.3 , and let S be the set of roles. For t<|S|^{2} , there exists a sequence of collections \mathcal{K}_{0}\supseteq\mathcal{K}_{1}\supseteq\cdots\supseteq\mathcal{K}_{t} and a sequence of constants \gamma_{0}>\gamma_{1}>\cdots>\gamma_{t}>0 such that for all 0\leq i\gamma_{1}>\ldots>\gamma_{m} , analyzing the dependency graph D_{\gamma}(\mathcal{K}_{j}) at each step j : • Case A (Locked Tournament): If D_{\gamma}(\mathcal{K}_{j}) is a locked tournament, we invoke Lemma 4.4 and find H_{1} . • Case B (Unlocked Tournament): If D_{\gamma}(\mathcal{K}_{j}) is a tournament but there exists an unlocked edge, we prune to \mathcal{K}_{j+1} . By Lemma 4.5 , this strictly increase the number of locked edges. • Case C (Independent Pair): If D_{\gamma}(\mathcal{K}_{j}) is empty (contains no directed edges), we terminate the pruning phase and proceed to Phase 2, defining our terminal collection as \mathcal{K}^{*}=\mathcal{K}_{j} . Since |S|=2 , the maximum number of possible directed edges is 2 . Thus, the pruning process terminates in m\leq 2 steps, ensuring \mathcal{K}^{*} is \gamma^{*} -good for \gamma^{*}\geq\gamma_{2} . Phase 2: Probabilistic Cactus Embedding For a fixed physical vertex u\in V(G) with \rho(u)=a , let \mathcal{K}^{*}_{u}\subseteq\mathcal{K^{*}} be the set of appearances containing u . We define the set of physical partners of u for role b within the collection \mathcal{K^{*}} as: V_{b}(u)=\{v\in V(G):\exists(K,\phi)\in\mathcal{K^{*}}\text{ s.t. }\phi(a)=u,\phi(b)=v\} We partition \mathcal{K}^{*}_{u} by the physical vertex playing role b : \mathcal{K}^{*}_{u}=\bigcup_{v\in V_{b}(u)}\mathcal{K}^{*}_{u,v},\text{ where }\mathcal{K}^{*}_{u,v}=\{(K,\phi)\in\mathcal{K^{*}}:\phi(a)=u\text{ and }\phi(b)=v\}. Since D_{\gamma}(\mathcal{K^{*}}) is empty, for every v\in V_{b}(u) , the size of each partition is bounded: |\mathcal{K}^{*}_{u,v}|<\gamma\deg_{\mathcal{K}^{*}}(u) . The tester identifies an embedding f:V(H)\to V(G) by following the cactus decomposition into petals. In particular, H consists of petals \{P_{1},\dots,P_{t}\} , connected to each other via articulation points in this order. We define the sequence of sub-cacti H^{(1)},\dots,H^{(t)} such that H^{(i)}=\bigcup_{j=1}^{i}P_{j} is the subgraph formed by the first i petals in this fixed topological ordering of the petals of H and let V_{emb}^{(i)}=f(V(H^{(i)})) be the set of physical vertices already embedded. Assume the tester has successfully found a physical embedding f:V(H^{(i)})\to V(G) . To extend this to H^{(i+1)} , let u\in V(H^{(i)}) be the articulation vertex where the next petal P_{i+1} attaches, and let s=\Phi(u)\in S be its role. The tester identifies P_{i+1} by sampling Q=O(1/\gamma^{*}) neighbors of the physical vertex f(u) and using Bounded-BFS for depth r\geq\textrm{diam}(H_{1}) to find an appearance (K,\phi)\in\mathcal{K}^{*}_{f(u)} . Since the collection is \gamma^{*} -good, this sampling succeeds with constant probability. The primary risk is a collision : the event \boldsymbol{\mathcal{E}}_{i+1} that the sampled appearance (K,\phi) contains a physical vertex z already present in V_{emb}^{(i)} . Conditioned on the existing embedding H^{(i)} , the probability of hitting any z\in V_{emb}^{(i)}\setminus\{f(u)\} is: \mathop{{\bf Pr}\/}[\boldsymbol{\mathcal{E}}_{i+1}\mid H^{(i)}]=\frac{|\{(K,\phi)\in\mathcal{K}^{*}_{f(u)}:\phi(b)\in V_{emb}^{(i)}\setminus\{f(u)\}\}|}{|\mathcal{K}^{*}_{f(u)}|}. Since V_{emb}^{(i)} is fixed by the conditioning, we sum over its vertices: \mathop{{\bf Pr}\/}[\boldsymbol{\mathcal{E}}_{i+1}\mid H^{(i)}]=\frac{\sum_{z\in V_{emb}^{(i)}\setminus\{f(u)\}}|\mathcal{K}^{*}_{f(u),z}|}{|\mathcal{K}^{*}_{f(u)}|}<\frac{\sum_{z\in V_{emb}^{(i)}}\gamma\deg_{\mathcal{K}^{*}}(f(u))}{\deg_{\mathcal{K}^{*}}(f(u))}\leq|V(H)|\cdot\gamma. By the chain rule, the probability of completing all t petals without an accidental collision is at least: \prod_{i=1}^{t}\operatorname{{\bf Pr}}[\neg{\boldsymbol{\mathcal{E}}_{i}}\mid H^{(i-1)}]\geq(1-|V(H)|\cdot\gamma)^{t}\geq 1-t\cdot|V(H)|\cdot\gamma. We choose \gamma such that this probability is at least 2/3 , it finds an H -witness. The total query complexity is t\cdot O(1/\gamma^{*}\gamma)=O_{H,H_{1},\epsilon,p}(1) . ∎ Remark 2 . An important point of discussion: We note that for a particular graph H , and fixed S , being a cactus with respect to (H_{1},S) is not unique. In particular, it could be the case that in a different representation of H as a cactus, the roles of the S vertices can be changed as noted before. Thus, to ensure testability of \mathcal{H} , it is enough that for every obstacle S , there is one decomposition of the cactus which is a valid cactus with respect to (H_{1},S) . 4.3 Testable \{H_{1},H\} -freeness - the general case We move to 2 -size forbidden families \mathcal{H} , as above where H_{1} has obstacles larger than 2 . Unlike for 2-size obstacles, there are more complex lower bounds. As a result, there are more restrictions on the cacti types that make \mathcal{H} -freeness testable. The main complication comes from the fact that while we fix H_{1} , a labeled obstacle S and H , a decomposition of H into a cactus with respect to (H_{1},S) is not unique. In particular, see e.g., in Figure 3 , a decomposition of H , with respect to (H_{1},S) , with different S -roles of its articulation points. The difficulty that this non-uniqueness creates is exemplified with the following argument: Consider the lower bound graph G as discussed in the proof of Lemma 3.6 for the case of S of size r=3 and take v_{3}=a . Note that as in Figure 3 the S -label a appears twice in H , while all H_{1} -appearances in G share the same fixed vertex a . Hence no H appears in G with the above S -labels, which might indicate that \{H_{1},H\} -freeness is not testable. However, as seen in Figure 3 , the same H can be decomposed as a cactus where a does not appear twice. Hence the above argument does not prevent \{H_{1},H\} -freeness to be testable. In fact, however, the above \mathcal{H} is not testable due to the fact that b must appear twice (or more) in any (H_{1},S) -cactus, and hence the lower bound graph G^{\prime} from Lemma 3.6 , with v_{3}=b , serves as a lower bound for the family \{H_{1},H\} ). The above discussion implies an additional necessary condition for \{H_{1},H\} -freeness to be testable, as stated in Lemma 4.6 . Lemma 4.6 . Let H be a cactus with respect to a (H_{1},S) , where H_{1} is a non-testable graph with a labeled obstacle S of size r\geq 3 . For the family \mathcal{F}=\{H_{1},H\} to be testable, H must satisfy the following: for every subset S^{\prime}\subset S of size |S^{\prime}|=r-2 , there must exist a cactus representation (H,\Phi) such that for every role s\in S^{\prime} , the preimage satisfies |\Phi^{-1}(s)|\leq 1 . Thus, considering the above example: we have seen two representations where a,c appear uniquely in one of them. We note that in both representations b appears twice and this cannot be avoided - hence, the H above does not facilitate the testability of \{H_{1},H\} . Proof. Assume that for some subset S^{\prime}\subset S with |S^{\prime}|=r-2 , every valid cactus representation (H,\Phi) requires at least one role s\in S^{\prime} to be assigned to two or more distinct vertices in V(H) . We demonstrate non-testability by utilizing the lower bound graph G_{S^{\prime}} from Lemma 3.6 . The construction of G_{S^{\prime}} involves two sets of vertices A and C of size m=\Theta(\sqrt{n}) . For each pair (i,j)\in[m]^{2} , we form an edge-disjoint copy of H_{1} . In this construction, the roles v_{1},v_{2}\in S\setminus S^{\prime} are mapped to the variable pairs (i,j) , while the roles in S^{\prime}=\{v_{3},\ldots,v_{r}\} are fixed and remain identical for every H_{1} -appearance in the graph. This graph G_{S^{\prime}} is \Omega(1/k) -far from being H_{1} -free, yet finding any specific copy requires identifying the unknown (i,j) pair among the known fixed vertices S^{\prime} , which requires at least \Omega(n^{1/4}) queries. Because every H_{1} -appearance in G_{S^{\prime}} shares the exact same physical vertices for all roles in S^{\prime} , any structure formed by these appearances is restricted to using at most one physical vertex for each role s\in S^{\prime} . By our assumption, every valid cactus representation (H,\Phi) of H requires at least one role s\in S^{\prime} to be mapped to at least two distinct vertices ( |\Phi^{-1}(s)|\geq 2 ). Since G_{S^{\prime}} provides only a single physical vertex for each such role, H cannot be embedded into G_{S^{\prime}} using these H_{1} building blocks. Since G_{S^{\prime}} is \Omega(1/k) -far from being \mathcal{F} -free but contains no copies of H , and H_{1} remains hard to detect, the distribution proves that \mathcal{F} -freeness is not testable. ∎ The following lemma establishes that the structural restriction identified in Lemma 4.6 is not only necessary but also sufficient for testability. Lemma 4.7 . Let H_{1} be a non-testable graph with a labeled obstacle S of size r\geq 3 . If for every subset S^{\prime}\subset S of size r-2 , the cactus H admits a representation (H,\Phi) where each role s\in S^{\prime} appears at most once (i.e., |\Phi^{-1}(s)|\leq 1 ), then \{H_{1},H\} -freeness is testable. Proof. We follow the same strategy used in the proof of Theorem 5 . Let G be \epsilon -far from H_{1} -freeness. For a suitable choice of \gamma_{0}=\gamma_{0}(H_{1},H,\epsilon,p) , we utilize the \gamma_{0} -good role-preserving collection \mathcal{K}_{0} provided by Lemma 4.3 . We examine the dependency digraph D_{\gamma}(\mathcal{K}_{0}) . If the the digraph is a tournament (with possible some anti-parallel edges) with all edges locked, we apply Lemma 4.4 to find an H_{1} appearance. If the digraph is not a locked tournament, we use Lemma 4.5 to successively prune the collection and obtain a sequence of collections \mathcal{K}_{0}\supseteq\ldots\supseteq\mathcal{K}_{m} and \{\gamma_{\ell}\}_{\ell=0}^{m} . If at step \ell the digraph D_{\gamma}(\mathcal{K}_{\ell}) is not a tournament, then there exists at least one pair of roles \{a,b\}\subset S such that there is no directed path from a to b and no directed path from b to a in D_{\gamma}(\mathcal{K}_{\ell}) . We define S^{\prime}=S\setminus\{a,b\} . By hypothesis, H admits a representation (H,\Phi) where \Phi:V(H)\to V(H_{1}) is a homomorphism and |\Phi^{-1}(s)|\leq 1 for all s\in S^{\prime} . The tester attempts to construct an embedding f:V(H)\to V(G) inductively. Let \{P_{1},\dots,P_{t}\} be the petal decomposition of H , and let H^{(i)}=\bigcup_{j=1}^{i}P_{j} be the sub-cactus formed by the first i petals. Let V_{emb}^{(i)}=f(V(H^{(i)})) denote the set of physical vertices already fixed in G . To extend the embedding to H^{(i+1)} , let w\in V(H^{(i)}) be the articulation vertex where P_{i+1} attaches, and let a=\Phi(w)\in S . The tester samples Q=O(1/\gamma_{\ell}) neighbors of the physical vertex f(w) to identify an appearance (K,\phi)\in\mathcal{K}_{\ell} . We define \boldsymbol{\mathcal{E}}_{i+1} as the event that the sampled appearance contains a physical vertex z already present in V_{emb}^{(i)}\setminus\{f(w)\} . Conditioned on the existing embedding H^{(i)} , the set V_{emb}^{(i)} is fixed. Since |\Phi^{-1}(s)|\leq 1 for s\in S^{\prime} , any vertex in V(H^{(i)}) mapping to a role in S^{\prime} is unique and cannot force a collision. Thus, a collision only occurs if a vertex z\in V_{emb}^{(i)} plays role b in the new appearance. Because D_{\gamma}(\mathcal{K}_{\ell}) lacks the edge a\to b , the number of appearances where f(w) plays role a and z plays role b is at most \gamma\deg_{\mathcal{K}_{\ell}}(f(w)) . The conditional probability of a collision is: \mathop{{\bf Pr}\/}[\boldsymbol{\mathcal{E}}_{i+1}\mid H^{(i)}]=\frac{\sum_{z\in V_{emb}^{(i)}\setminus\{f(w)\}}|\{(K,\phi)\in\mathcal{K}_{\ell}:\phi(a)=f(w),\phi(b)=z\}|}{|\{(K,\phi)\in\mathcal{K}_{\ell}:\phi(a)=f(w)\}|}. Thus: \mathop{{\bf Pr}\/}[\boldsymbol{\mathcal{E}}_{i+1}\mid H^{(i)}]<\frac{|V(H)|\cdot\gamma\deg_{\mathcal{K}_{\ell}}(f(w))}{\deg_{\mathcal{K}_{\ell}}(f(w))}\leq|V(H)|\cdot\gamma. By the chain rule and a union bound over the t petals, the probability that the entire embedding f:V(H)\to V(G) is completed successfully is at least: \prod_{i=1}^{t}\operatorname{{\bf Pr}}[\neg{\boldsymbol{\mathcal{E}}_{i}}\mid H^{(i-1)}]\geq(1-|V(H)|\cdot\gamma)^{t}\geq 1-t|V(H)|\gamma. For \gamma<\frac{1}{3t|V(H)|} , this probability is at least 2/3 . As each exploration step requires O_{H_{1},\epsilon,p}(1) queries in the Bounded-BFS , the total query complexity is Q_{\text{total}}=O_{H,H_{1},\epsilon,p}(1) , and the proof is complete. ∎ Combining Lemma 4.6 and Lemma 4.7 , we obtain the following characterization. Theorem 6 . Let H_{1} be a non-testable graph and H be a testable graph. The family \{H_{1},H\} -freeness is testable if and only if for every labeled obstacle S of H_{1} , and for every S^{\prime}\subset S with |S^{\prime}|=|S|-2 , H has a cactus representation (H,\Phi) where each role in S^{\prime} appears uniquely or not at all (i.e., |\Phi^{-1}(s)|\leq 1 for all s\in S^{\prime} ). 4.4 Extension to finite family of forbidden graphs The characterization for 2 -size families provided in Theorem 6 can be generalized to any finite family of graphs \mathcal{F}=\{H_{1},\ldots,H_{\ell}\} . This generalization rests on two fundamental observations regarding the interaction between non-testable graphs and the collective structural properties of the family. When a family contains multiple non-testable graphs (e.g., H_{1} and H_{2} ), their respective obstacles do not “interact” in a way that creates new conditions for testability. Non-testability is a “fragile” property: for the family to be testable, the tester only needs to find any member of the family with O(1) queries. Therefore, if a family is non-testable, every non-testable member must remain “hidden” simultaneously. This means the sufficiency conditions we derived must simply be checked against every non-testable graph in the family individually. In a size 2 family \{H_{1},H\} , the single graph H was solely responsible for “breaking” every possible obstacle of H_{1} . In a larger family, this responsibility can be shared. If H_{1} is the non-testable member, and we have a set of testable graphs \{H_{2},\ldots,H_{\ell}\} , the family is testable if every potential obstacle of H_{1} is “covered” by at least one of the other graphs. Specifically, the condition for testability is relaxed as follows: For every labeled obstacle S of H_{1} , and for every subset S^{\prime}\subset S of size |S^{\prime}|=|S|-2 , there must exist some graph H_{j}\in\mathcal{F}\setminus H_{1} that admits a cactus representation (H_{j},\Phi) where each role in S^{\prime} appears at most once. In the inductive proof of Lemma 4.7 , we showed that if H satisfies the singleton condition for S^{\prime} , a tester can find H in any graph G that is \epsilon -far from being \{H_{1},H\} -free. In a large family, if G is \epsilon -far from \mathcal{F} -freeness, it is by definition, \epsilon -far from being H_{j} -free for every j . If a particular obstacle S^{\prime} is present in G , the tester does not need a single graph H to handle every possible S^{\prime} . As long as there is some H_{j} in the family that can “fit” into the structure constrained by S^{\prime} , the tester will find that H_{j} and successfully reject the graph. Formally, we have the following theorem. Theorem 7 . Let \mathcal{F}=\{H_{1},\dots,H_{k}\} be a finite family of graphs. The property of being \mathcal{F} -free is testable if and only if for every non-testable member H_{i}\in\mathcal{F} and every labeled obstacle S of H_{i} , the following condition holds: For every subset S^{\prime}\subset S of size |S|-2 , there exists at least one graph H_{j}\in\mathcal{F}\setminus\{H_{i}\} that admits a cactus representation (H_{j},\Phi) with respect to (H_{i},S) such that for every role s\in S^{\prime} , the preimage satisfies |\Phi^{-1}(s)|\leq 1 . Definition 14 (Cactus Sentinel) . Let \mathcal{F} be a family of graphs. For a non-testable member H_{i}\in\mathcal{F} let S=\{v_{1},\ldots,v_{r}\}\subset V(H_{i}) be an obstacle and S^{\prime}\subset S a set of size r-2 . A graph H_{j}\in\mathcal{F} is a sentinel for (H_{i},S,S^{\prime}) if there exists a role mapping \Phi:V(H_{j})\to V(H_{i}) such that (H_{j},\Phi) is a cactus with respect to (H_{i},S) satisfying the following. For every role s\in S^{\prime} , its preimage in H_{j} satisfies |\Phi^{-1}(s)|\leq 1 . Lemma 4.8 . Let \mathcal{F} be a family such that for some non-testable H_{i}\in\mathcal{F} and some S^{\prime}\subset S of size r-2 , there is no sentinel H_{j}\in\mathcal{F}\setminus H_{i} with respect to (H_{i},S,S^{\prime}) . Then there exists a distribution on p -degenerate graphs that are \epsilon -far from \mathcal{F} -freeness but requires \Omega(n^{1/4}) queries to test. Proof sketch. Let H_{i},S,S^{\prime} be as defined in the lemma statement. We construct a distribution \mathcal{D} of n -vertex graphs G using the construction in Definition 9 , where we identify the set “fixed” vertices W as the set S^{\prime} . Note that the roles \{v_{1},v_{2}\}=S\setminus S^{\prime} are mapped to hub sets A and C of size m=\Theta(\sqrt{n}) . The m^{2} copies of each S -component of H_{i} are attached via independent random permutations \boldsymbol{\pi}_{\ell} . Suppose a tester finds a copy of some H_{j}\in\mathcal{F} with o(n^{1/4}) queries. Note that if H_{j}=H_{i} , then by Lemma 3.6 , finding H_{i} in a graph drawn from \mathcal{D} require \Omega(n^{1/4}) queries. If H_{j}\neq H_{i} , then, by our assumption, H_{j} is not a sentinel for (H_{i},S,S^{\prime}) . This means for any role mapping \Phi:V(H_{j})\to V(H_{i}) , one of the following must be true: • There exists s\in S^{\prime} such that |\Phi^{-1}(s)|\geq 2 . In the construction of graphs from the distribution \mathcal{D} , each role s\in S^{\prime} is represented by a single vertex in W . Thus, H_{j} cannot appear in such graphs, since it requires two distinct physical vertices to play the same fixed role s . • (H_{j},\Phi) is not a cactus with respect to (H_{i},S) . However, since H_{j} is testable, if an H_{j} -copy in G is separated by the S -role vertices, then each such S -role vertex is an articulation point for the H_{j} -copy (as otherwise, by Lemma 3.6 , H_{j} will not be testable). Thus, for every H_{j} -appearance in G , the S -role vertices L\subset V(H_{j}) are articulation points for H_{j} . Additionally, any L -component of H_{j} is a subgraph of an S -component of H_{i} . Hence H_{j} with the correspondence homomorphism \Phi defined by the S -role mapping, and the inherited L -component “subgraph mapping” forms a cactus with respect to (H_{1},S) . This contradicts our assumption. Since G is O_{H_{i}}(1) -far from being \mathcal{F} -free, the lemma follows. ∎ Lemma 4.9 . Let G be \epsilon -far from \mathcal{F} -freeness. For any non-testable H_{i}\in\mathcal{F} , let \mathcal{K} be a \gamma -good role-preserving collection of H_{i} -appearances. If for every obstacle S of H_{i} and S^{\prime}\subset S of size |S|-2 , there exists a sentinel H_{j}\in\mathcal{F} , then a copy of some H\in\mathcal{F} can be discovered using the canonical tester with O_{\mathcal{F},\epsilon,p}(1) queries. Proof sketch. Fix a non-testable H_{i}\in\mathcal{F} and its \gamma_{0} -good role-preserving collection \mathcal{K}_{0} with global role mapping \rho:\textrm{Heavy}_{h}\to S . We use the dependency graph D_{\gamma}(\mathcal{K}_{0}) to analyze the testability. If D_{\gamma}(\mathcal{K}_{0}) is a locked tournament, then H_{i} is discovered in O_{\mathcal{F},\epsilon,p}(1) queries by Lemma 4.4 . If the digraph is not a locked tournament, we apply Lemma 4.5 to prune the collection and obtain a sequence of collections \mathcal{K}_{0}\supseteq\ldots\supseteq\mathcal{K}_{m} and \{\gamma_{\ell}\}_{\ell=0}^{m} . If at step \ell the digraph D_{\gamma}(\mathcal{K}_{\ell}) is not a tournament, then there exists at least one pair of roles \{a,b\}\subset S such that there is no directed path from a to b and no directed path from b to a in D_{\gamma}(\mathcal{K}_{\ell}) . We define S^{\prime}=S\setminus\{a,b\} . By the sentinel hypothesis, there exists a sentinel H_{j}\in\mathcal{F}\setminus\{H_{i}\} admitting a cactus representation (H_{j},\Phi) such that |\Phi^{-1}(s)|\leq 1 for all s\in S^{\prime} . Let H_{j}=\bigcup_{k=1}^{m}P_{k} be the petal decomposition of H_{j} . We construct an embedding f:V(H_{j})\to V(G) inductively: Suppose we have an embedding for H_{j}^{(k)}=\bigcup_{i=1}^{k}P_{i} . To extend f to P_{k+1} , let w be the articulation vertex with \Phi(w)=a . We sample O(1/\gamma_{\ell}) appearances K\in\mathcal{K}_{\ell} such that \phi^{-1}(a)=f(w) . We extend f to f^{\prime} for all v\in V(P_{k+1}) by setting f^{\prime}(v)=\phi^{-1}(\Phi(v)) . A collision occurs if f^{\prime}(v)\in f(V(H_{j}^{(k)})) for some v\in V(P_{k+1}) . Since |\Phi^{-1}(s)|\leq 1 for all s\in S^{\prime} , any vertex v\in V(P_{k+1}) playing a role in S^{\prime} is unique in H_{j} . Since no vertex in V(H_{j}^{(k)}) maps to \Phi(v) , no collision is structurally forced. Thus, a collision can only occur with respect to roles \{a,b\} . By the case assumption, the pair (a,b) does not form a directed edge in the dependency digraph D_{\gamma}(\mathcal{K}) . In a similar manner to the proof of Lemma 4.7 , if the sampled appearance K contains a role a mapped to a physical vertex in the existing embedding, then the tester finds an H_{i} -appearance in G and rejects. Otherwise, if no collision occurs, by the union bound over the number of petals in H_{j} , the process successfully constructs a complete embedding f:V(H_{j})\to V(G) with high probability. As each exploration step requires O_{H_{1},\epsilon,p}(1) queries in the Bounded-BFS , the total query complexity is Q_{\text{total}}=O_{H,H_{1},\epsilon,p}(1) , and the proof is complete. ∎ We conclude with the following theorem which combines Lemma 4.8 and Lemma 4.9 . Theorem 8 (Characterization of \mathcal{F} -freeness Testability) . Let \mathcal{F} be a finite family of p -degenerate graphs. The property of being \mathcal{F} -free is testable in the random neighbor oracle model if and only if for every H_{i}\in\mathcal{F} and every obstacle S\subset V(H_{i}) for which H_{i} is not testable, there exists a sentinel H_{j}\in\mathcal{F} with respect to (H_{i},S,S^{\prime}) for every subset S^{\prime}\subset S of size |S|-2 . Appendix A Bounded-BFS simulation using random-oracle A main building block in our algorithm is a variation of bounded depth BFS. For vertex v\in V the procedure Bounded-BFS simulates a BFS for t iterations using the random neighbor oracle, while being “query efficient”. In particular, for a threshold h=O(1) , as the search progresses, if it reaches a vertex whose degree is at most h , it explores all of its neighbors; otherwise, it probes only h randomly chosen neighbors. (see Figure 4 for a description of Bounded-BFS subroutine) Since the algorithm only has random-neighbour queries, we would like to guarantee that for each light vertex sampled (i.e., with degree at most h ) during iterations 1,\ldots,\ell-1 of Bounded-BFS , all of its neighbours will be sampled as well. Subroutine Bounded-BFS (G,v,t,s,h) . Input: a random oracle access to G=(V,E) , starting vertex v\in V , depth bound t , number of neighbor-queries at each vertex s and the threshold for ’high’-degree h . Output: A subgraph G^{\prime} of G . 1. Let S_{0}=\{v\} . 2. For \ell=1 to t : • Let S_{\ell}=\emptyset and E_{\ell}=\emptyset . • For every u\in S_{\ell-1} do: – Choose \boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{s} neighbours of u uniformly at random and let E_{u}=\{(u,\boldsymbol{w}_{i}):i\in[s]\} . – Set E_{\ell}=E_{\ell}\cup E_{u} and S_{\ell}=S_{\ell}\cup\{\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{s}\} . • S_{\ell}=S_{\ell}\setminus\bigcup_{i=0}^{\ell-1}S_{i} 3. Return: the subgraph of G induced by the edges \bigcup_{\ell=1}^{t}E_{\ell} . Figure 4: Simulation of bounded-depth BFS using random oracle. By setting s=h\log(2h^{t+1}/\delta) and applying a union bound over at most 2h^{t} vertices sampled during the course of the algorithm, we have that with probability at least 1-\delta , every light vertex sampled during iterations 1,\ldots,\ell-1 , all of its neighbours are also sampled. Appendix B Deferred proofs Proof of Lemma 3.4 . Let u,H_{1},H_{2} as in the lemma. Let \mathcal{D} be a distribution over p -degenerate n -vertex graphs that are \epsilon -far from \mathcal{P}_{H_{1}} , such that any one-sided error \epsilon -tester with q queries fails to find a copy of H_{1} with probability at least 2/3 on a graph drawn according to \mathcal{D} . Fix any G\in\mathrm{supp}(\mathcal{D}) and let A be the set of nodes v\in V(G) for which there exists a homomorphism \phi:V(H_{1})\to V(G) such that \phi(u)=v . We construct a new graph G^{\prime}=G\circ H_{2} as follows. For every vertex v\in A we attach a \deg(v) vertex disjoint copies H_{2}^{(v)} of H_{2} by identifying the vertex u\in H_{2} for which \phi(u)=v . Each such copy is vertex disjoint from V(G)\setminus\{v\} and from all other copies H_{2}^{(v^{\prime})} for v\neq v^{\prime}\in A . We let n^{\prime}=|V(G^{\prime})| . We note that \sum_{v\in A}\deg(v)\leq pn . More over, every copy is of constant size k . Hence the total number of copies and hence the size n^{\prime} of the graph G^{\prime} is n^{\prime}=O(n) . Further, we note that since G is p -degenerate, and so is H , then the resulting G^{\prime} is also O(p) -degenerate. Since G is \epsilon -far from \mathcal{P}_{H_{1}} , one has to make at least \epsilon n modifications to make G\in\mathcal{P}_{H_{1}} . This implies that at least \epsilon n modifications are necessary to make G^{\prime}\in\mathcal{P}_{H} (as we need to eliminate any copy of H_{1} in G^{\prime} ). By normalizing, we have that \mbox{dist}(G^{\prime},\mathcal{P}_{H})=\epsilon^{\prime}=\Omega(\epsilon/k) . Let \mathcal{T} be any one-sided error \epsilon/k -tester for \mathcal{P}_{H} on graphs with n^{\prime} nodes making q queries. We simulate \mathcal{T} on an input G^{\prime} , by answering every oracle query as follows. If the query vertex is in V(G) , we answer according to the oracle of G , and if the query corresponds to a vertex in one of the H_{2} copies, we answer according to the description of the specific H_{2} copy (no access to G is required for such query). Note that the simulation uses at most q queries. By construction, if G\in\mathcal{P}_{H_{1}} then G^{\prime}\in\mathcal{P}_{H} , and therefore the simulation accepts G . On the other hand, if \mbox{dist}(G,\mathcal{P}_{H_{1}})\geq\epsilon , then \mbox{dist}(G^{\prime},\mathcal{P}_{H})\geq\epsilon^{\prime} so the simulation will reject G with probability at least 2/3 . This implies a one-sided error \epsilon -tester with q queries for \mathcal{P}_{H_{1}} which is a contradiction. ∎ Proof of Lemma 3.5 . The proof is by induction on the number of 2-blocks \ell in the decomposition \mathcal{B} . The base case is trivial. Suppose that the lemma holds for every connected graph having a 2-block decomposition with at most \ell-1 blocks. Therefore, by Lemma 2.1 , one can represent H using the decomposition (H^{\prime}_{1},H^{\prime}_{2}) where V(H)=V(H^{\prime}_{1})\cup V(H^{\prime}_{2}) , V(H^{\prime}_{1})\cap V(H^{\prime}_{2})=\{v^{*}\} , H_{1}^{\prime} is a 2-block, and H^{\prime}_{2} has a 2-block decomposition with at most \ell-1 2-blocks. By the induction hypothesis \mathcal{P}_{H^{\prime}_{1}} and \mathcal{P}_{H^{\prime}_{2}} have one-sided error canonical testers. Let T_{H^{\prime}_{1}} be a q_{H^{\prime}_{1}} -canonical \epsilon/k -tester for \mathcal{P}_{H^{\prime}_{1}} with success probability amplified to 99/100 . Similarly, define T_{H^{\prime}_{2}} be a q_{H^{\prime}_{2}} -canonical \epsilon/k -tester for \mathcal{P}_{H^{\prime}_{2}} with success probability amplified to 99/100 . We consider the following q_{H} -canonical tester T_{H} where q_{H}=\max(q_{H^{\prime}_{1}}+q_{H^{\prime}_{2}},(kp)^{2}/\epsilon) . Note that if G\in\mathcal{P}_{H} , then T_{H} accepts G with probability 1 . Suppose that G is \epsilon -far from \mathcal{P}_{H} , and by Remark 1 we can assume that G is semi-bipartite with respect to \textrm{Heavy}_{h} where h\geq\frac{4p^{2}}{\epsilon} . Additionally, note that since G is \epsilon -far from \mathcal{P}_{H} , it holds that \mbox{dist}(G,\mathcal{P}_{H^{\prime}_{1}})\geq\epsilon/k and \mbox{dist}(G,\mathcal{P}_{H^{\prime}_{2}})\geq\epsilon/k (as there are at most k 2-blocks in the decomposition \mathcal{B} ). By the distance guarantee, there exists a set \mathcal{H}(G) of \epsilon n/kp H -appearances in G . Suppose that \Omega(\epsilon n/kp) of H^{\prime}\in\mathcal{H} are such that V(H^{\prime})\cap\textrm{Heavy}_{h}=\emptyset . Then, by Lemma 3.2 , T_{H} finds such an appearance with probability at least 2/3 . Next, we consider the case where every H^{\prime}\in\mathcal{H}(G) has at least one vertex in \textrm{Heavy}_{h} . For \delta=\epsilon/4kp^{2} , using Lemma 3.3 , there exists a sub-collection \mathcal{H}^{\prime}(G)\subseteq\mathcal{H}(G) such that every H^{\prime}\in\mathcal{H}^{\prime}(G) is \delta -good and |\mathcal{H}^{\prime}(G)|\geq(\epsilon/kp-2\delta p)n\geq\epsilon n/2pk . For every H^{\prime}\in\mathcal{H}^{\prime}(G) let \phi_{H^{\prime}}:V(H^{\prime})\to V(H) be an isomorphism. We classify the elements in \mathcal{H}^{\prime}(G) with respect to whether \phi^{-1}_{H^{\prime}}(v^{*}) is in \textrm{Light}_{h} . If at least \epsilon n/4kp of H^{\prime}\in\mathcal{H}^{\prime}(G) are as above, then T_{H} sample a vertex u from such H^{\prime}_{2} -appearance with probability at least 99/100 . Conditioned on this event, running Bounded-BFS (as done in the tester T_{H^{\prime}_{2}} ) from u must discover an H^{\prime}_{2} -appearance with probability at least 99/100 (as otherwise we get a contradiction to \mathcal{P}_{H^{\prime}_{2}} being testable). At the point where T_{H} discovers \phi^{-1}_{H^{\prime}}(v^{*}) , in the following iterations the tester will sample all the neighbors of \phi^{-1}_{H^{\prime}}(v^{*}) , and by the choice of q_{H} during the next iterations of the algorithm, it will discover an H^{\prime}_{1} -appearance with probability at least 99/100 (as otherwise we get a contradiction to the testability of \mathcal{P}_{H^{\prime}_{1}} ). Thus, the algorithm finds an H -appearance with probability at least 97/100 . Next, consider the case where \epsilon n/4kp of the members in \mathcal{H}^{\prime}(G) have \phi^{-1}_{H^{\prime}}(v^{*})\in\textrm{Heavy}_{h} . As before, with probability at least 98/100 the tester finds an H^{\prime}_{2} appearance by using Bounded-BFS . Since \phi^{-1}_{H^{\prime}}(v^{*}) is \delta -good, and q_{H}>\max(q_{H^{\prime}_{1}}+q_{H^{\prime}_{2}},(kp)^{2}/\epsilon)>3/\delta with probability at least 9/10 , the next iterations will discover an H^{\prime}_{1} -appearance. Overall, the tester succeeds with probability at least 1-2/100-1/10>2/3 and the lemma follows. ∎