Max Clique Optimization

Question

I'm trying to find the max clique in a graph (adjacency matrix), the graph can have up to 50 nodes. Currently, what I have starts taking forever when the graph sizes get to around n=40. Can anyone find any optimizations I can make?

 public static void maxClique(Graph graph, List<Integer> clique) {
 //Get the newest node added to the clique
 int currentValue = clique.get(clique.size() - 1);
 if (clique.size() > max.size()) {
 max = clique;
 }
 // Check every node
 for (int i = 0; i < graph.size; i++) {
 // If the node being checked is connected to the current node, and isn't the current node
 if (graph.matrix[currentValue][i] == 1 && !clique.contains(i)) {
 //Check if the new clique is bigger than the current max.
 //Make a new clique and add all the nodes from the current clique to it
 ArrayList<Integer> newClique = new ArrayList<>();
 newClique.addAll(clique);
 //Add the new node
 newClique.add(i);
 //Repeat
 if (makesNewClique(graph, clique, i)) {
 maxClique(graph, newClique);
 }
 }
 }
 }

Full class contents: https://pastebin.com/fNPjvgUm Adjacency matrix: https://pastebin.com/yypN9K4L

• David Eisenstat: I think this algorithm is much slower than Bron--Kerbosch for starters (time on the order of k! versus 2^k for each k-node clique). If you just need the maximum clique, there are further optimizations.
• Coolcodehere: @DavidEisenstat I implemented Bron-Kerbosh and it's way faster, thanks!

Answer 1

David Eisenstat 's comment had the answer, here's my code for anyone that comes here later:

 public void bronKerbosh(Set<Integer> p, Set<Integer> r, Set<Integer> x) {
 if (x.isEmpty() && p.isEmpty() && r.size() > max.size()) {
 max = new ArrayList<>();
 max.addAll(r);
 }
 Object[] pArr = p.toArray();
 for (Object vTemp : pArr) {
 int v = (int)vTemp;
 Set<Integer> newR = new HashSet<>();
 newR.addAll(r);
 newR.add(v);
 bronKerbosh(intersect(p, neighbors(v)), newR, intersect(x, neighbors(v)));
 p.remove(v);
 x.add(v);
 }
 }