Property testing of a complete multipartite graph

Question

Propose and prove an $\epsilon$-test for the following property in the dense graph model: $G=(V,E)$ is a complete multipartite graph. That is, there exists a partition $V=V_1\cup\ldots\cup V_\ell$ such that $uw\in E$ if and only if there are $i\neq j$ such that $u\in V_i$ and $w\in V_j$.

I have been stuck at trying to solve this question for a few days. I tried to devise an algorithm along the lines GGR98 for bipartiteness testing (such as here), where we sample a sets $U$ and $S$ of size $\mathrm{poly}(1/\epsilon)$ and try to "self-correct" $S$ based on a small number of "partitions" induced by $U$. In particular, I am not sure how to define "violating edges with respect to $U$" for the above mentioned property. Any help?

EDIT: The number $\ell$ is not given to the algorithm as input. In other words, the task is to determine if there exists an $\ell$ such that the graph is complete $\ell$-partite.

Answer 1

The following answer construct a tester for a graph being complete $\ell$-partite for a fixed value of $\ell$.

Consider the following tester:

• Choose $\ell+1$ vertices at random.
• Verify that the edges between them are consistent with a complete $\ell$-partite graph, that is, there is a way to color the vertices using $\ell$ colors such that there is an edge between two vertices iff they have different colors.

We claim that for every $\epsilon>0$ there exists $\delta>0$ such that if the test succeeds with probability at least $1-\delta$, then the graph is $\epsilon$-close to complete $\ell$-partite. To show this, we assume that the test succeeds with probability at least $1-\delta$, and show that the graph is $\epsilon(\delta)$-close to complete $\ell$-partite, where $\epsilon(\delta) \to 0$ as $\delta \to 0$. Moreover, the proof is by induction on $\delta$, the case $\ell = 1$ being trivial.

Let $\gamma$ be the probability that $\ell-1$ randomly chosen points form a clique. If $\gamma \leq \sqrt{\delta}$ then the graph passes the test for being complete $(\ell-2)$-partite with probability at least $1-\sqrt{\delta}-\delta$, and we complete the proof by induction. Assume, therefore, that $\gamma \ge \sqrt{\delta}$.

The expected failure probability of the test given that the first $\ell-1$ points form a clique is at most $\delta/\gamma \leq \sqrt{\delta}$. In particular, we can find a clique $x_1,\ldots,x_{\ell-1}$ such that with probability $1-\sqrt{\delta}$ over the choice of $x_\ell,x_{\ell+1}$, the graph induced by $x_1,\ldots,x_{\ell+1}$ is consistent with a complete $\ell$-partite graph.

Define the color $c(x)$ of a point $x \neq x_1,\ldots,x_{\ell-1}$ as follows. If $x$ is connected to all but $x_i$, then $c(x) = i$. If $x$ is connected to all, then $c(x) = \ell$. Otherwise, $c(x) = \bot$. Then with probability $1-\sqrt{\delta}$, the following holds:

• Either $c(x_\ell) = c(x_{\ell+1}) \neq \bot$ and $(x_\ell,x_{\ell+1})$ is not an edge,
• Or $c(x_\ell) \neq c(x_{\ell+1})$, $c(x_\ell),c(x_{\ell+1}) \neq \bot$, and $(x_\ell,x_{\ell+1})$ is an edge.

This shows that we can partition all but $\sqrt{\delta} n$ of the vertices into $\ell$ sets, such that the induced graph differs from the corresponding complete $\ell$-partite one in an $O(\sqrt{\delta})$-fraction of edges.