Tolerant Testers for Subgraph-Freeness

Abstract

In this paper we study the problem of tolerantly testing the property of being $H$-free (which also implies distance approximation from being $H$-free). In the general-graphs model, we show that tolerant $K_k$-freeness testing can be achieved with query complexity that is polynomial in the arboricity of the input graph $G$, $arb(G)$, and independent of the size of $G$ (for graphs in which the average degree is $\Omega (1))$. Specifically for triangles, our algorithm distinguishes graphs which are $\epsilon$-close to being triangle-free from graphs that are $3\epsilon (1+\eta )$-far from being triangle-free with expected query complexity which is $\tilde{O}(ar{b}^3(G))$ (for constant $\eta$ and $\epsilon$). For general $k$-cliques our algorithm distinguishes graphs which are $\epsilon$-close to being $K_k$-free from graphs which are $\left(\genfrac{}{}{0ex}{}{k}{2}\right)\epsilon (1+\eta )$-far from being $K_k$-free with expected query complexity which is polynomial in $k$, $1/\epsilon$, $1/\eta$ and $arb(G)$. We then generalize our result and provide a similar result for any motif $H$ which is $2$-connected and has radius $1$. This includes for example the wheel graph. Finally, we show that our tester can be applied to the bounded-degree model for tolerantly testing $H$-freeness for any motif $H$. The query complexity of the algorithm is polynomial in the degree bound, $d$, improving the previous state-of-the-art by Marko and Ron (TALG 2009) that obtained quasi-polynomial query complexity in $d$.