Efficient branch-and-bound algorithms for finding triangle-constrained 2-clubs

Niels Grüttemeier (), Philipp Heinrich Keßler (), Christian Komusiewicz () and Frank Sommer ()
Additional contact information
Niels Grüttemeier: Fraunhofer IOSB-INA
Philipp Heinrich Keßler: Philipps-Universität Marburg
Christian Komusiewicz: Friedrich-Schiller-Universität Jena
Frank Sommer: TU Wien

Journal of Combinatorial Optimization, 2024, vol. 48, issue 3, No 1, 27 pages

Abstract: Abstract 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 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.

Keywords: Clique relaxation; Branch and bound; NP-hard problem; Data reduction rules (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01204-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:48:y:2024:i:3:d:10.1007_s10878-024-01204-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01204-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().