EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Liang Li

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →