reduction of independence problem and cluster problem

Question

independent problem is: there is a simple and undirected graph, we are looking for the maximum vertex in which there is no edge between any two of them.
cluster problem is: there is a simple and undirected graph, we are looking for the maximum number of the vertex in which there are proximity every two vertexes ( there is an edge between any two vertexes)
how can I reduct independent problem to cluster problem and vise versa?

nir shahar · Answer

If i understand your question correctly, given $G$, build a graph $G'$ where $V(G)=V(G')$ and for every $v,uin V(G)$, $(v,u)in E(G')iff(v,u)notin E(G)$

reduction of independence problem and cluster problem

One Answer

Add your own answers!

Ask a Question