[Math] Algorithm that can divide all graph nodes N into two fully connected sets

Question

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 a_i in set A are connected to all other nodes a_j in A,
and all nodes b_i in set B are connected to all other nodes b_j 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.

Answer 1

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");
}