A Faster Branching Algorithm for the Maximum k-Defective Clique Problem

A k-defective clique of an undirected graph G is a subset of its vertices that induces a nearly complete graph with a maximum of k missing edges. The maximum k-defective clique problem, which asks for the largest k-defective clique from the given graph, is important in many applications, such as social and biological network analysis. In the paper, we propose a new branching algorithm that takes advantage of the structural properties of the k-defective clique and uses the efficient maximum clique algorithm as a subroutine. As a result, the algorithm has a better asymptotic running time than the existing ones. We also investigate upper-bounding techniques and propose a new upper bound utilizing the textitconflict relationship between vertex pairs. Because conflict relationship is common in many graph problems, we believe that this technique can be potentially generalized. Finally, experiments show that our algorithm outperforms state-of-the-art solvers on a wide range of open benchmarks.