Skip to main content
added 14 characters in body
Source Link
Bangye
  • 458
  • 2
  • 5

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. IfA graph $G$ is a union of several disjoint cliques (a.k.a. cluster graph), then 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.

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. If $G$ is a union of several disjoint cliques (a.k.a. cluster graph), then 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.

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.

Source Link
Bangye
  • 458
  • 2
  • 5

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. If $G$ is a union of several disjoint cliques (a.k.a. cluster graph), then 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.