1
$\begingroup$

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}.

sample graph

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.
$\endgroup$
  • $\begingroup$ You mean that all verticies in first subgraph connected only with verticies from first subgraph? So there is no edges between $A$ and $B$ ? $\endgroup$ – openspace Sep 3 '16 at 14:34
  • $\begingroup$ If it so, then you could use deep-first-search and find connected component. $\endgroup$ – openspace Sep 3 '16 at 14:35
  • $\begingroup$ No to your first question @openspace. As (N = A U B), there can be a node n in both A and B. $\endgroup$ – boardrider Sep 3 '16 at 14:38
  • $\begingroup$ So there could be an intersection between A and B? $\endgroup$ – openspace Sep 3 '16 at 14:40
  • $\begingroup$ Yes, @openspace: see edit on the OP. $\endgroup$ – boardrider Sep 3 '16 at 14:42
1
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.