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:
- dOmega library: https://github.com/jwalteros/dOmega/tree/master
- Cliquer: https://users.aalto.fi/~pat/cliquer.html
- 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).