Speaker:

Chunyu Luo (University of Electronic Science and Technology of China)

Time:

• 16:20-17:20 (Time in Beijing)
• November 1, 2024 (Friday)

Venue:

518, Research Building 4

Abstract:

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 conflict relationship between vertex pairs. Because the 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. Our source code, as well as the experiment data, is open source and available https://github.com/cy-Luo000/Maximum-k-Defective-Clique.git