Tolerant Testers for Subgraph-Freeness

Since $S$ is an independent set in $G^H$, it follows that any pair ${\mathscr{H}}_1,{\mathscr{H}}_{\mathcal{2}}\in S$ is a pair of edge-disjoint copies of $H$ in $G$ (by definition). Since $S$ is maximal, it follows that if we remove for each $\mathscr{H}\in S$ all its edges from $G$ then $G$ becomes $H$-free (since we remove at least one edge from each copy of $H$ in $G$). $\mathrm{⊲}$

By Claim 12, for any maximal IS in $G^H$, $S$, it holds that $\frac{dis{t}_H(G)}{|E(H)|}\le |S|\le dis{t}_H(G)$. Therefore, for any such $S$ it holds that $\mathrm{Pr}[v\in S]\in [\frac{dis{t}_H(G)}{|E(H)|n_H},\frac{dis{t}_H(G)}{n_H}]$, where $v$ is drawn u.a.r. from $V(G_H)$. This is true since $|V(G_H)|=n_H$. Since $MI{S}_{\pi }(G^H)$ is maximal for any $\pi$ (by definition), the claim follows. Equation 2 follows from the fact that each vertex $v$ in the independent set covers at most $d(v)+1$ vertices from the graph. Thus, any maximal independent set is of size at least $n_H(G)/(\mathrm{\Delta }(G^H)+1)$, in particular, $MI{S}_{\pi }(G^H)$ (for any $\pi$). This concludes the proof. $\mathrm{⊲}$

By using the previous claims we arrive to the following claim.

Let $E_1$ denote the event that in all the executions of Step 2a of the algorithm, a copy of $H$ was returned. By definition 10, the setting of $\delta$ and since $s\ge n_H(G)$, w.h.c.p., $E_1$ occurs. We henceforth assume $E_1$ occurs. Consider the random variable $Z_i$ (see Step 2c of the algorithm). By construction $Z_i$ takes values in $\{0,1\}$. By Claim 13, Equation 1, $𝔼(Z_i)\in [\frac{dis{t}_H(G)}{|E(H)|n_H(G)},\frac{dis{t}_H(G)}{n_H(G)}]$. By Equation 2, $𝔼(Z_i)\ge 1/(\mathrm{\Delta }(G^H)+1)$. The claim follows from the setting of $\mathrm{\ell }$ and the multiplicative Chernoff’s bound (see Theorem 30). $\mathrm{⊲}$

We next prove our main theorem for this section. In order to realize this theorem we provide in the next sections concrete $H$-copies oracles and $H$-copies number estimators (first for $H$ which is a $k$-clique and then generalize, for $H$ which is $2$-connected and has radius $1$).

Assume $G$ is $ϵ$-close to being $H$-free. If the algorithm accepts $G$ in Step 3 then we are done. Otherwise, it follows that $\widehat{n}\ge ϵm$.

Let $E_1$ denote the event that the estimator in Step 2 returns a good approximation as described in Definition 8. Conditioned on $E_1$ and the fact that $\widehat{n}\ge ϵm$ it is implied that $n_H(G_{\theta })\ge ϵm/2$ (assume otherwise and reach a contradiction to the fact that $\widehat{n}\ge ϵm$ as ) and hence its return value is in $(1\pm \gamma )n_H(G_{\theta })$.

Let $E_2$ denote the event that Approximate-Average-MIS-In-Auxiliary-Graph returns a good approximation as described in Claim 14. Conditioned on $E_1\cap E_2$ we obtain that

Since $dis{t}_H(G_{\theta })\le dis{t}_H(G)\le ϵm$ we obtain that $\widehat{n}\widehat{Z}\le {(1+\gamma )}^2ϵm$ and hence the algorithm accepts $G$.

Assume $G$ is $\beta$-far from being $H$-free where $\beta =ϵ|E(H)|(1+\eta )$. By the setting of $\theta$ it follows that $dis{t}_H(G_{\theta })\ge (1-\gamma )\beta m$. Thus, $n_H(G_{\theta })\ge (1-\gamma )\beta m$. Therefore, conditioned on $E_1\cap E_3$ we obtain that $\widehat{n}\in (1\pm \gamma )n_H(G_{\theta })$. In particular, it holds that $n_H(G_{\theta })\ge ϵm/2$. Hence conditioned on $E_1\cap E_2\cap E_3$ we obtain that Equation 4 holds in this case as well. In particular $\widehat{n}\widehat{Z}\ge {(1-\gamma )}^3\frac{\beta m}{|E(H)|}>ϵm{(1+\gamma )}^2$ (since $(1+\eta )>{(1+2\gamma )}^5>{(1+\gamma )}^2/{(1-\gamma )}^3)$. Thus, conditioned on $E_1\cap E_2\cap E_3$, the algorithm rejects $G$, as desired. $◀$

By construction, linearity of expectation and Theorem 11. $\mathrm{⊲}$

Consider a copy, $𝒦$, of $K_k$ in $G_{\theta }$. Let $y(𝒦)$ denote the number of $\theta$-light vertices in $𝒦$. The probability that $𝒦$ is found in Step 2f of Approximate-$K_k$-copies-in-$G_{\theta }$ is exactly $y(𝒦)\cdot 1/(n\left(\genfrac{}{}{0pt}{}{\theta }{k-1}\right))$. Conditioned on the event that indeed $𝒦$ was found in Step 2f of iteration $j$ the probability that $Y_j$ is set to be $1$ is $1/y(𝒦)$. Thus, for every $j$, $\mathrm{Pr}(Y_j=1)=n_{K_k}(G_{\mathrm{\Theta }})/(n\left(\genfrac{}{}{0pt}{}{\theta }{k-1}\right))$. The claim follows. $\mathrm{⊲}$

For $s\le n_{K_k}(G_{\theta })$ the claim follows from Claim 16, the setting of $t$ and multiplicative Chernoff’s bound (see Theorem 30). To see the correctness of the second part, consider $s=n_{K_k}(G_{\theta })$. By the first part of the claim, w.h.c.p. the return value of the algorithm is in $(1\pm \gamma )n_{K_k}(G_{\theta })=(1\pm \gamma )s$. Namely, at most $(1+\gamma )s$. Now consider the case in which $s>n_{K_k}$. By a coupling argument, w.h.c.p. the return value is at most $(1+\gamma )s$ in this case. To see this, couple the return value of the algorithm to the return value of the algorithm on the graph after we add $s-n_{K_k}$ copies to the graph (arbitrarily). Since we added copies, the return value of the algorithm on the modified graph dominates the return value on the original graph (to see this consider executing the algorithm in parallel in both graphs - the outcome in the modified graph is always at least as high) but is guaranteed to be at most $(1+\gamma )s$ w.h.c.p. by the above. The claim about the query complexity follows from construction. This concludes the proof. $\mathrm{⊲}$

For any copy of $K_k$, $𝒦$, in each iteration of the while-loop, the probability that we return $𝒦$ in Step 1f of the algorithm is exactly $1/(n\left(\genfrac{}{}{0pt}{}{\theta }{k-1}\right))$. Therefore if the number of copies is greater than $s$ then the probability that it will return a copy during in a single iteration is at least $s/(n\left(\genfrac{}{}{0pt}{}{\theta }{k-1}\right))$. The claim follows by the setting of the number of iterations. $\mathrm{⊲}$

The claim follows from construction. $\mathrm{⊲}$

The theorem follows from the fact that $\mathrm{\Delta }({(G_{\theta })}^H)\le \left(\genfrac{}{}{0pt}{}{k}{2}\right){\theta }^{k-2}$, Theorem 15 and claims 16-20. $◀$

Let $v$ be a vertex in $\mathscr{H}$ which is incident to all other vertices in $\mathscr{H}$ (such vertex exists since $H$ has radius $1$). If $v$ is $\theta$-light then Item 1 holds. Otherwise, $v$ is $\theta$-heavy. Since there are no edges in $G_{\theta }$ such that both endpoints are $\theta$-heavy, the claim follows. $◀$ We say that a BFS is a $\theta$-restricted if it explores only the neighbors of the $\theta$-light vertices it reaches. We say that an exploration reveals a copy $\mathscr{H}$ if all the vertices of $\mathscr{H}$ appeared in the exploration.

If item 1 of observation 22 holds, then clearly the claim follows. Otherwise, there is exactly one $\theta$-heavy vertex, $u$, in $\mathscr{H}$. Since $H$ is $2$-connected, after we remove $u$ from $\mathscr{H}$, $\mathscr{H}$ remains connected and its diameter is at most $|V(H)|-1$. Thus, a $\theta$-restricted BFS of depth $|V(H)|-1$ from any $\theta$-light vertex of $\mathscr{H}$ reveals all the $\theta$-light vertices of $\mathscr{H}$. The claim follows from the fact that at least one of the $\theta$-light vertices in $\mathscr{H}$ is a neighbor of $u$. $\mathrm{⊲}$ Therefore, by Claim 23, finding for a $\theta$-light vertex, $v$, all the $H$-copies in $G_{\theta }$ that include $v$, can be done by using $O({\theta }^{|V(H)|})$ queries. Consequently, a query for all-neighbors in ${(G_{\theta })}^H$ can be answered by making $O(|V(H)|{\theta }^{|V(H)|})$ queries to $G$. This can be achieved by going over all vertices of the queried copy, $\mathscr{H}$, and for each $\theta$-light vertex, finding all its copies. From the union of these sets we then remove all the copies that do not share an edge with $\mathscr{H}$ and obtain all the neighbors of $\mathscr{H}$ in ${(G_{\theta })}^H$.

To support random copy queries we assign each copy of $H$ to its $\theta$-light vertex of lowest id. To sample a $H$-copy u.a.r. from $G_{\theta }$ we first pick a vertex $v\in V$ u.a.r., if it is $\theta$-light then we find all its $H$-copies as described above. We then pick a copy that is assigned to $v$ u.a.r. and return it w.p. $a_{H,\theta }(v)/a_{H,\theta }^{max}$ where $a_{H,\theta }(v)$ denotes the number of copies that are assigned to $v$ in $G_{\theta }$ and $a_{H,\theta }^{max}$ denotes the maximum number of copies that include a specific $\theta$-light vertex (recall that the copies in $G_{\theta }$ are assigned only to $\theta$-light vertices). Clearly, the above algorithm samples each copy of $H$ in $G_{\theta }$ w.p. $1/(n\cdot a_{H,\theta }^{max})$. Consequently, the probability that it returns a copy is $n_H(G_{\theta })/(n\cdot a_{H,\theta }^{max})$. Thus, the success probability of the algorithm depends on $a_{H,\theta }^{max})$. A straightforward upper-bound on $a_{H,\theta }^{max}$ is $|V(H)|!\left(\genfrac{}{}{0pt}{}{{\theta }^{|V(H)|}}{|V(H)|}\right)$ where the first term is due to all possible labeling of the vertices and the second term is due to all possible ways to pick the vertices of the copy from the set of vertices we explored. In the next claim we provide a tighter bound on $a_{H,\theta }^{max}$.

Fix an arbitrary labeling of $H$. Let $v\in V$. We next bound $a_{H,\theta }(v)$. Label the $H$-copies that $v$ belongs to according to the fixed labeling of $H$ (each copy has its own labeling). If there is more than one such labeling per copy (due to automorphism), pick one arbitrarily. We next describe a one-to-one mapping from the set of labeled copies to a set of sequences of integers. We then bound the cardinality of the latter set and obtain a bound on the number of $H$-copies that $v$ belongs to and hence a bound on $a_{H,\theta }^{max}$. Fix a labeled copy of $v$, $\mathscr{H}$, and consider the BFS exploration of $\mathscr{H}$ starting at $v$, where vertices with smaller label are explored first. Given the label of $v$ and the sequence of the vertices in $\mathscr{H}$ by their BFS order we can reconstruct the labels of all the vertices in the copy. The set of vertices and their labels are mapped to a single copy. Moreover, by the above, we can identify the copy by the identity of the root, its label and a sequence of $|V(H)-1|$ indexes in $[\theta ]$. Each index indicates the index of the respective element in its parent adjacency-list. The indexes are listed according to the BFS exploration. Since the identity of the root is known, we can inductively reconstruct the tree by the sequence of indexes. Note that the parents are always $\theta$-light (while the leaves may be $\theta$-heavy) therefore it suffices to use indexes in $[\theta ]$. From the above we see that for a specific label of $v$ there are at most ${\theta }^{|V(H)|-1}$ copies of $H$ to which $v$ belongs. Since there are $|V(H)|$ possible labels, we get the desired bound. $\mathrm{⊲}$

The claim about the query complexity follows by construction. Consider the random variable $Y_j$ which is defined in Approximate-$H$-copies-in-$G_{\theta }$ . Since $𝔼(Y_j)\ge n_H(G_{\theta })/n$ and $Y_j\le a_{H,\theta }^{max}$, for $s\le n_H(G_{\theta })$, by the setting of $t$ and the multiplicative Chernoff’s bound (Theorem 30), w.h.c.p the output of the algorithm is in $(1\pm \gamma )n_H(G)$, as required. For $s>n_H(G_{\theta })$, by a coupling argument, w.h.c.p. the output of the algorithm is at most $(1+\gamma )$ (see more details in the proof of Claim 14). $\mathrm{⊲}$

The claim about the query complexity follows by construction. In each iteration of the algorithm, each copy of $H$ is returned with probability $1/(n\cdot a_{H,\theta }^{max})$. Thus, in each iteration a copy is returned w.p. $n_H(G_{\theta })/(n\cdot a_{H,\theta }^{max})$. Thus, if $s\le n_H(G)$, a copy is returned w.p. at least $1-\delta$ by the setting of the number of iterations. $\mathrm{⊲}$

By Construction. $\mathrm{⊲}$

The theorem follows from the fact that $\mathrm{\Delta }({(G_{\theta })}^H)\le h\cdot a_{H,\theta }^{max}$, Theorem 15 and claims 24–27. $◀$

By the proof of Theorem 21. $◀$