CC BY 4.0Grüttemeier, NielsNielsGrüttemeierKeßler, Philipp HeinrichPhilipp HeinrichKeßlerKomusiewicz, ChristianChristianKomusiewiczSommer, FrankFrankSommer2024-10-312024-10-312024https://publica.fraunhofer.de/handle/publica/478239https://doi.org/10.24406/h-47823910.1007/s10878-024-01204-z10.24406/h-478239In 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 triangles in the subgraph. So far, the only algorithm for solving Vertex Triangle 2-Club relies on an ILP formulation (Almeida and Brás in Comput Oper Res 111:258-270, 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.enClique relaxationBranch and boundNP-hard problemData reduction rulesOAjournal article