### Finding and Counting Cliques with cliquer

#### by Derrick Stolee

For a graph , a **clique** is a set such that all pairs of vertices in are adjacent in . Determining the maximum size of a clique in a graph is a classic NP-Complete problem, but sometimes you just need to find or count cliques anyway.

Today, we discuss the *cliquer* algorithm, as designed by Niskanen and Östergård. Their very efficient implementation is available on their *cliquer* homepage. The entire implementation is very succinct and can be used as a library. In fact, Sage uses *cliquer* for its backend for clique algorithms. The main algorithm computes the maximum (weighted) clique and also can count maximum or maximal (weighted) cliques. We focus on the unweighted case.

As a short warning: if you want to compile *cliquer* as a C++ library, you need to do two things: 1. Replace all instances of a variable named “new” with a different name, and 2. Cast all malloc/calloc/realloc methods to specific data types. The data types used by *cliquer* are not compatible with *nauty*, so I recommend that if you are simultaneously looking for cliques while performing isomorph-free generation that you store two copies of your graph, one in each format, and update each separately.

### Standard backtracking algorithm

The standard method to search for any combinatorial object is to use a backtracking search, with some simple ordering constraints. For instance, we can order the vertices and then iteratively select the vertices for by increasing indices. The standard recursive algorithm is as follows:

`FindMaxClique()`

**if** **then**

**return** Null // No clique will be big enough

**else if** **then**

**return** // The clique found so far

**end if**

Null

**for all** **do**

FindMaxClique()

**if** Null **and** **then**

**end if**

**end for**

**return**

Call the above algorithm with the call FindMaxClique() to find a maximum clique.

While this algorithm will find a maximum clique (and can be modified easily to count maximum cliques) it lacks a good way to predict that it made poor choices for the first few elements of . That is the main contribution to the *cliquer* algorithm: it has a better way to “predict” how many vertices it can pick up in later choices, which helps significantly with pruning.

Before we continue, take some time to understand the following ways to change the above algorithm:

- If we are only looking for a largest clique, we can set to when we find a new clique of size at least . This prevents us from reporting other cliques of the same size while also allowing us to prune more quickly.
- We can replace the use of the size of the sets with the sum of weights in the sets in the case of a (vertex) weighted graph.
**Exercise:**Adapt the above algorithm to only search for maximal cliques in such a way that it provides a pruning step.

### The *cliquer* algorithm

The *cliquer* algorithm begins with a vertex ordering . However, this ordering is much more important to *cliquer* than the backtracking search. Define to be the maximum size of a clique in the subgraph induced by the vertices . We will compute these values in order and observe that is the clique number of .

Observe that for all . Thus, we only need to look for a clique of size in , and such a clique *must* contain . This gives us a start to our clique. As we grow our clique and is the set of possible additions to , we can still prune when . But, the extra bonus we receive is that we can test how large our clique can grow by finding and then pruning when . This extra pruning mechanism more than makes up for the fact that we are performing distinct clique calculations to determine each value .

`Cliquer()`

**if** **then**

**return** Null // No clique will be big enough

**else if** **then**

**return** // The clique found so far

**end if**

**if** **then**

**return** Null // No clique will be big enough

**end if**

**for all** *in decreasing order* **do**

FindMaxClique()

**if** Null **and** **then**

**return**

**end if**

**end for**

**return** Null

To start the recursion to compute , simply call Cliquer() and if a set is returned it will be a clique of size . Otherwise, set .

**Exercise.** Adapt the *cliquer* algorithm (as described) to count maximum cliques. What about maximal cliques?

### A few short notes

The performance of the *cliquer* algorithm is closely tied to the ordering . Niskanen and Östergård have a few ideas of how to order these vertices to improve performance. Observe that if the graph is -colored and the vertices are ordered by color class, then selecting a vertex in a given color class immediately removes the other vertices of that color from consideration. This may be a good ordering, and improves when fewer colors are used, but computing the chromatic number is itself an NP-complete problem! Thus, very little time should be spent trying to find a small coloring and perhaps a simple algorithm, such as greedy coloring, should be used to find a non-optimal coloring.

Other orders are possibly rewarding. In some work that I am currently editing with several coauthors, we consider computing the clique number of some graphs that are vertex-transitive subject to a cyclic ordering where the map is an automorphism. Further, these graphs are very dense, so when the algorithm is in process the set consists of a few contiguous segments . Then, the maximum clique size in such a segment is equal to . It can be beneficial to use these numbers to bound the size of a clique in the pruning stage.

### Resources

Sampo Niskanen and Patric R.J. Östergård, Cliquer User’s Guide.

Patric R. J. Östergård, A fast algorithm for the maximum clique problem, Discrete Applied Mathematics 120 (2002) 197-207.

It is interesting that the naive algorithm can be formalized in tree-like resolution: whatever is the heuristic used to sort the vertex set, if the graph has no clique of size k << n then the trace of the algorithm can be read as a resolution proof (of tree-like shape) that such clique does not exists. Such proof must have length roughly n^k for several graphs.

The second algorithm uses the vector c[i] and probably cannot be formalized in tree-like resolution, and thus the lower bound does not apply. It is still open whether the lower bound holds for general resolution proofs, which naturally capture more algorithms.

That is a very interesting perspective that I had never thought about.