EUVIMEDEUVIMED entdecken
Crossref

Revisiting the Maximum Defective Clique Problem: Faster Branching and a Tighter Upper Bound

Kewu Yang, Kaiqiang Yu, Shengxin Liu, Zhaoquan Gu

Proceedings of the VLDB Endowment · 01.05.2026 · 19 (9) · 2439-2451

DOI: 10.14778/3819518.3819562 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 19.08.2026. Verfasst von Kewu Yang und 3 weiteren Autor:innen. Die Arbeit nennt 55 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The k -defective clique model relaxes the strict completeness constraint of the traditional clique by allowing up to k missing edges, providing a robust formulation for detecting cohesive structures in noisy graphs. Consequently, the maximum k -defective clique problem has attracted significant attention. State-of-the-art exact algorithms predominantly adopt the branch-and-bound framework, which recursively partitions the current problem instance (or branch) into two sub-problems via a branching procedure, until each sub-problem becomes trivially solvable. However, this strategy often leads to excessive branching by overlooking intermediate sub-problems that are non-trivial yet efficiently solvable. While recent studies have attempted to refine branching procedures, they fail to address this structural redundancy. To address this, we propose BBRes, a framework that incorporates a novel early termination strategy into the recursive branching process. By employing a specialized polynomial-time solver to identify and resolve tractable sub-instances, BBRes effectively avoids redundant branching steps. Additionally, we design a tailored branching strategy that synergizes with this termination mechanism. As a result, BBRes achieves an improved theoretical worst-case time complexity. To enhance practical performance, we propose a tighter upper bound based on a novel double graph coloring method integrated with max-flow techniques, which is orthogonal to the branching framework. Extensive experiments show that BBRes achieves at least 2X speedup over state-of-the-art methods on a substantial fraction of the datasets.

Zitieren

APA

Yang, K., Yu, K., Liu, S., & Gu, Z. (2026). Revisiting the Maximum Defective Clique Problem: Faster Branching and a Tighter Upper Bound. Proceedings of the VLDB Endowment, 19(9), 2439-2451. https://doi.org/10.14778/3819518.3819562

Vancouver

Yang K, Yu K, Liu S, Gu Z. Revisiting the Maximum Defective Clique Problem: Faster Branching and a Tighter Upper Bound. Proceedings of the VLDB Endowment. 2026;19(9):2439-2451. doi:10.14778/3819518.3819562

BibTeX
@article{Yang2026,
  author = {Yang, Kewu and Yu, Kaiqiang and Liu, Shengxin and Gu, Zhaoquan},
  title = {Revisiting the Maximum Defective Clique Problem: Faster Branching and a Tighter Upper Bound},
  journal = {Proceedings of the VLDB Endowment},
  year = {2026},
  volume = {19},
  number = {9},
  pages = {2439--2451},
  doi = {10.14778/3819518.3819562}
}
Kostenlos starten →