Given an unweighted graph $G = (V,E)$. I am interested in enumerating all pairs of disconnected cliques, i.e. there should not exist any edge between two cliques. (For example, there would not exist any such pair in a complete graph). A clique could be of any size $\geq 1$.
Are there any standard approaches to solve this problem? If so, could someone please highlight the sources or suggest some approaches?
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<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$.
Another way of thinking about this problem is to consider the complement of your graph $G$. In the complement, the subgraphs you are looking for are complete bipartite subgraphs, also called bicliques. The problem of enumerating all maximal bicliques is well studied, due to many applications on data mining. I believe this is most cited paper on the subject.
