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

本文介绍了无向图 $G$ 的 $k$-缺陷团，它是由一组顶点组成的子集，该子集诱导出的几乎完全图最多有 $k$ 条缺失边。最大 $k$-缺陷团问题是指在给定图中寻找最大的 $k$-缺陷团，该问题在社交和生物网络分析等许多应用中都很重要。本文提出了一种新的分支算法，利用 $k$-缺陷团的结构特性，并将高效的最大团算法作为子程序。因此，该算法的渐进运行时间比现有算法更好。我们还研究了上界技术，并提出了一种利用顶点对之间的“冲突关系”作为新上界的方法。由于冲突关系在许多图问题中很常见，我们认为这种技术具有潜在的普适性。最后，实验表明，我们的算法在广泛的开放基准测试中优于现有的解算器。

最大$k$缺失团问题（maximum $k$-defective clique problem）

利用$k$-缺失团的结构特征，结合最大团算法，提出了一种新的分支算法，并且提出了一种新的上界估计方法，利用顶点间的冲突关系。

实验结果表明，该算法在多个数据集上优于现有的解决方案，并且该上界估计方法具有一定的通用性。

最近的相关研究包括：\"A new branch-and-bound algorithm for maximum $k$-clique problem\"、\"An efficient branch-and-bound algorithm for maximum $k$-clique problem\"等。