Return to Answer

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]

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 https://www.cs.yale.edu/homes/aspnes/pinewiki/attachments/LinearProgramming/lp.pdf

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: https://en.wikipedia.org/wiki/Clique_problem#Algorithms

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.

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]

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.

@kglr commented that the source code is actually readable using

PrintDefinitions[GraphComputation`InternalFindClique]

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 https://www.cs.yale.edu/homes/aspnes/pinewiki/attachments/LinearProgramming/lp.pdf

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: https://en.wikipedia.org/wiki/Clique_problem#Algorithms

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.

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]

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 https://www.cs.yale.edu/homes/aspnes/pinewiki/attachments/LinearProgramming/lp.pdf

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: https://en.wikipedia.org/wiki/Clique_problem#Algorithms

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.

@kglr commented that the source code is actually readable using

PrintDefinitions[GraphComputation`InternalFindClique]

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. You will find multiple ways to formulate this problem as ILP.

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$. $w_i$ denote the vertex weights. $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 https://www.cs.yale.edu/homes/aspnes/pinewiki/attachments/LinearProgramming/lp.pdf

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: https://en.wikipedia.org/wiki/Clique_problem#Algorithms

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.

@kglr commented that the source code is actually readable using

PrintDefinitions[GraphComputation`InternalFindClique]

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 https://www.cs.yale.edu/homes/aspnes/pinewiki/attachments/LinearProgramming/lp.pdf

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: https://en.wikipedia.org/wiki/Clique_problem#Algorithms

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.