论文标题
有效的分支和结合算法，用于查找三角形约束的2俱乐部
Efficient Branch-and-Bound Algorithms for Finding Triangle-Constrained 2-Clubs
论文作者
论文摘要
在顶点三角2俱乐部问题中，我们获得了一个无向图$ g $，旨在找到最多具有直径为2的$ g $的最大vertex子图，并且每个顶点至少包含在该子级别中的$ \ ell $ triangles中。到目前为止，解决顶点三角2俱乐部的唯一算法依赖于ILP公式[Almeida和Brás，Comput。操作。 res。 2019]。在这项工作中，我们开发了一种组合分支和结合算法，再加上一组数据减少规则，优于现有实现，并能够在几分钟内具有超过100,000个顶点的稀疏现实图形上找到最佳解决方案。我们还将我们的算法扩展到边缘三角2俱乐部问题，其中三角限制在子图的所有边缘都施加。
In the Vertex Triangle 2-Club problem, we are given an undirected graph $G$ and aim to find a maximum-vertex subgraph of $G$ that has diameter at most 2 and in which every vertex is contained in at least $\ell$ triangles in the subgraph. So far, the only algorithm for solving Vertex Triangle 2-Club relies on an ILP formulation [Almeida and Brás, Comput. Oper. Res. 2019]. In this work, we develop a combinatorial branch-and-bound algorithm that, coupled with a set of data reduction rules, outperforms the existing implementation and is able to find optimal solutions on sparse real-world graphs with more than 100,000 vertices in a few minutes. We also extend our algorithm to the Edge Triangle 2-Club problem where the triangle constraint is imposed on all edges of the subgraph.
