Testing Triangle Freeness in the General Model in Graphs with Arboricity $O(\sqrt{n})$

We provide an upper bound whose running time complexity is $\tilde{O}(\Gamma/\bar{d}+\Gamma)\cdot{\rm poly}(1/\epsilon)$ on expectation. Therefore, for $m\leq n$ our upper bound is $\tilde{O}(\Gamma/\bar{d})$ and when $m>n$ our upper bound is $\tilde{O}(\Gamma)$ (ignoring polynomial dependencies in $1/\epsilon$).

We provide three lower bounds, each suitable for a different range of parameters.

1. 1.

   For any $\Gamma$ and any feasible $m\geq 1$, we provide a lower bound of $\Omega((\Gamma n)/m)=\Omega(\Gamma/\bar{d})$ queries. Therefore our upper bound is tight when $m\leq n$ (up to polynomial dependencies in $1/\epsilon$ and $O(\log\log n)$ factors).

2. 2.

   For any $\Gamma$ and any feasible $m\geq\Gamma^{3}$ we provide a lower bound of $\Omega(\Gamma)$ queries. Therefore, our upper bound is also essentially tight as long as $m\geq\Gamma^{3}$ (notice that since $m\leq n\cdot\Gamma$, it is implied that this lower bound applies only for graphs in which $\Gamma=O(n^{1/3})$). Since we may assume that $m\geq n$ (otherwise we already have essentially tight lower bound), one implication of this lower bound is that our upper bound is tight in the strong sense for graphs with arboricity $O(n^{1/3})$ (namely it is tight for any feasible $m$) as it is always the case that $m\geq\Gamma^{3}$ for $\Gamma=O(n^{1/3})$.

3. 3.

   For any $\Gamma\leq(n/2)^{1/2}$ and any feasible $n\leq m\leq\Gamma^{3}$ we provide a lower bound of $\Omega(m^{1/3})$ queries. Since it is always the case that $m\geq\Gamma^{2}$, a lower bound of $\Omega(\Gamma^{2/3})$ queries is also implied.

To summarize, for graphs of arboricity $\Gamma=O(n^{1/2})$ we obtain that our upper bound is tight for a large range of average degrees. Additionally, for the range of average degrees in which we do not provide tight bounds, our upper bound is essentially $O(\Gamma)$ while our lower bound is $\Omega(\Gamma^{2/3})$ in the worst case.

As mentioned before, Alon et al. [3] provide tight bounds only in two cases. The first case is when $d_{\rm max}=O(\bar{d})$ and $\bar{d}\leq\sqrt{n}$, where $d_{\rm max}$ denotes the maximum degree and $\bar{d}$ denotes the average degree of the graph. In this case, it follows that $\Gamma=\Theta(d_{\rm max})=\Theta(\bar{d})$ an so our upper bounds essentially match. Additionally we note that a bound on the arboricty of the graph does not imply a bound on the maximum degree of the graph. In fact, the maximum degree could be $\Theta(n)$ while the arboricity is $\Theta(1)$ (as it is the case in the star graph). Consequently, the tightness of our upper bound is not restricted for graphs which have bounded maximum degree.

The second case is when $\bar{d}=\Theta(1)$, for these graphs the running time complexity of their algorithm is $\tilde{\Theta}(n^{1/2})$. For this case, the running time complexity of our upper bound is $\tilde{O}(\Gamma)$. We note that in graphs in which $\bar{d}=\Theta(1)$, $\Gamma$ could range between $\Theta(1)$ and $\Theta(n^{1/2})$. Therefore when $\bar{d}=\Theta(1)$ the complexity of our upper bound is not worse than the complexity of the upper bound in [3] but could be much better, depending on $\Gamma$.

For average degree in the range between $\Omega(1)$ and $O(n^{2/5})$ and in the range between $\Omega(n^{1/2})$ and $O(n^{2/3})$ the upper bound of $O(m^{1/2})$ queries of Alon et al. achieves the best running time, in terms of $n$ and $m$. For these ranges, the running time of our algorithm is $\tilde{O}(\Gamma)$. Since $m^{1/2}\geq\Gamma$, we obtain that for this ranges as well the performances of our algorithm are at least as good (up to $O(\log\log n)$ and ${\rm poly}(1/\epsilon)$ factors) but could be significantly better.

For average degree in the range between $\Omega(n^{2/5})$ and $O(n^{1/2})$ the upper bound of $O(\max\{(n\bar{d})^{4/9},n^{2/3}/\bar{d}^{1/3}\})$ queries of Rast [13] achieves the best running time. In this range our upper bound is always better than the upper bound of [13] for graphs of arboricity $O(n^{12/21})$.

It is well known that a graph which is $\epsilon$-far from being triangle free has $\Omega(\epsilon m)$ edge-disjoint triangles (see Claim 1). Therefore if we were able to sample edges uniformly from the graph then after sampling $O(1/\epsilon)$ edges we would sample an edge $\{u,v\}$ which belongs to a triangle. Thus, if we revealed the entire neighborhood of $u$ and the entire neighborhood of $v$ then we would find a triangle in the graph. Our algorithm is based on this simple approach. There are only two problems that need to be addressed. The first problem is that sampling edges uniformly in a graph in which the degrees have high variability is too costly. The second problem, which also stems from the variability of the degrees in the graph, is that revealing the entire neighborhood of a vertex can be too costly, depending on its degree.

This is where the arboricity of the graph comes into play. For a graph of arboricity $\Gamma$, as was shown in [4], the fraction of edges in the subgraph induced on heavy vertices, that is, vertices with degree greater than $c\Gamma/\epsilon$ where $c$ is some absolute constant, is at most $\epsilon/2$. Therefore, if $\Gamma$ was given to us as a parameter then we could, in some sense, ignore the subgraph induced on vertices of degree greater than $\Theta(\Gamma/\epsilon)$ since a graph which is $\epsilon$-far from being triangle free still have $\Omega(\epsilon m)$ violating edges (and $\Omega(\epsilon m)$ edge-disjoint triangles) even after we remove this subgraph entirely. Ignoring this subgraph allows us on one hand to sample edges almost uniformly from the resulting graph while making only $\Omega(\Gamma/\bar{d})$ queries, and also guarantees that there are $\Omega(\epsilon m)$ violating edges for which both endpoints are not heavy. This solves the two problems we had with taking the simple approach.

However a bound on the arboricty of the graph is not given to the algorithm as a parameter. Since approximating the arboricity of a graph up to a constant factor is not possible in sublinear time (to see this consider a graph with a hidden clique), we estimate a different parameter which we informally refer to as the effective arboricity of the graph. We show that this parameter suffices for our needs. In fact, this parameter could be much smaller than $\Gamma$, in which case the complexity of our algorithm is better than $O(\Gamma/\bar{d}+\Gamma)$. We reduce the problem of approximating the effective arboricity of the graph to the problem of estimating the number of edges in the graph in which we remove the subgraph induced on heavy vertices, where heavy vertices are defined with respect to increasing thresholds. We stop increasing our threshold once the estimation of the number of edges is sufficiently large. As we prove, with high constant probability, our approximation to the effective arboricity is bounded by $O(\Gamma)$ which leads to a tester with running time $O(\Gamma/\bar{d}+\Gamma)$, as claimed.

Our first lower bound of $\Omega(\Gamma/\bar{d})$ for graphs in which $\bar{d}\leq 1$ is based on a simple hitting argument. Specifically, construct a graph which is $1/3$-far from being triangle free in which $\Omega(\Gamma/\bar{d}+\Gamma)=\Omega(\Gamma/\bar{d})$ queries are required in order to sample a vertex which is not isolated with probability that is at least $1/3$.

Our other two lower bounds are simple adaptations of the lower bound of $\Omega(\min\{\bar{d},n/\bar{d}\})$ queries presented in Alon et al. [3].

As described above, for an input graph $G$, the number of edges in the subgraph induced on the heavy vertices w.r.t. the threshold $4\Gamma(G)/\epsilon$ is at most $(\epsilon/2)|E(G)|$ (see Claim 4). Therefore, when testing triangle freeness, we may, roughly speaking, ignore this subgraph with the hope of obtaining better complexity. Since $\Gamma(G)$ is not given to the algorithm as a parameter, we compute, in Algorithm 1, a different parameter of the graph, denoted by $\Gamma^{*}$, which is, roughly speaking, an approximation of the effective arboricity of the graph. In order to specify the guarantees on $\Gamma^{*}$ we shall need a couple of definitions.

When $G$ is clear from the context we may simply use $H_{t}$ and $L_{t}$. Using the definition of $H_{t}(G)$, we next define the graph $H(G,t)$ which is defined w.r.t. $G$ and a threshold $t$.

The guarantees on $\Gamma^{*}$, which is the return value of Algorithm 1 (that will be described next), are as described in the following claim.

Algorithm 1 proceeds in iterations where in each iteration it multiplies $\Gamma^{*}$ by a factor of $2$, where initially $\Gamma^{*}$ is set to $1$. It stops when the estimated number of edges in $E(H(G,t))$, for $t$ which is $\Theta(\Gamma^{*}/\epsilon)$, is at least $|E(G)|(1-\Theta(\epsilon))$. In order to estimate the number of edges in $E(H(G,t))$, Algorithm 1 calls Algorithm 2.

In turn, Algorithm 2 uses the directed graph $D(G,t)$, which we defined momentarily, that is constructed from $G$ and can be accessed by making a constant number of queries to $G$.

The following claim specifies the guarantees of Algorithm 2.

We are now ready to prove Claim 5.

Given a threshold $t$, Algorithm 3 samples an edge from $H(G,t)$ almost uniformly as described in the next claim.

Using Algorithms 2 and 3 we are now ready to describe our tester (Algorithm 4).

Since the tester has one-sided error (it rejects only if it finds a witness for violation, i.e., a triangle) its correctness follows from the following claim.

We adapt the following lower bound of Alon et al. [3].