1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Try using the following: if $(x,y),(x,z) \notin E$ then $(y,z) \notin E$. $\endgroup$ Commented May 18, 2021 at 13:18
  • $\begingroup$ I can't see why this is sufficient. Suppose we delete a single edge from a complete bipartite graph, then this violating vertex pair will not be detected by this criterion, right? $\endgroup$
    – user136729
    Commented May 18, 2021 at 14:25
  • $\begingroup$ Every tester which doesn’t sample a linear fraction of edges will miss such a small change. Same goes for other properties, such as bipartiteness. Are you suggesting that bipartite isn’t testable? Perhaps you should take a closer look at the definition of an $\epsilon$-tester. $\endgroup$ Commented May 18, 2021 at 14:30
  • $\begingroup$ I see now. It was easier for me to solve the problem of the graph being a union of cliques, as it was more similar to the GGR98 construction, in conjunction with the criterion you suggested. Thank you! $\endgroup$
    – user136729
    Commented May 18, 2021 at 17:16
  • $\begingroup$ A graph is complete multipartite iff its complement is a disjoint union of cliques. $\endgroup$ Commented May 18, 2021 at 17:44

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer! I meant for $\ell$ to be some unknown number, which is not given as input to the algorithm. I will edit the question to reflect this. $\endgroup$
    – user136729
    Commented May 18, 2021 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.