Testing Graph Properties with the Container Method

The $\rho$-Clique property is the set of all graphs on $n$ vertices that contain a clique on $\rho n$ vertices. The problem of testing the $\rho$-Clique property can be considered in both the large clique regime, where $\rho$ is a constant, and in the small clique regime, where $\rho:=\rho(n)$ is a function of the number of vertices of the graph. In the small clique regime, it is important to note that the problem is non-trivial only when $\epsilon<\rho^{2}$ is also a function of $n$, since we can always add at most $\binom{\rho n}{2}<\rho^{2}n^{2}$ edges to any graph to form a $\rho n$-clique.

What is the sample complexity $\mathcal{S}_{\rho\textsc{-Clique}}(n,\epsilon)$ for $\epsilon$-testing the $\rho$-Clique property? Goldreich, Goldwasser, and Ron [GGR98] were the first to consider this question and showed that $\mathcal{S}_{\rho\textsc{-Clique}}(n,\epsilon)=\tilde{O}(\rho/\epsilon^{4})$. This result has remarkable qualitative implications in both the large clique and the small clique regimes. In the large clique regime, it shows that $\epsilon$-testing $\rho$-cliques requires only inspection of a constant-sized subgraph when $\epsilon>0$ is an absolute constant. And in the small clique regime, it shows that the sample complexity for $\epsilon$-testing $\rho$-clique property is sublinear in $n$ for all $\rho=\omega(n^{-1/7})$ when $\epsilon=\Omega(\rho^{2})$—i.e., when the tester must distinguish graphs with $\rho n$-cliques from those whose $\rho n$-subgraphs all have constant density bounded away from $1$.

Improved bounds on the sample complexity for testing cliques were obtained by Feige, Langberg, and Schechtman [FLS04]. With a new direct analysis of the canonical tester for testing cliques, they showed that $\mathcal{S}_{\rho\textsc{-Clique}}(n,\epsilon)=\tilde{O}(\rho^{4}/\epsilon^{3})$. And by considering the restricted problem of distinguishing graphs that consist of a single $\rho n$-clique from those that consist of a single $(\rho-\frac{\epsilon}{\rho})n$-clique, they showed that $\mathcal{S}_{\rho\textsc{-Clique}}(n,\epsilon)=\tilde{\Omega}(\rho^{3}/\epsilon^{2})$.

Our first main result is a new upper bound on the sample complexity of testing the $\rho$-Clique property that is nearly optimal, since it matches the lower bound of Feige, Langberg, and Schechtman up to polylogarithmic factors.

The qualitative implications of Theorem 1 are most striking in the small clique regime. In this regime, the result has a more natural representation when we reformulate it using notation from the Densest $k$-Subgraph (D$k$S) problem. (For more details on the D$k$S problem, see [Man17] and the references therein.)

This result implies that for every constant $\delta>0$ and every $k=\omega(\ln^{3}n)$, we can distinguish graphs with a $k$-clique from graphs whose $k$-subgraphs have density at most $1-\delta$ by examining only a sublinear portion of the graph. The previous bounds in [GGR98] and [FLS04] showed that sublinear sample complexity is achievable for constant $\delta$ when $k=\tilde{\omega}(n^{6/7})$ and $k=\tilde{\omega}(n^{1/2})$, respectively.

This result can also be viewed as a generalization of results of Rácz and Schiffer [RS19] and of Huleihel, Mazumdar, and Pal [HMP21] regarding the sample complexity of the Planted $k$-Clique Detection problem. The latter result shows that sampling an induced subgraph on $O(\frac{n}{k\delta}\ln{\frac{n}{k}})$ vertices suffices to distinguish (i) random graphs with edge probability $(1-\delta)$ from (ii) random graphs with edge probability $(1-\delta)$ containing a planted $k$-clique. The former result shows a similar bound for the restricted case of $\delta=1/2.$ When $\delta>0$ is a constant, the bound in Theorem 1’ shows that the same sample complexity (up to logarithmic factors) suffices to solve the more general perfect completeness decision version of the Densest $k$-Subgraph problem as defined in the theorem statement.

Moreover, Theorem 1’ also gives a nearly optimal upper bound on the query complexity of algorithms that solve the Densest $k$-Subgraph problem in the regime where $\delta>0$ is constant. In this setting, the algorithm is free to query any vertex pair (instead of selecting a set $S$ of vertices and querying all the pairs of vertices in $S$ to determine $G[S]$ exactly), and is free to adaptively select which pairs of vertices to query based on the results of its earlier queries. The bound in the theorem implies that there is a bounded-error algorithm that distinguishes graphs with $k$-cliques from those whose subgraphs have at most $(1-\delta)k^{2}$ edges and has query complexity at most $O(\frac{n^{2}}{\delta^{4}k^{2}}\ln^{6}(\frac{n}{\delta^{2}k}))$. However, as shown in [RS19, HMP21], at least $\Omega(\frac{n^{2}}{\delta^{2}k^{2}}\ln^{2}{\frac{n}{k}})$ queries are required to solve the easier $k$-Planted Clique problem, even for adaptive algorithms.

The $k$-Colorable property is the set of all graphs on $n$ vertices that are $k$-colorable. The case where $k=2$ corresponds to bipartiteness. For testing bipartiteness, nearly optimal bounds $\mathcal{S}_{2-\textsc{Colorable}}(n,\epsilon)=\tilde{\Theta}(1/\epsilon)$ [GGR98, AK02] are known. We focus on the case where $k\geq 3$. We again consider two different regimes: the low chromatic number regime where $k$ is a constant, and the polychromatic regime where $k=k(n)$ is a function of $n$. In the polychromatic regime, we note that $\epsilon$-testing the $k$-Colorable property is non-trivial only when $\epsilon<1/k$ (and so also depends on $n$) since we can always eliminate at most $k\binom{n/k}{2}\leq n^{2}/k$ edges from a graph to make it $k$-colorable.

The study of the sample complexity of the $k$-Colorable property has a long history that predates the definition of property testing itself. Rödl and Duke [RD85], building on prior work of Bollobás, Erdős, Simonovits, and Szemerédi [BESS78], showed that $\mathcal{S}_{k\textsc{-Colorable}}(n,\epsilon)$ is a constant independent of $n$ when both $k$ and $\epsilon$ are constant. However, this result relies on the regularity lemma and so the bounds obtained on the sample complexity grow as a tower of height polynomial in $1/\epsilon$. Notably, this means that these results give only very limited results in the polychromatic regime since they give a sublinear bound on the sample complexity of $k(n)$-colorability only for some $k(n)$ that are iterated logarithm functions of $n$.

Goldreich, Goldwasser, and Ron [GGR98] obtained much better bounds for $k$-Colorable. They showed that $\mathcal{S}_{k\textsc{-Colorable}}(n,\epsilon)=\tilde{O}(k^{2}/\epsilon^{3})$ for all $k\geq 3$. This result provides a significant improvement in the testability of colorability in the polychromatic regime: it shows that $k$-colorability is testable with a sublinear sample complexity when $\epsilon=\delta/k$ for a constant $\delta>0$ whenever $k=o(n^{1/5})$.

Alon and Krivelevich [AK02] further improved the bounds for testing $k$-colorability. They showed that $\mathcal{S}_{k\textsc{-Colorable}}(n,\epsilon)=\tilde{O}(k/\epsilon^{2})$ for all $k\geq 3$. This result shows that $k$-colorability can be testable with a sublinear sample complexity for all $k=o(n^{1/3})$. Sohler [Soh12] obtained another improvement in the low chromatic number regime, showing that $\mathcal{S}_{k\textsc{-Colorable}}(n,\epsilon)=\tilde{O}(k^{6}/\epsilon)$ and, in particular, when $k$ is constant then the sample complexity for testing $k$-colorability is $\tilde{\Theta}(1/\epsilon)$. But in the polychromatic setting, the bound of Alon and Krivelevich remains stronger whenever $k=\omega(1)$ and $\epsilon=\omega(1/k^{5})$.

Our next main result unifies and improves on both of the incomparable results of Alon and Krivelevich [AK02] and Sohler [Soh12].

Theorem 2 implies that sublinear sample complexity suffices to distinguish $k$-colorable graphs from graphs whose $k$-colorings all create at least $\delta/k$ monochromatic edges for all values of $k=o(\sqrt{n})$ when $\delta>0$ is constant.

We do not know whether the bound in Theorem 2 is optimal. The best lower bound for testing $k$-colorability in the polychromatic regime is $\tilde{\Omega}(1/\epsilon)$ [AK02]. Since $\epsilon$-testing $k$-colorability is non-trivial only when $\epsilon<1/k$, this means that there is a quadratic gap between our new upper bound and this lower bound for testing $k$-colorability for large values of $k$.

Theorems 1 and 2 are both established by analyzing the natural tester that checks whether the sampled induced subgraph $G[S]$ has the property that we are testing or not. In the case of large cliques, this tester accepts with probability at least 1/2,³³3See the Remark at the end of Section 3.3 for a discussion related to this choice of acceptance probability. and in the case of $k$-colorability, the tester always accepts when the graph has the property. The challenge in the analysis, as is usually the case in property testing, is in showing that the tester rejects all graphs that are far from having the property with sufficiently large probability. We address this challenge with the use of the graph container method.

We first note that the graph container method is stated in terms of independent sets. In the case of testing $\rho$-cliques, our application of the graph container method applies more naturally to testing $\rho$-independent sets, which is equivalent by considering the complement of a graph.

Very briefly, the graph container method builds upon the observation that though a graph may contain a large number of independent sets, for every graph $G$ we can find a much smaller collection of sets of vertices that we call containers such that (i) every independent set is a subset of at least one of the containers, (ii) the containers are small, and (iii) for each container $C$, the induced subgraph $G[C]$ is sparse. The graph container method was originally introduced by Kleitman and Winston [KW82] to bound the number of square-free graphs. The method has since been used to great effect, notably by Sapozhenko (see [Sap05] and the references therein), and was later extended to the hypergraph container method [BMS15, ST15] that has seen even more wide use throughout combinatorics. The container method has also been recently applied to algorithmic settings for the problem of approximately counting independent sets in bipartite graphs [JPP23] and the problem of obtaining faster exact algorithms for almost-regular graphs [Zam23].

Our use of the graph container method builds on Kleitman and Winston’s original approach to it. The key component of the method as they introduced it is a simple greedy algorithm for identifying a small set of vertices of an independent set that form its fingerprint. The fingerprint of an independent set $I$ in turn uniquely defines the container that contains $I$. Our main technical lemmas provide tight bounds on the size of the containers as a function of the size of the corresponding fingerprints. We describe the algorithm and present the technical lemmas in Section 2.

The tight bounds on the size of containers can then be used to analyze the soundness of testers for $\rho$-independent sets in the following way. Let $S$ be the set of $s$ vertices sampled by the tester. Any independent set $S$ has a (very small) fingerprint that defines a container with bounded size; we can use this bounded size to show that the probability that more than $\rho s$ vertices (including the fingerprint vertices) in $S$ are drawn from that container is extremely small. So small, in fact, that we can apply a union bound over all potential fingerprints in $S$ to bound the overall probability that the sample includes a large independent set. For all the details of the proof, see Section 3.

For testing $k$-colorability, the overall approach is the same, but a different argument is required to show that for any $k$ independent sets in the sample, we can identify $k$ fingerprints whose corresponding containers have a small union. See Section 4 for the details.

Theorems 1 and 2 suggest a number of intriguing open problems. We discuss three of them briefly.

By construction, the sequence of fingerprints and containers of an independent set satisfy a number of useful properties. For instance, we have

so that for each $t=1,2,\ldots,|I|$, $F_{t}\subseteq I\subseteq C_{t}$.

The construction of the algorithm also guarantees that the $t$-th container of an independent set is the same as the $t$-th container of its $t$-th fingerprint.

Another basic property of the containers of any independent set is that we can bound their maximum degree in the following way.

In order to use containers in our proofs, we need stronger structural results about containers when the graph is $\epsilon$-far from the properties of interest.

In the case of testing the $\rho$-Clique property, we first change our focus so that we instead look at graphs that are $\epsilon$-far from having the $\rho$-IndepSet property. We show that for each such graph $G$, every independent set in $G$ is a subset of a container of size strictly less than $\rho n$. In fact, our result shows more: there is a container for $I$ of size $(\rho-\alpha)n$ where $\alpha$ is at least as large as $\epsilon/\rho$ times the length of the corresponding fingerprint (up to log factors).

Graph container lemmas like the one above are often used to bound the size of a collection of containers that cover all independent sets. Indeed, Lemma 5 also immediately yields such a bound, showing that for every graph $G$ that is $\epsilon$-far from the $\rho$-IndepSet property, there is a collection of $n^{\tilde{O}(\rho^{2}/\epsilon)}$ containers such that every independent set of $G$ is a subset of at least one container. However, for our intended application in the proof of Theorem 1, the size of the collection of containers is not relevant; what we need is the bound on the size of the containers in (2) and, in particular, the trade-off in that bound between the size of the container and its fingerprint.

For testing the $k$-Colorable property, we need a different type of Graph Container lemma which bounds the size of the union of $k$ containers for different independent sets in a graph.

Once again, the upper bound on the size of the union of containers is what we need for the proof of Theorem 2, and this result is possible only because the bound in (3) decreases linearly with the size of the corresponding fingerprints.

We present the proof of Lemma 5 in Section 3 and the proof of Lemma 6 in Section 4.

The main tool in the proof of the Graph Container Lemma for testing independent sets, Lemma 5, is a shrinking lemma that, informally speaking, says that many vertices are excluded in each round of Algorithm 1 whenever the containers contain a large subset $C$ for which the induced subgraph $G[C]$ is sparse.

We are now ready to complete the proof of the Graph Container Lemma for testing independent sets, restated below.

See 5

We are now ready to use Lemma 5 to complete the proof of Theorem 1. The proof of the theorem also makes use of the following form of Chernoff’s bound for hypergeometric distributions.

We are now ready to prove Theorem 1, restated below in its precise form (with the polylogarithmic term) and for the $\rho$-IndepSet property.

In this section we prove the main lemma that balances the trade off between the size of the union and the sum of the fingerprints sizes of a set of containers, restated from Section 2.2.

See 6

We can now complete the proof of Theorem 2, restated below.