6
$\begingroup$

Does anyone know which algorithms Mathematica use for computing FindClique[g] and FindClique[g,{n}] (finds a maximal clique containing exactly n vertices)?

Improve this question
$\endgroup$
18
  • 2
    $\begingroup$ you can see the definition of the function called by FindClique using Needs["GeneralUtilities`"]; PrintDefinitions[GraphComputation`GraphCliqueDump`findClique] $\endgroup$
    – kglr
    Commented May 1, 2020 at 9:48
  • 1
    $\begingroup$ try PrintDefinitions[GraphComputation`InternalFindClique] and click on the link to get the notebook that gives definition of findClique. $\endgroup$
    – kglr
    Commented May 1, 2020 at 10:16
  • 1
    $\begingroup$ @kglr I don't think that spelunking will give a productive answer to this question. I really wonder if OP wants to know the specific algorithm Mathematica uses, or if he just wants to know how to find maximal cliques, e.g. en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm $\endgroup$
    – Szabolcs
    Commented May 1, 2020 at 10:24
  • 2
    $\begingroup$ @Szabolcs, the code is not too long and it looks like the core method is just LP. $\endgroup$
    – kglr
    Commented May 1, 2020 at 10:36
  • 1
    $\begingroup$ @Szabolcs I want to know which algorithm WL uses to compute a maximal clique. The reason for that is straightforward. I'm planning to use it as one of the phases of the solution of a "big" problem. Before to use it as a "black box" I prefer to understand the prof and con of the "black box." $\endgroup$
    – Kiril Danilchenko
    Commented May 1, 2020 at 10:43

1 Answer 1

Reset to default
3
$\begingroup$

I'll leave the answer below as an explanation of what GraphComputation`InternalFindClique does, but I am not convinced that FindClique really uses GraphComputation`InternalFindClique. InternalFindClique seems to simply ignore its size argument.

@kglr commented that the source code is actually readable using

PrintDefinitions[GraphComputation`InternalFindClique]

enter image description here

It appears that FindClique finds independent vertex sets in the complement graph, which is an equivalent problem. It solves the independent vertex set problem using an integer linear programming (ILP) formulation which it passes to LinearProgramming.

What's implemented here is:

Maximize $$\sum_{i \in V} w_i x_i$$ subject to the constraints $x_i + x_j \le 1$ for all edges $(i,j)$ (independence) and $x_i \in \{0,1\}$ for all vertices $i$.

$i$ denotes vertices, $w_i$ denotes vertex weights, and $x_i = 1$ means that vertex $i$ is part of the independent vertex set that was found.

I am not very familiar with ILP, but some googling suggests that this is a standard formulation, e.g. see this link.

This answers your question about what method FindClique uses in Mathematica 12.1.

There are many other methods to find maximal cliques. Wikipedia lists several.

As far as I know, the most widely used method to solve this problem is the Bron-Kerbosch algorithm.

Another way to find maximal cliques in Mathematica is to use igraph's implementation through IGraph/M. The igraph documentation was the following note:

The current implementation uses a modified Bron-Kerbosch algorithm to find the maximal cliques, see: David Eppstein, Maarten Löffler, Darren Strash: Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. Algorithms and Computation, Lecture Notes in Computer Science Volume 6506, 2010, pp 403-414.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.