1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Saurabh Agrawal Dec 21 '17 at 17:53
  • $\begingroup$ 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$ $\endgroup$ – JimN Dec 21 '17 at 18:37
  • $\begingroup$ 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. $\endgroup$ – Saurabh Agrawal Dec 21 '17 at 20:00
  • $\begingroup$ How large are your graphs? $\endgroup$ – Juho Dec 21 '17 at 20:02
  • $\begingroup$ 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? $\endgroup$ – JimN Dec 21 '17 at 20:25
1
$\begingroup$

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

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