  The Maximum k-Defective Clique Problem (MDCP) aims to find a maximum
k-defective clique in a given graph, where a k-defective clique is a relaxation
clique missing at most k edges. MDCP is NP-hard and finds many real-world
applications in analyzing dense but not necessarily complete subgraphs. Exact
algorithms for MDCP mainly follow the Branch-and-bound (BnB) framework, whose
performance heavily depends on the quality of the upper bound on the
cardinality of a maximum k-defective clique. The state-of-the-art BnB MDCP
algorithms calculate the upper bound quickly but conservatively as they ignore
many possible missing edges. In this paper, we propose a novel CoLoring-based
Upper Bound (CLUB) that uses graph coloring techniques to detect independent
sets so as to detect missing edges ignored by the previous methods. We then
develop a new BnB algorithm for MDCP, called KD-Club, using CLUB in both the
preprocessing stage for graph reduction and the BnB searching process for
branch pruning. Extensive experiments show that KD-Club significantly
outperforms state-of-the-art BnB MDCP algorithms on the number of solved
instances within the cut-off time, having much smaller search tree and shorter
solving time on various benchmarks.
