9
$\begingroup$

If h is a graph, FindClique[g, {n}] should return a clique on exactly $n$ vertices if one exists in h.

Consider the following:

h = Graph[{1 <-> 2, 1 <-> 3, 1 <-> 4, 1 <-> 6, 2 <-> 3, 2 <-> 4, 
   2 <-> 6, 3 <-> 4, 4 <-> 6}, VertexLabels -> "Name"]
FindClique[h, {3}]

The output is {}. However, there is a clique on 3 vertices in h, like {1,2,4}. Is this indeed a bug, or am I overlooking something? Interestingly, FindCycle[h, {3}, All] does find all triangles of the graph, including {1 <-> 2, 2 <-> 4, 4 <-> 1}. I would expect FindClique[h, {3}, All] to return exactly the same answer as FindCycle[h, {3}, All] in general.

I am running V10.0.0.0, by the way.

$\endgroup$
  • 2
    $\begingroup$ Confirmed in v9.0.1 and v10.0.2. You really should upgrade to 10.0.2 BTW. Please report this Wolfram support and let us know what they said. Tagging as bug. $\endgroup$ – Szabolcs Feb 17 '15 at 14:37
  • $\begingroup$ Or maybe I spoke too soon and it only find maximal cliques? Let's wait until someone else chimes in. $\endgroup$ – Szabolcs Feb 17 '15 at 14:40
  • $\begingroup$ @Szabolcs Oh, maybe. If it is so, the documentation is quite confusing... $\endgroup$ – Juho Feb 17 '15 at 14:43
  • $\begingroup$ Indeed, it is confusing. But it appears that it finds maximal cliques only, the results agree with igraph when I test on many random graphs. So not a bug in the functions ... but a bug in the documentation then. I'll write an answer after breakfast $\endgroup$ – Szabolcs Feb 17 '15 at 14:43
10
$\begingroup$

This is not a bug. It appears that FindCliques returns only maximal cliques, i.e. cliques (complete subgraphs) that are not a subset a larger clique.

In your example {1,2,4} is not maximal because it can be extended to {1,2,4,5}.

I would not call this a bug because the behaviour is consistent, and the documentation does suggest that this is the case:

FindClique[g] finds a largest clique in the graph g.

...

A clique is a maximal set of vertices where the corresponding subgraph is a complete graph.

Personally I find this rather confusing because the standard definition of clique that I am familiar with does not require it to be maximal. It appears that by cliques Mathematica means maximal cliques.

Update: As of 2015 May the documentation page of FindCliques includes a Background section which explains precisely the terminology and what the function does.


Update: Now I recommend using IGraph/M instead of IGraphR. The command is IGCliques[g, Infinity]. See here for more details.

Here's a quick test to show that Mathematica finds maximal cliques correctly, by comparing with igraph:

canonical = Sort[Sort /@ Round[#]] &

g = RandomGraph[{10, 20}];

canonical@FindClique[g, Infinity, All]

(* {{1, 6}, {1, 10}, {2, 6}, {2, 10}, {4, 5}, {4, 6}, {1, 3, 7}, {1, 7, 8}, {3, 7, 9}, {4, 7, 8}, {2, 3, 5, 9}} *)

<<IGraphR`
canonical@IGraph["maximal.cliques"][g]

(* {{1, 6}, {1, 10}, {2, 6}, {2, 10}, {4, 5}, {4, 6}, {1, 3, 7}, {1, 7, 8}, {3, 7, 9}, {4, 7, 8}, {2, 3, 5, 9}} *)

And @@ Table[
   With[{g = RandomGraph[{10, 20}]}, 
     canonical@FindClique[g, Infinity, All] === canonical@IGraph["maximal.cliques"][g]],
   {100}]

(* True *)

Two workarounds for finding all cliques, not only maximal ones:

  • First find the maximal ones, then take all Subsets of each clique. This does not make it easy to find cliques only up to size $k$ though.

  • Use igraph though IGraphR, like this: IGraph["cliques"][h, 3, 3] $\longrightarrow$ {{1., 2., 3.}, {1., 2., 4.}, {1., 2., 5.}, {1., 3., 4.}, {1., 4., 5.}, {2., 3., 4.}, {2., 4., 5.}}

$\endgroup$
9
$\begingroup$

Mathematica finds only maximal cliques. It has more sense since any subset of clique is clique. So you can use Subsets to find all cliques of the size k

findAllCliques[g_, {k_}] := Union @@ (Subsets[#, {k}] & /@ FindClique[g, {k, ∞}])

findAllCliques[h, {3}]
(* {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}} *)
$\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.