# Enumerating pairs of disconnected cliques in a graph

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 am counting pairs of objects. For example, consider a graph G = (V,E), where V = {v1,v2,v3,v4} and E = {(v1,v2),(v3,v4)}. Then {v1,v2} and {v3,v4} are two cliques that are disconnected. – Saurabh Agrawal Dec 21 '17 at 17:53
• So, if you know how to count your cliques and you have $n$ cliques, then you have $n(n-1)/2$ pairs. Isn't that your answer? If you are asking to list all pairs of cliques, then you need to name your cliques: $c_1, c_2, c_3,$ etc. And the list of all cliques are $c_i c_j$ for all pairs $i$ and $j$ where $i>j$ – JimN Dec 21 '17 at 18:37
• No, because cliques need not be disjoint. For instance, we could have {A,B,C}, and {B,C,D} as two cliques, but they would not form a pair of disconnected cliques. – Saurabh Agrawal Dec 21 '17 at 20:00
• How large are your graphs? – Juho Dec 21 '17 at 20:02
• You will need to specify whether you mean maximal cliques as well. (Every edge counts as a 2-clique in some contexts). Can you also clarify what disconnected cliques means to you? in your last example, you have a shared vertex to show two cliques which are not disconnected. What if you had two cliques {a,b} and {c,d} and there was an edge joining b and c? Are cliques {a,b} and {c,d} disconnected in your problem? – JimN Dec 21 '17 at 20:25

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