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\'as, 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.
翻译:在 Vertex 三角 2- Club 问题中, 我们得到一个未引导的图形 $G$, 目的是找到一个最大顶端 $G$ 的子集, 其直径最多为 2, 并且每个顶端都包含在 Subgraph 的至少$\ ell $ 的三角中。 到目前为止, 解决 Vertex 三角 2 - Club 的唯一算法依赖于 ILP 配方 [Almeida and Br\'as, Comput. Oper. Res. 2019] 。 在这项工作中, 我们开发了一个组合式分支和约束式算法, 加上一套数据减少规则, 超越了现有的执行功能, 并且能够在几分钟内找到 10万 以上 的原始世界图形上找到最佳的解决方案 。 我们还将我们的算法扩大到 Edge 三角 2- Club 问题, 在那里对子图的所有边缘都施加三角约束 。