Enumerating pairs of disconnected cliques in a graph
I figured out this solution while discussing with a Professor.

The above problem could be formulated into a clique search problem. Let the input graph be $G_1 = (V_1,E_1)$. Create a duplicate $G_2 = (V_2,E_2)$ of $G_1$. Let vertices in $V_1$ be denoted by $\{v_{11},v_{12},...,v_{1k}\}$ and their duplicates in $V_2$ be represented by $\{v_{21},v_{22},...,v_{2k}\}$. Now, for each pair of vertices $(v_{1i},v_{1j})$ in $G_1$ without an edge with $(i&lt;j)$, connect $(v_{1i},v_{2j})$. Then, all the desired pairs of disconnected cliques of $G_1$ can be obtained as cliques of $G_1 \cup G_2$ that have vertices in both $G_1$ and $G_2$.