Split-and-Reduce: A New Exact Algorithm with Tight Multi-Order Intersection Bounds for the Quasi-Clique Enumeration Problem

The quasi-clique enumeration problem (degree-based quasi-cliques) is substantially more challenging than the classical clique problem because quasi-cliques do not satisfy the hereditary property, leading to exponential search spaces even in dense graphs. We introduce the Split-and-Reduce (SR) algorithm, an exact deterministic method that derives a family of tight lower bounds Mₖ (N, r) on k-wise neighbourhood intersections directly from the pigeonhole principle. By integrating critical-chain inclusion theorems, recursive graph decomposition, weakest-first candidate ordering, and dynamically updated upper bounds on the maximum feasible quasi-clique size, SR prunes invalid vertices, pairs, and triplets far earlier than existing methods while remaining completely insensitive to vertex ordering. We prove that SR yields strictly stronger theoretical upper bounds on the maximum quasi-clique size than all previously known results. A single-threaded implementation outperforms the state-of-the-art QUICK algorithm by up to two orders of magnitude with guaranteed completeness and zero false positives. For the first time, SR computes maximum quasi-cliques in graphs containing billions of edges (Friendster, Orkut, DBLP), revealing unexpectedly small stable quasi-clique sizes (<150 vertices even at moderate r) in real-world networks. These advances substantially strengthen the mathematical foundation for exact dense-subgraph enumeration and provide powerful new tools for structural graph theory.