A Faster Branching Algorithm for the Maximum $k$-Defective Clique Problem
<|reference_start|>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 \textit{conflict 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.<|reference_end|>
@article{luo2024a,
    title={A Faster Branching Algorithm for the Maximum $k$-Defective Clique
  Problem},
    author={Chunyu Luo, Yi Zhou, Zhengren Wang, Mingyu Xiao},
    journal={arXiv preprint arXiv:2407.16588},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.16588},
    primaryClass={cs.DS cs.AI}
}