Maximum clique of DIMACS graph C2000.9: find 81 or prove 80
Difficulty 62: the best certified upper bound (168, a preprint) is more than twice the best clique (80), so proving 80 is far beyond exact methods, and heuristics have not found 81 in nearly two decades; level with the World TSP (62) as a finite instance with no proof route. Application value 4 and leverage 8: a random benchmark graph.
The problem
In a dense 2000-dot graph, find 81 dots that are all joined to each other, or prove none exist.
- 1Dense random graph, 2000 dots
- 2Heuristics find a group of 80
- 3Best proof: at most 168
- 4Is 81 possible?
The question. A graph is a set of vertices joined by edges; you can store it as an adjacency matrix with when vertices and are joined. A is a set of vertices in which every pair is joined, and the is the size of the largest one. C2000.9 is a standard test graph from the 1993 DIMACS challenge: 2,000 vertices, each pair joined with probability 0.9, giving 1,799,532 edges. What is its clique number?
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- Then
- Maximum clique of DIMACS graph C2000.9: find 81 or prove 80The problem
State of the art
The literature lists ω(C2000.9) ≥ 80 (for instance in the DIMACS table of the 2024 review by Marino, Buffoni and Zavalnij). A 2026 arXiv preprint by Krpan and Povh (arXiv:2607.11726, not peer reviewed) improves the best certified integer upper bound from 177 to 168 for C2000.9 using core and truss reductions with the Lovász theta function, and states that the exact clique numbers of C500.9, C1000.9 and C2000.9 are not known. The gap between 80 and 168 is the remaining distance: exact methods are far from proving 80 optimal.
Realistic applications
Maximum clique has uses in bioinformatics, coding theory and network analysis, but this random instance has no direct application. Better upper bounds help general branch-and-bound and semidefinite-programming solvers.
What counts as solved
A clique of 81 vertices, verified by checking all pairs against the instance file; or an upper bound of 80 certified by an independently checkable proof (a branch-and-bound log with bounds that can be re-derived, or an exact SDP/LP dual certificate).
How it gets verified
Bound / recordA numeric bound or record checked from a certificate or recomputation.
Quantity: the clique number of DIMACS C2000.9 (2000 vertices, 1,799,532 edges); lower bound 80 (heuristics, listed in the 2024 review), best certified upper bound 168 (Krpan and Povh preprint, 2026). A clique of 81 vertices is checked pairwise against the instance file. An upper bound needs a certificate that an independent program can recheck: a branch-and-bound proof tree with re-derivable bounds, or an exact dual certificate for the bounding relaxation.
Claims under verification
+ add a claimWhere the work is
Both directions need computation; the upper-bound side also needs new theory in bounding relaxations and reductions.
Bottlenecks
ranked by votes- #1TheoryBounding gap between 80 and 168
Colouring bounds and Lovász theta bounds are loose on dense random graphs; proving 80 would need relaxations far tighter than the ones now known.
Community grades
Sign in to add your own grade.
Connected problems
No connections yet.
Progress
- Jul 13, 2026Upper bound 168 (preprint)source
Krpan and Povh reported an improved certified upper bound of 168 for C2000.9 in a preprint.