Is there a bug in FindClique?

Question

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.

Answer 1

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

Answer 2

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}} *)