4
$\begingroup$

Design an $\epsilon$-test for the following property in the dense graph model: $G(V,E)$ is a union of three disjoint cliques.

I've been sitting for a few hours and I don't have any idea of how to solve this one ... anyone has any ideas / leads?

I have tried to pick the vertices randomly and then conclude from the graph they make $G'$ what it says about $G$. I've divided into cases by connectivity: if the connectivity is $4$ or more it is easy to conclude that the Graph do not has the property. I have struggled with the math in the other cases.

$\endgroup$
3
  • $\begingroup$ The first thing to try is to randomly choose a few vertices and verify that the graph that they induce is a disjoint union of three cliques. $\endgroup$ Commented Sep 15, 2015 at 15:46
  • 2
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$
    – D.W.
    Commented Sep 15, 2015 at 15:52
  • 1
    $\begingroup$ Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it would be helpful if you edited the question to write your thoughts and what you could not figure out. It will definitely draw more answers to your post. We do not want to just do your exercise for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here. $\endgroup$
    – D.W.
    Commented Sep 15, 2015 at 15:53

2 Answers 2

2
$\begingroup$

I will explain how to solve a similar question:

Design an $\epsilon$-test for the following property in the dense graph model: $G(V,E)$ is a union of two disjoint cliques.

I assume that a clique is also considered a union of two disjoint cliques (one of them empty).

The natural test to try is

Sample three vertices $x,y,z$, and check that the graph $G[x,y,z]$ induced by $x,y,z$ is either a triangle or an edge.

If a graph is a union of two disjoint cliques, then this test always passes. Conversely, suppose that this test always passes. Fix some vertex $x$, and let $V_1$ be the set of vertices connected to $x$, $V_2$ be the set of vertices not connected to $x$. If $y,z \in V_1$ then $G[x,y,z]$ includes the edges $(x,y),(x,z)$, and so must be a triangle, that is, $(y,z) \in E$. If $y,z \in V_2$ then $G[x,y,z]$ doesn't contain the edges $(x,y),(x,z)$, and so must be the edge $(y,z) \in E$. Finally, if $y \in V_1$ and $z \in V_2$ then $G[x,y,z]$ contains $(x,y)$ but not $(x,z)$. It must be an edge, so that $(y,z) \notin E$. We conclude that $G$ is indeed a union of two disjoint cliques.

Now suppose that the test passes with probability $1-\epsilon$. In particular, there must be a vertex $x_0$ such that conditioned on $x = x_0$, the test passes with probability at least $1-\epsilon$ (why?). Define $V_1,V_2$ as before. The argument above shows that $H$, the union of the cliques on $V_1$ and on $V_2$, is $\epsilon$-close to $G$ (in fact, slightly closer). Indeed, for every pair of vertices $y,z \neq x_0$, the test passes on $x_0,y,z$ if and only if the edge $(y,z)$ exists on both or neither $G$ and $H$. Thus $G$ and $H$ agree on all edges involving $x$, and agree on a $1-\epsilon$ fraction of the rest of the edges.


What about the actual question? Again, the natural test to try is

Sample four vertices $x,y,z,w$, and check that the graph $G[x,y,z,w]$ induced by $x,y,z,w$ is a union of three disjoint cliques.

This time the analysis is slightly more complicated. Suppose that the test passes with probability $1 - \epsilon$. We consider two cases.

Case 1. $G$ contains at least a $1-\sqrt{\epsilon}$ fraction of all possible edges.

In this case, $G$ is $\sqrt{\epsilon}$-close to a clique.

Case 2. $G$ contains at most a $1-\sqrt{\epsilon}$ fraction of all possible edges.

In this case, we can find two unconnected vertices $x_0,y_0$ such that conditioned on $x=x_0,y=y_0$, the test passes with probability at least $1-\sqrt{\epsilon}$. We can now define $V_1,V_2,V_3$ analogously to how we defined $V_1,V_2$ in the preceding case, and show that $G$ is $\sqrt{\epsilon}$-close to the union of the cliques on $V_1,V_2,V_3$. Details left to the reader.

$\endgroup$
1
$\begingroup$

I give a hint but not a complete solution. For property testing, it may help to consider what are the forbidden patterns. Then you may have an algorithm with one-side error. A graph $G$ is a union of several disjoint cliques (a.k.a. cluster graph) if and only if there is no induced $P_3$ (a path of three vertices), i.e., any three vertices induce a triangle or one edge. Of course, for your problem, a graph without induced $P_3$ is a cluster graph but not necessary consists of exactly three disjoint cliques. So, if you only randomly check $P_3$, it will be two-sides error. You can think about four vertices. A three-disjoint-cliques graph must also be a cluster graph, and furthermore any four vertices do not induce an independent set.

$\endgroup$

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.