# Algorithm that can divide all graph nodes N into two fully connected sets?

For a given graph G, is there an algorithm that can divide all graph G nodes N into two sets – A and B (N = A U B),
such that all nodes ai in set A are connected to all other nodes aj in A,
and all nodes bi in set B are connected to all other nodes bj in B?

If the answer to the above is yes, is there a polynomial time algorithm?

Example: The following graph can be divided into sets {1, 2, 3} and {4, 5, 6}.

## Edits:

1. There can be nodes in both A and B: e.g., a node n may exist such that n belongs to A and n belongs to B.
2. If the division into two sets, as defined above, is not possible, the algorithm should recognise it and inform us.
• You mean that all verticies in first subgraph connected only with verticies from first subgraph? So there is no edges between $A$ and $B$ ? – openspace Sep 3 '16 at 14:34
• If it so, then you could use deep-first-search and find connected component. – openspace Sep 3 '16 at 14:35
• No to your first question @openspace. As (N = A U B), there can be a node n in both A and B. – boardrider Sep 3 '16 at 14:38
• So there could be an intersection between A and B? – openspace Sep 3 '16 at 14:40
• Yes, @openspace: see edit on the OP. – boardrider Sep 3 '16 at 14:42

Two observations: If you can find $A$ and $B$ so that their union is all of $G$ and they both induce cliques then you can find $A$ and $B$ that are disjoint cover all of $G$ and also induce cliques.}

Now notice that $A$ and $B$ induce cliques if and only if there are no edges between vertices of $A$ and no edges between vertices of $B$ in the complement of $G$.

So your problem is equivalent to determining if $G^c$ is bipartite, and if it is, finding a partition of $G^c$. This can easily be done in $\mathcal O(n^2)$ time.

Here is some c++11 code:

#include <bits/stdc++.h>
using namespace std;

const int MAX=1010; // maximum number of vertices
set <int> A[MAX];// A[i] stores all the neighbours of vertex i
int C[MAX]; // this store in which "part" we save vertex i

void impossible(){// I just use this to print when I realize its impossible
printf("impossible\n");
exit(0);
}

void dfs(int x){
for(int y:A[x]){
if(C[y]==C[x]) impossible();// this means the graph is not bipartite
if(C[y]==0){
if(C[x]==1) C[y]=2;
else C[y]=1;
dfs(y);
}
}
}

int main(){
int n,m; // number of vertices and edges
scanf("%d %d",&n,&m); // we read n and m
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i!=j) A[i].insert(j); // we want to build the complement, so we start adding every edge
}
}
for(int i=0;i<m;i++){// we read the edges in G and erase them from G^c
int u,v;
scanf("%d %d",&u,&v);
A[u].erase(v);
A[v].erase(u);
}
for(int i=0;i<n;i++){
if(C[i]==0){// if i has not been explored yet we dfs from i
C[i]=1;
dfs(i);
}
}
printf("The set A contains:\n");
for(int i=0;i<n;i++){
if(C[i]==1) printf("%d ",i);
}
printf("\nThe set B contains:\n");
for(int i=0;i<n;i++){
if(C[i]==2) printf("%d ",i);
}
printf("\n");
}