Results on $H$-Freeness Testing in Graphs of Bounded $r$-Admissibility

A graph property is a class of graphs closed under isomorphisms. A property-tester for a property $P$ is a probabilistic algorithm that receives as input the size of a graph $G$, a distance parameter $ϵ>0$ (among potentially other parameters), and oracle access to the graph $G$. The algorithm accepts with probability at least $2/3$ any input from $P$ and rejects with probability at least $2/3$ an input that it is $ϵ$-far from the property $P$. The term “$ϵ$-far” is a notion of distance that depends on the exact problem setting and discuss it further below. The complexity measure of a property-tester is a function that bounds above the total number of queries to the oracle the algorithm uses, as a function of the input parameters $ϵ$, size of the graph and any other input parameters provided. A property is testable if it has a property-tester whose query complexity is independent of the size of the input graph.

We study here the property of $H$-freeness, where $H$ is a fixed known graph, i.e. the property of graphs that do not have a subgraph isomorphic to $H$, which is one of the fundamental graph properties that has been studied in the property testing framework. $H$-freeness was studied in the dense, sparse and general graph models. In the dense model it was shown implicitly in [1] that $H$-freeness is testable, for a more explicit result see [2]. Goldreich and Ron [8], showed that $H$-freeness is testable in the bounded degree graph model. In an effort to move towards larger sparse¹¹1Here sparse should be understood as having a linear number of edges or equivalently bounded average degree graph classes, Czumaj et al. [4] showed that $H$-freeness is testable in sparse graphs when $H$ is a tree. This result is most likely tight for sparse graphs as Alon et al. [3] showed that triangle-freeness is not testable in sparse graphs.

While this settles the question for the most general notion of sparse graphs, the question is still open for a plethora of sparse graph subclasses which are more structured. Possibly the most famous among them is the class of planar graphs. Czumaj et al. [5] showed that $H$-freeness is testable for this class. Proceeding in this line of research, and moving to a much larger class of sparse graphs, Levi [10] showed that triangle-freeness is testable in graphs of bounded arboricity, which is a superset of the family of planar graphs. In Eden et al. [7] it is shown that, for every $r\ge 4$, $C_r$-freeness is not testable in graphs of bounded arboricity. Specifically, it is shown that, in graphs of bounded arboricity, the query complexity of $C_4$-freeness and $C_5$-freeness is $\tilde{\mathrm{\Theta }}(n^{1/4})$, the query complexity of $C_6$-freeness is $\tilde{O}(n^{1/2})$, and for every $k\ge 6$, the query complexity of $C_6$-freeness is $O(n^{1-1/\lfloor k/2\rfloor })$ and $\mathrm{\Omega }(n^{1/3})$. These results also leave open the question of which sparse classes – somewhere between bounded arboricity and planar graphs – and which values of $r$ is $C_r$-freeness testable.

In order to identify a suitable notion of sparseness, we draw inspiration from the field of structural sparse graph theory and propose the $r$-admissibility measure of graphs as a parameter that governs the testability of $H$-freeness. $2$-admissibility was originally defined in [9], where it was simply referred to as admissibility. The more general notion of $r$-admissibility²²2If you are interested in a more formal definition in this stage, we suggest that you proceed to Section 3, and read up to Proposition 3 before you proceed here. for natural values of $r$ was first defined in [6]. Strictly speaking, $r$-admissibility is a family of measures where $r$ governs how “deep” into the graph we look. We remark that, graph classes with bounded $1$-admissibility are equivalent to graphs with bounded arboricity (both measures lie within a constant factor of each other). Many well-known sparse classes, like planar graphs, graphs of bounded genus, graphs excluding a fixed (topological) minor and graphs of bounded degree have bounded $r$-admissibility [12, 14, 6] meaning that the $r$-admissibility of any member of such a class can be bounded by a function which only depends on $r$ and the class itself.

We show that $C_4$-freeness is testable in graphs with bounded $2$-admissibility, and that $H$-freeness, for every $H$ of diameter $2$, is also testable in graphs with bounded $2$-admissibility and in particular $C_5$-freeness is testable in graphs with bounded $2$-admissibility. Using our techniques it is possible to show that $C_6$ and $C_7$ are testable in graphs with bounded $3$-admissibility. This result will appear in the journal version of this paper that will also contain a lower bound which shows that, for every $r\ge 4$, $C_r$-freeness is not testable in graphs of bounded $(\lfloor r/2\rfloor -1)$-admissibility. This implies that for every $r>0$, there exists a graph $H$ of diameter $r+1$ such that $H$-freeness is not testable on graphs with bounded $r$-admissibility. The above leads us to conjecture that, for every $r\in 𝒩$ and $t\le 2r+1$, $C_t$-freeness is testable in graphs with bounded $r$-admissibility and furthermore for every $r>2$, $H$-freeness, for $H$ of diameter $r$, is testable in graphs with bounded $r$-admissibility.

We use $𝒩$ for the set of integer numbers, $ℛ$ for the set of real numbers, ${ℛ}^{+}$ for the set of positive real numbers. For an integer $k$, we use $[k]$ as a shorthand for the set $\{1,2,\mathrm{\dots },k\}$. In this paper, all graphs are simple. For a graph $G$ we use $V(G)$ and $E(G)$ to refer to its vertex- and edge-set, respectively. For a vertex $u\in V(G)$ we use the notation $N_G(u)$ to denote the set of all of $u$’s neighbours in $G$. We omit the subscript, when clear for context. The diameter of a graph is the maximum of the distance between $u$ and $v$ over all pairs of vertices $u$ and $v$ in $V(G)$.

We use the notation ${\mathrm{Heavy}}_{\alpha }(G)$, where $\alpha \in 𝒩$ to denote the set of vertices in $V(G)$ that have degree larger than $\alpha$. We write ${\mathrm{Heavy}}_{\alpha }$ when $G$ is clear from context. In some places we will use the notation without initially stating the value of $\alpha$, in those cases $\alpha$ is calculated further down when its concrete value is required.

For sequences of vertices $x_1,x_2,\mathrm{\dots },x_{\mathrm{\ell }}$, in particular paths, we use notations like $x_{1}P{x}_{\mathrm{\ell }}$, $x_1$ or $x_{1}P$ or $P{x}_{\mathrm{\ell }}$ to indicate subpaths $P$ that are part of the larger path. For example, the notation $uPv$ for a path $u,a,b,c,v$ would mean that $P$ is the subpath $a,b,c$, whereas $uP$ in the same context would mean that $P$ is the subpaths $a,b,c,v$. All the paths in this paper are simple. Though paths here are undirected, we often treat them as directed by specifying a start and end vertex.

An ordered graph is a pair $𝔾=(G,\le )$ where $G$ is a graph and $\le$ is a total order relation on $V(G)$. We write ${\le }_{𝔾}$ to denote the ordering of $𝔾$ and extend this notation to derive relations , ${>}_{𝔾}$, ${\ge }_{𝔾}$. For simplicity we will call $𝔾$ an ordering of $G$ and we write $\pi (G)$ for the set of all possible orderings of $G$.

We use the same notations for graphs and ordered graphs, additionally we write for the before neighbourhood and $N_{𝔾}^{+}(u)≔\{v\in N(u)\mid v{>}_{𝔾}u\}$ for the after neighbourhood of a vertex $u\in 𝔾$. We omit the graphs in the subscripts if clear from the context. We further use ${\mathrm{deg}}_{𝔾}^{-}(u)≔|N_{𝔾}^{-}(u)|$ and ${\mathrm{deg}}_{𝔾}^{+}(u)≔|N_{𝔾}^{+}(u)|$, as well as ${\mathrm{\Delta }}^{-}(𝔾)≔{\max }_{u\in 𝔾}{\mathrm{deg}}_{𝔾}^{-}(u)$ and ${\mathrm{\Delta }}^{+}(𝔾)≔{\max }_{u\in 𝔾}{\mathrm{deg}}_{𝔾}^{+}(u)$. We omit subscripts if clear from the context.

In particular, for every vertex $v$ in a $\gamma$-degenerate graph $G$ and every degeneracy ordering $𝔾$ of the graph it holds that ${\mathrm{deg}}_{𝔾}^{-}(v)\le \gamma$. Consequently, the number of edges in a $\gamma$-degenerate graph is bounded by $\gamma n$. A degeneracy ordering of a graph can be computed in time $O(n+m)$ and $O(\gamma n)$ for $\gamma$-degenerate graphs [11].

In this section we present Algorithm 1 which is used for all upper bounds presented. Algorithm 1 receives as an input a graph $H$, a set of parameters including the parameter $p$ and oracle access to a graph $G$. We note that for each upper bound shown in this paper, the parameters provided to Algorithm 1, in addition to $p$, are dependent on the graph $H$.

Algorithm 1 can be seen as a variation of the “standard” BFS (breadth first search) based testers for properties of bounded degree graphs. In such testers, initially a small subset of the graph’s vertices is randomly selected and then a fixed depth BFS is performed (using oracle queries) from every vertex in the selected set.

Algorithm 1 differs from the “standard” testers, at the BFS stage: In the “standard” tester the search is expanded to all neighbours of a discovered vertex (until the fixed depth is reached). In contrast, Algorithm 1 only queries a subset of neighbours, specifically for a vertex $v$ it randomly selects a size at most $\min \{\mathrm{deg}(v),\lceil \alpha \rceil \}$ subset $X\subseteq [{\mathrm{deg}}_G(v)]$ and then it queries the identity of every $i$th neighbour for $i\in X$. We call this type of search pseudo-BFS and refer to it with the acronym PBFS.^††margin: PBFS

In this section we fix some $ϵ>0$, an integer $p>0$, $\alpha =32p^2/ϵ$. The input graph $G$ is $(p,2)$-admissible and we let $𝔾$ be an ordering of $G$ with ${\mathrm{adm}}_2(𝔾)=p$.

In this section we fix $ϵ>0$, $p\in 𝒩$, $\alpha =3|V(H)|\lceil {ϵ}^{-1}{2}^{2|V(H)|+4p^2\log p}\rceil$. As before, $G$ is an arbitrary $(p,2)$-admissible graph and $𝔾$ is an ordering of $G$ with ${\mathrm{adm}}_2(𝔾)=p$. Finally, $H$ is an arbitrary diameter $2$ graph.

The trimming process in this section depends on the structure of $H$ and requires an extra construct ($𝐇$). Let us first provide some intuition why this is required.

Suppose that $\tilde{H}$ is an $H$-subgraph of $\tilde{G}$ and $h$ is the largest vertex in $V(\tilde{H})\setminus {\mathrm{Heavy}}_{\alpha }(G)$. We show below that the number of vertices like $h$ in $\tilde{G}$ is large enough to ensure that with high enough probability one of them will be in the set $S_0$ selected by Algorithm 1.

Ideally, in $\tilde{H}$, every vertex $u\in V(\tilde{H})$, is reachable from $h$ via vertices not from ${\mathrm{Heavy}}_{\alpha }(G)$. This is an ideal case, because of the following. The depth of the PBFSs used is $|V(H)|$. Thus, as the PBFS queries all the neighbours of vertices $V(\tilde{H})\setminus {\mathrm{Heavy}}_{\alpha }(G)$, all these vertices will be discovered and also all edges incident to them. This means that the algorithm discovers all the edges of $\tilde{H}$ except those that are incident on two vertices from $V(\tilde{H})\cap {\mathrm{Heavy}}_{\alpha }(G)$. The trimming we use ensures that there are no edges between heavy vertices, so in particular, this latter case cannot occur and Algorithm 1 will discover $\tilde{H}$.

If we do not find ourselves in the ideal case, $\tilde{H}$ has a separator $\tilde{K}$ that consists only of vertices from ${\mathrm{Heavy}}_{\alpha }(G)$. By similar reasoning to the ideal case, if $h$ is included in the set $S_0$ that Algorithm 1 selects, it discovers all the vertices in $\tilde{H}$ that can be reached from $h$ via vertices in $V(\tilde{H})\setminus {\mathrm{Heavy}}_{\alpha }(G)$, this includes all the vertices of $\tilde{K}$. Let us denote the subgraph found so far by ${\tilde{H}}_1$. The algorithm now still needs to find the remaining vertices of $\tilde{H}$ that are “behind” the separator, let us call denote this subgraph by ${\tilde{H}}_2$.

The problem here is that the vertices $\tilde{K}$ of on the boundary between ${\tilde{H}}_1$ and ${\tilde{H}}_2$ have a high degree, therefore the probability to discover ${\tilde{H}}_2$ may be arbitrarily small. We therefore design a trimming process that will ensure that there are many “useful” ${\tilde{H}}_2$-subgraphs ${\tilde{H}}_2^{\prime }$ isomorphic to ${\tilde{H}}_2$ in $\tilde{G}$ that can serves to complete ${\tilde{H}}_1$ into a graph isomorphic to $H$. Specifically, a subgraph ${\tilde{H}}_2^{\prime }$ is useful if $\tilde{K}\subset V({\tilde{H}}_2^{\prime })$ and there exists an isomorphism from ${\tilde{H}}_2^{\prime }$ to ${\tilde{H}}_2$ which maps every vertex of $\tilde{K}$ to itself.

Let $Q^{\prime }$ be a maximum family of vertex disjoint useful ${\tilde{H}}_2$-subgraphs with respect to the fixed graph ${\tilde{H}}_1$. If $Q^{\prime }$ is small then we can remove them all simply by removing all edges between members of $Q^{\prime }$ and $\tilde{K}$. If this is not possible, $Q^{\prime }$ must be sufficiently large and the PBFS can discover one of its members with sufficiently high probability.

The above is a simplification, since $\tilde{H}$ might disconnect into more than two components when removing the separator $\tilde{K}$. In this case we also need to ensure that the members of $Q^{\prime }$ are sufficiently disjoint.

Finally, in the preceding discussion we fixed a single $\tilde{H}$ with separator $\tilde{K}$, however $\tilde{H}$ is of course not known in advance. We therefore enumerate all possible sets $K\subset H$ that can take the role of $\tilde{K}$ (not that, by Proposition 3, we only need to look at sets of size ). Since $K$ consists only of heavy vertices and our trimming removes edges between heavy vertices, we can further assume $K$ to be independent.

We say a set of graphs is a set of sibling graphs by $L$, if every pair of graphs in the set are siblings by $L$.