Two Clique Problem (Check if Graph can be divided in two Cliques) - GeeksforGeeks

Two Clique Problem (Check if Graph can be divided in two Cliques) - GeeksforGeeks
A Clique is a subgraph of graph such that all vertcies in subgraph are completely connected with each other. Given a Graph, find if it can be divided into two Cliques.

Input : G[][] =   {{0, 1, 1, 0, 0},
                  {1, 0, 1, 1, 0},
                  {1, 1, 0, 0, 0},
                  {0, 1, 0, 0, 1},
                  {0, 0, 0, 1, 0}};
Output : Yes

This problem looks tricky at first, but has a simple and interesting solution. A graph can be divided in two cliques if its complement graph is Bipartitie. So below are two steps to find if graph can be divided in two Cliques or not.

1. Find complement of Graph. Below is complement graph is above shown graph. In complement, all original edges are removed. And the vertices which did not have an edge between them, now have an edge connecting them.
   
2. Return true if complement is Bipartite, else false. Above shown graph is Bipartite. Checking whether a Graph is Biparitite or no is discussed here.

Time complexity of above implementation is O(V2).

bool isBipartiteUtil(int G[][V], int src, int colorArr[])

{

    colorArr[src] = 1;

 

    // Create a queue (FIFO) of vertex numbers and enqueue

    // source vertex for BFS traversal

    queue <int> q;

    q.push(src);

 

    // Run while there are vertices in queue (Similar to BFS)

    while (!q.empty())

    {

        // Dequeue a vertex from queue

        int u = q.front();

        q.pop();

 

         // Find all non-colored adjacent vertices

        for (int v = 0; v < V; ++v)

        {

            // An edge from u to v exists and destination

            // v is not colored

            if (G[u][v] && colorArr[v] == -1)

            {

                // Assign alternate color to this adjacent

                // v of u

                colorArr[v] = 1 - colorArr[u];

                q.push(v);

            }

 

            // An edge from u to v exists and destination

            // v is colored with same color as u

            else if (G[u][v] && colorArr[v] == colorArr[u])

                return false;

        }

    }

 

    // If we reach here, then all adjacent vertices can

    // be colored with alternate color

    return true;

}

 

// Returns true if a Graph G[][] is Bipartite or not. Note

// that G may not be connected.

bool isBipartite(int G[][V])

{

    // Create a color array to store colors assigned

    // to all veritces. Vertex number is used as index in

    // this array. The value '-1' of  colorArr[i]

    // is used to indicate that no color is assigned to

    // vertex 'i'.  The value 1 is used to indicate first

    // color is assigned and value 0 indicates

    // second color is assigned.

    int colorArr[V];

    for (int i = 0; i < V; ++i)

        colorArr[i] = -1;

 

    // One by one check all not yet colored vertices.

    for (int i = 0; i < V; i++)

      if (colorArr[i] != -1)

        if (isBipartiteUtil(G, i, colorArr) == false)

           return false;

 

     return true;

}

 

// Returns true if G can be divided into

// two Cliques, else false.

bool canBeDividedinTwoCliques(int G[][V])

{

     // Find complement of G[][]

     int GC[V][V];

     for (int i=0; i<V; i++)

       for (int j=0; j<V; j++)

          if (i != j)

             GC[i][j] = !G[i][j];

 

     // Return true if complement is Bipartite

     // else false.

     return  isBipartite(GC);

}

Read full article from Two Clique Problem (Check if Graph can be divided in two Cliques) - GeeksforGeeks