Revisiting the Maximum Defective Clique Problem: Faster Branching and a Tighter Upper Bound
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.
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}
}
EUVIMED