Fast $k$-clique checking algorithm?

Question

I have a problem where part of it requires answering the question: does graph $G=(V,E)$ contain a clique of size at least $k$?

Obviously, answering this question is a NP-Complete problem. I am no trying to find a polynomial time algorithm. I am trying to find an empirically fast algorithm that works well for moderately large graphs (say $|V| < 100,000$).

I have already tried a few approaches, like:

1. dOmega library: https://github.com/jwalteros/dOmega/tree/master
2. Cliquer: https://users.aalto.fi/~pat/cliquer.html
3. Quick cliques (although this is for enumerating all cliques): https://github.com/darrenstrash/quick-cliques

None of these approaches seem to work well for what I want. However, I also have the feeling that none of them is using information about $k$ to maybe speedup search (not sure if this makes sense to be honest). Approach (1) tries to solve a Max-Clique, approach (2) uses Bron-Kerbosch algorithm even though it has a function to search for a single clique of a given size, and (3) enumerates all cliques.

I don't need the clique itself, just identifying whether $G$ has a clique of size at least $k$. Alternatively, I am happy with any bound technique that has reasonable tightness to answer whether $G$ cannot have for sure a clique of size at least $k$. For example, I know that the largest clique size $\omega$ of $G$ with degeneracy $d$ respects the relation $\omega \leq d+1$. Unfortunately, computing degeneracy of my graphs has proven fruitless since the bound is typically not tight enough to help with any information.

Does anyone have a suggestion? Converting the clique problem into something else is also a possibility, in case this could help with finding a empirically fast algorithm.

Edit: for clarification. We cannot rely on a commercial ILP solver. Ideally, we would like a special-purpose algorithm, or if an open-source ILP solver can handle large instances, then this can also be considered.

Values of $k \leq 20$ we can already handle well with our current approach. We are looking at an algorithm to do the same quickly when $30 \leq k \leq 200$. Techniques that offer good bounds are also very much welcome.

Average degree of nodes varies widely. For example, some instances with 800 nodes have average node degree of $\approx 290$ while some with 2000 nodes also have $\approx 300$. The ratio between $k$ and $\omega$ (the actual max-clique) also varies, but so far we have seen ratios $0.5 \leq \frac{\omega}{k} \leq 2$.

We don't have any particular structure in the graph (not one that we are of anyway).

Answer 1

I suspect you are likely to be out of luck. My advice is to try to find some other way to meet your business needs without requiring you to solve this computational task. The clique problem is NP-hard, so you should not expect any efficient algorithm for your problem.

In particular, testing whether there exists a clique of size $\ge k$ is as hard (under worst-case complexity) as finding the size of the maximum clique. (The reduction: if you had an algorithm for testing the existence of a clique, then you could use binary search on $k$ to find the size of the maximum clique.) Indeed, the usual way of proving that the clique problem is NP-hard focuses on the decision problem (given a graph and $k$, test whether there is a clique of size $\ge k$) rather than on the optimization problem (given a graph, find the size of the maximum clique), so you are already considering exactly the same problem that is studied in complexity theory.

Standard approaches for dealing with NP-hardness are to look for approximation algorithms, fixed-parameter tractable algorithms, or algorithms whose worst-case running time is exponential but maybe fast enough in practice. However, approximation algorithms are a dead end: the clique problem is hard to NP-hard even to approximate to within an approximation ratio of $O(n^{1-\epsilon})$ -- or in other words, it is very hard even to approximate the size of the largest clique, even with a very rough/crude approximation. Also, the clique problem is believed to not be fixed-parameter tractable. Especially, assuming the exponential time hypothesis, no algorithm can solve the problem in $n^{o(k)}$ time -- or in other words, you should not expect an algorithm that works on all possible graphs, using only the fact that $k$ is small, and has a reasonable running time. See https://en.wikipedia.org/wiki/Clique_problem#Approximation_algorithms, https://en.wikipedia.org/wiki/Clique_problem#Fixed-parameter_intractability.

One reasonable approach is to use a dedicated clique solver. It seems you have already tried that.

Another reasonable approach is to use an ILP solver or SAT solver. I'll list below some ways that you can formulate this as an ILP/SAT instance. However, I expect that these will fail once $k$ gets large enough, so I am not optimistic that these will lead to a useful solution for your specific problem with your particular parameters. My uneducated guess would be that maybe there simply is no algorithm with the characteristics you are hoping for.

SAT

There are many ways to encode the clique problem as a SAT instance. If this is a critical problem, I would suggest you explore all options to see what works best on the kinds of instances you face.

One approach is to introduce boolean variables $x_v$, one per vertex $v \in V$ of the graph. For each $(u,v) \notin E$, add a clause $\neg x_u \lor \neg x_v$. Also, add the constraint that at least $k$ of the $x$'s be true (see Encoding 1-out-of-n constraint for SAT solvers, Reduce the following problem to SAT, https://stackoverflow.com/q/43081929/781723). This requires $n$ boolean variables and something like $n^2+O(n \log^2 k)$ clauses, with all clauses being small.

Another approach is to introduce boolean variables $x_v$, one per vertex $v \in V$, and $y_{u,v}$, one per edge $(u,v) \in E$ with $u<v$. Add clauses $x_u \lor \neg y_{u,v}$, $x_v \lor \neg y_{u,v}$, $\neg x_u \lor \neg x_v \lor y_{u,v}$ for each $(u,v) \in E$ with $u<v$. Also, add the constraints that at least $k$ of the $x$'s be true and at least $k(k-1)/2$ of the $y$'s be true. This requires $n+m$ boolean variables and something like $O(m \log^2 k)$ clauses, with all clauses being small. (Here $n =$ the number of vertices, $m =$ the number of edges.)

There are probably many other encodings into SAT.

Then, you can use an off-the-shelf SAT solver, of which there are many excellent ones.

Integer Linear Programming

You can also use effectively the same encoding into ILP. Each variable becomes a zero-or-one integer variable. Each clause has a direct translation to ILP (e.g., $r \lor s \lor t$ becomes $r + s + t \ge 1$). The one main difference is that the $k$-out-of-$n$ constraint can be encoded very easily using a single linear inequality.

Finally, you can give this to an ILP solver, such as Gurobi.