Finding and Counting Cliques with cliquer

by Derrick Stolee

For a graph G, a clique is a set S \subseteq V(G) such that all pairs of vertices in S are adjacent in G. 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 v_1,\dots,v_n and then iteratively select the vertices for S by increasing indices. The standard recursive algorithm is as follows:

FindMaxClique(G, U, S, m)
if |S| + |U| < m then
    return Null     // No clique will be big enough
else if U = \varnothing then
    return S     // The clique found so far
end if
T \leftarrow Null
for all v_j \in U do
    U \leftarrow U - \{v_j\}
    S' \leftarrow S \cup \{ v_j \}
    U' \leftarrow U \cap N_G(v_j)
    T' \leftarrow FindMaxClique(G, U', S', m)
    if T' \neq Null and |T'| > m then
        m \leftarrow |T'|
        T \leftarrow T'
    end if
end for
return T

Call the above algorithm with the call FindMaxClique(G, V(G), \varnothing, 1) 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 S. 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 m to |T'| + 1 when we find a new clique T' of size at least m. 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 v_1,\dots,v_n. However, this ordering is much more important to cliquer than the backtracking search. Define c[i] to be the maximum size of a clique in the subgraph induced by the vertices v_1,\dots,v_i. We will compute these values c[1], c[2], \dots, c[n] in order and observe that c[n] is the clique number of G.

Observe that c[i] \leq c[i+1] \leq c[i] + 1 for all i \in \{1,\dots,n-1\}. Thus, we only need to look for a clique of size m=c[i]+1 in \{v_1,\dots,v_{i+1}\}, and such a clique must contain v_{i+1}. This gives us a start to our clique. As we grow our clique S and U is the set of possible additions to S, we can still prune when |S| + |U| < m. But, the extra bonus we receive is that we can test how large our clique can grow by finding k = \max\{ j : v_{j} \in U\} and then pruning when |S| + c[k] < m. This extra pruning mechanism more than makes up for the fact that we are performing n distinct clique calculations to determine each value c[i].

Cliquer(G, U, S, m, c)
if |S| + |U| < m then
    return Null     // No clique will be big enough
else if U = \varnothing then
    return S     // The clique found so far
end if
k \leftarrow \max\{ j : v_j \in U\}
if |S| + c[k] < m then
    return Null     // No clique will be big enough
end if
for all v_j \in U in decreasing order do
    U \leftarrow U - \{v_j\}
    S' \leftarrow S \cup \{ v_j \}
    U' \leftarrow U \cap N_G(v_j)
    T' \leftarrow FindMaxClique(G, U', S', m)
    if T' \neq Null and |T'| \geq m then
        return T'
    end if
end for
return Null

To start the recursion to compute c[i], simply call Cliquer(G, N_G(v_i), \{v_i\}, c[i-1]+1) and if a set is returned it will be a clique of size c[i]=c[i-1]+1. Otherwise, set c[i] = c[i-1].

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 v_1,\dots,v_n. Niskanen and Östergård have a few ideas of how to order these vertices to improve performance. Observe that if the graph is k-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 v_1,\dots,v_n where the map v_i \mapsto v_{i+1} is an automorphism. Further, these graphs are very dense, so when the algorithm is in process the set U consists of a few contiguous segments v_i,\dots,v_j. Then, the maximum clique size in such a segment v_i,\dots,v_j is equal to c[j-i+1]. It can be beneficial to use these numbers to bound the size of a clique in the pruning stage.

Resources

Cliquer Homepage

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.

Advertisements