What this research found
Finding the largest set of vertices in a graph that are all mutually adjacent is NP-hard and resistant even to approximation. An exact branch-and-bound solver was written from scratch, using no external clique, integer-programming or satisfiability machinery, and run on five instances from the maximum-clique track of the Second DIMACS Implementation Challenge under a 300-second per-instance cutoff. Four instances were closed to proven optimality at exactly the published optima, while the densest timed out holding a verified clique of 39 against a known optimum of 44. The accompanying analysis attributes the difficulty spread not to graph size but to density, the quality of the initial lower bound, and family-specific topology.
- Four of the five instances were solved to proven optimality with clique sizes matching the published DIMACS optima exactly: C125.9 at 34, brock200_2 at 12, keller4 at 11, and p_hat300-2 at 25. Every returned clique passed an independent pairwise-adjacency check and is published as an explicit vertex list.
- The densest instance, gen200_p0.9_44, exhausted the 300-second budget after exploring 8,268,000 search-tree nodes, returning a valid clique of size 39 against the known optimum of 44, so its optimality is reported as unproven.
- Effort spanned more than three orders of magnitude, from 4,084 nodes and 0.098 seconds on brock200_2 to 8,268,000 nodes on gen200_p0.9_44, and absolute size is plainly the wrong lens: p_hat300-2 has the most vertices (300) and edges (21,928) of the five yet solved in 2.935 seconds.
- The sharpest structural result comes from two instances of identical density 0.90 whose effort differs more than twentyfold. On C125.9 the degeneracy-seeded greedy heuristic landed directly on the optimum of 34, leaving only a proof to complete in 399,900 nodes; on gen200_p0.9_44 the same heuristic reached 33 against an optimum of 44, and that eleven-vertex gap left the search tree open at the cutoff.
- Degeneracy, the size of the densest core a search must traverse, tracks difficulty as a structural proxy: 84 on the easiest instance, brock200_2, rising to 167 on gen200_p0.9_44, whose planted-clique construction is designed to defeat colouring-based pruning.
- Per-node cost is not the bottleneck. Throughput stayed inside a narrow band of roughly 28,000 to 60,000 nodes per second across all five instances, so runtime is essentially node count divided by a fixed cost, and it was the sheer size of the search tree rather than any per-node anomaly that prevented closure.
How it was done
Neighbourhoods were stored as arbitrary-precision-integer bitsets so that candidate intersection, set difference and cardinality each reduce to a single bitwise operation. Before any branching, a degeneracy ordering was computed by repeatedly peeling a minimum-degree vertex through a bucket queue, and a greedy clique built in reverse of that order — front-loading vertices from the densest core — supplied the initial incumbent. At each node a greedy proper colouring of the candidate set produced a per-vertex upper bound, and branching ran from highest colour downward so that the entire remaining prefix could be discarded the moment clique size plus colour number failed to beat the incumbent. Each instance was solved single-threaded under an identical 300-second wall-clock cutoff with the clock polled every 2,000 nodes, and every clique the search returned was re-checked by a separate routine confirming that all pairs of its vertices are adjacent before it was accepted.
Data sources
- Second DIMACS Implementation Challenge, maximum-clique track — C125.9, brock200_2, gen200_p0.9_44, keller4 and p_hat300-2 in standard edge-list format
- Tomita, Sutani, Higashi, Takahashi & Wakatsuki, WALCOM 2010 — the MCS colouring-bounded branch-and-bound algorithm
- Matula & Beck, Journal of the ACM 30:417 (1983) — smallest-last degeneracy ordering
- Hasselberg, Pardalos & Vairaktarakis, Journal of Global Optimization 3:463 (1993) — the planted-clique test-case generators
- Brockington & Culberson (1996) — camouflaging independent sets in quasi-random graphs
- Batsyn, Goldengorin, Maslov & Pardalos, Journal of Combinatorial Optimization 27:397 (2014) — heuristic seeding of MCS
Limitations
The solver is pure Python, so its absolute runtimes sit one to two orders of magnitude below compiled bit-parallel solvers and the particular instance that timed out is implementation-dependent; node counts are the more portable measure of effort. Five instances are also a small sample, so the density-versus-effort trend illustrates well-understood mechanisms rather than establishing a fitted law, and the 300-second cutoff is a policy choice rather than a fundamental barrier.
How this research was produced
K-Dense Web planned and ran this computer science investigation end to end — gathering the sources, carrying out the analysis, producing the figures, and drafting the report. The full session transcript, including every intermediate step, is available to view.
