Split-and-Reduce: A New Exact Algorithm with Tight Multi-Order Intersection Bounds for the Quasi-Clique Enumeration Problem
Mathematics · 13.04.2026 · 14 (8) · 1298
DOI: 10.3390/math14081298 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics, online erschienen am 13.04.2026. Verfasst von Liang Li. Die Arbeit nennt 43 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
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_k(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 (
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Li, L. (2026). Split-and-Reduce: A New Exact Algorithm with Tight Multi-Order Intersection Bounds for the Quasi-Clique Enumeration Problem. Mathematics, 14(8), 1298. https://doi.org/10.3390/math14081298
Vancouver
Li L. Split-and-Reduce: A New Exact Algorithm with Tight Multi-Order Intersection Bounds for the Quasi-Clique Enumeration Problem. Mathematics. 2026;14(8):1298. doi:10.3390/math14081298
BibTeX
@article{Li2026,
author = {Li, Liang},
title = {Split-and-Reduce: A New Exact Algorithm with Tight Multi-Order Intersection Bounds for the Quasi-Clique Enumeration Problem},
journal = {Mathematics},
year = {2026},
volume = {14},
number = {8},
pages = {1298},
doi = {10.3390/math14081298}
}
EUVIMED