reference request - Practical maximum clique search on 300–900 vertex graphs with only a few seconds available - MathOverflow
Practical maximum clique search on 300–900 vertex graphs with only a few seconds available
Ask Question
Asked<br>today
Modified<br>today
Viewed<br>41 times
$\begingroup$
I am looking for guidance on a practical maximum clique problem.
Suppose I am given an undirected graph $G=(V,E)$, usually with about $300$ to $900$ vertices. I need to find a clique $C \subseteq V$, meaning that for every two distinct vertices $u,v \in C$, the edge $(u,v)\in E$.
The ideal goal is to find a maximum clique. In my setting, however, there is a short wall-clock deadline, usually around $6$ to $30$ seconds. So in practice, I need to return the largest clique I can find before the deadline.
The returned clique also needs to be maximal. By this I mean that there should be no vertex $w \in V \setminus C$ that can be added to $C$ while keeping it a clique. So returning just any maximal clique is not useful; the clique needs to be large, ideally close to maximum.
I understand the basic difficulty: the maximum clique problem is NP-hard, and brute force over all vertex subsets is impossible here, since there are $2^{|V|}$ possible subsets.
I have seen several kinds of methods mentioned:
branch and bound with coloring bounds;
Bron--Kerbosch-style algorithms;
bitset-based exact search;
greedy construction;
local search or tabu search;
randomized restarts;
hybrid methods.
The part I am most unsure about is what one should do when the time limit is very short. Since the total deadline is only a few seconds, I cannot spend much time testing many different algorithms on the current graph. Ideally, I would like to decide very quickly, perhaps within the first $0.1$ to $0.5$ seconds, which approach to run first.
My questions are:
For graphs with about $300$--$900$ vertices and time limits of $6$--$30$ seconds, what maximum clique methods are considered strongest in practice?
If I only need a very large clique and do not need to prove optimality, are exact branch-and-bound methods still a good starting point, or are local-search / tabu-search methods usually better?
Are there cheap graph statistics, such as edge density, degree distribution, degeneracy, clustering, or approximate coloring number, that help decide which solver family to try first?
Is there literature on algorithm selection or solver portfolios for maximum clique, similar to what exists for SAT and other combinatorial optimization problems?
Are there well-known benchmark papers or implementations that would be good starting points before writing my own solver?
I am not asking anyone to solve a particular graph instance. I am trying to understand what algorithms and references are considered standard for this practical regime, especially when the time limit is too short to run many different approaches.
reference-request<br>co.combinatorics<br>graph-theory<br>algorithms<br>combinatorial-optimization
Share
Cite
Improve this question
Follow
asked 1 hour ago
user594194
1122 bronze badges
New contributor
user594194 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.<br>Check out our Code of Conduct.
$\endgroup$
Add a comment
Sorted by:
Reset to default
Highest score (default)
Date modified (newest first)
Date created (oldest first)
You must log in to answer this question.
Start asking to get answers
Find the answer to your question by asking.
Ask question
Explore related questions
reference-request<br>co.combinatorics<br>graph-theory<br>algorithms<br>combinatorial-optimization
See similar questions with these tags.
Featured on Meta
Partnering with Communities to Modernize Policies & Norms
Related
Practical error-estimates for (adaptive) Newton-Cotes Quadrature
Seeming contradiction about P vs NP between graphclasses.org and at least two papers about clique in even-hole-free graphs
Determine if a graph has a large clique
What is the relation between size of maximum clique and branchwidth?
Practical permutation search problems resilient to backtrack techniques
Which is the most time efficient algorithm for having a Tait Coloring (edge-3-coloring) of planar cubic graphs?
11
Do you know a faster algorithm to color planar graphs?
Complexity of a variant of Four coloring theorem
Variant of Graph coloring
Question feed
Subscribe to RSS
Question feed<br>To subscribe to this RSS feed, copy and paste this URL into your RSS reader.
Blog
Site design / logo © 2026 Stack Exchange Inc;<br>user contributions licensed under<br>CC BY-SA<br>rev 2026.6.23.43712