{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:52Z","timestamp":1740122392270,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T00:00:00Z","timestamp":1726876800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T00:00:00Z","timestamp":1726876800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["EAGR (KO 3669\/6-1)"],"award-info":[{"award-number":["EAGR (KO 3669\/6-1)"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"TU Wien"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the <jats:sc>Vertex Triangle 2-Club<\/jats:sc> problem, we are given an undirected graph\u00a0<jats:italic>G<\/jats:italic> and aim to find a maximum-vertex subgraph of\u00a0<jats:italic>G<\/jats:italic> that has diameter at most\u00a02 and in which every vertex is contained in at least\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u2113<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u00a0triangles in the subgraph. So far, the only algorithm for solving <jats:sc>Vertex Triangle 2-Club<\/jats:sc> relies on an ILP formulation (Almeida and Br\u00e1s in Comput Oper Res 111:258\u2013270, 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 <jats:sc>Edge Triangle 2-Club<\/jats:sc> problem where the triangle constraint is imposed on all edges of the subgraph.<\/jats:p>","DOI":"10.1007\/s10878-024-01204-z","type":"journal-article","created":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T21:01:29Z","timestamp":1726952489000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient branch-and-bound algorithms for finding triangle-constrained 2-clubs"],"prefix":"10.1007","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6789-2918","authenticated-orcid":false,"given":"Niels","family":"Gr\u00fcttemeier","sequence":"first","affiliation":[]},{"given":"Philipp Heinrich","family":"Ke\u00dfler","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0829-7032","authenticated-orcid":false,"given":"Christian","family":"Komusiewicz","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4034-525X","authenticated-orcid":false,"given":"Frank","family":"Sommer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,21]]},"reference":[{"key":"1204_CR1","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/j.cor.2019.07.003","volume":"111","author":"MT Almeida","year":"2019","unstructured":"Almeida MT, Br\u00e1s R (2019) The maximum l-triangle k-club problem: complexity, properties, and algorithms. Comput Oper Res 111:258\u2013270","journal-title":"Comput Oper Res"},{"key":"1204_CR2","doi-asserted-by":"crossref","unstructured":"Bader DA, Kappes A, Meyerhenke H, Sanders P, Schulz C, Wagner D (2014) Benchmarking for graph clustering and partitioning. In: Encyclopedia of Social Network Analysis and Mining. Springer, pp 73\u201382","DOI":"10.1007\/978-1-4614-6170-8_23"},{"issue":"1","key":"1204_CR3","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/s10878-005-1857-x","volume":"10","author":"B Balasundaram","year":"2005","unstructured":"Balasundaram B, Butenko S, Trukhanov S (2005) Novel approaches for analyzing biological networks. J Comb Optim 10(1):23\u201339","journal-title":"J Comb Optim"},{"issue":"1","key":"1204_CR4","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0377-2217(01)00133-3","volume":"138","author":"J Bourjolly","year":"2002","unstructured":"Bourjolly J, Laporte G, Pesant G (2002) An exact algorithm for the maximum $$k$$-club problem in an undirected graph. Eur J Oper Res 138(1):21\u201328","journal-title":"Eur J Oper Res"},{"issue":"3","key":"1204_CR5","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1007\/s10878-016-0009-9","volume":"33","author":"FD Carvalho","year":"2017","unstructured":"Carvalho FD, Almeida MT (2017) The triangle $$k$$-club problem. J Comb Optim 33(3):814\u2013846","journal-title":"J Comb Optim"},{"issue":"9","key":"1204_CR6","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1007\/s00607-012-0263-3","volume":"95","author":"M Chang","year":"2013","unstructured":"Chang M, Hung L, Lin C, Su P (2013) Finding large $$k$$-clubs in undirected graphs. Computing 95(9):739\u2013758","journal-title":"Computing"},{"issue":"1","key":"1204_CR7","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/0214017","volume":"14","author":"N Chiba","year":"1985","unstructured":"Chiba N, Nishizeki T (1985) Arboricity and subgraph listing algorithms. SIAM J Comput 14(1):210\u2013223","journal-title":"SIAM J Comput"},{"issue":"5","key":"1204_CR8","doi-asserted-by":"publisher","first-page":"1050","DOI":"10.1007\/s00224-023-10135-x","volume":"67","author":"J Garvardt","year":"2023","unstructured":"Garvardt J, Komusiewicz C, Sommer F (2023) The parameterized complexity of $$s$$-club with triangle and seed constraints. Theory Comput Syst 67(5):1050\u20131081","journal-title":"Theory Comput Syst"},{"issue":"1","key":"1204_CR9","doi-asserted-by":"publisher","first-page":"155","DOI":"10.7155\/jgaa.00352","volume":"19","author":"S Hartung","year":"2015","unstructured":"Hartung S, Komusiewicz C, Nichterlein A (2015) Parameterized algorithmics and computational experiments for finding 2-clubs. J Graph Algor Appl 19(1):155\u2013190","journal-title":"J Graph Algor Appl"},{"key":"1204_CR10","unstructured":"Ke\u00dfler PH (2020). Algorithm engineering for the triangle-$$2$$-club problem. Bachelor\u2019s thesis, Philipps-Universit\u00e4t Marburg. https:\/\/www.uni-marburg.de\/de\/fb12\/arbeitsgruppen\/algorith\/paper\/philipp_kessler_bachelor-thesis.pdf"},{"issue":"3","key":"1204_CR11","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1016\/j.ejor.2018.12.006","volume":"275","author":"C Komusiewicz","year":"2019","unstructured":"Komusiewicz C, Nichterlein A, Niedermeier R, Picker M (2019) Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments. Eur J Oper Res 275(3):846\u2013864","journal-title":"Eur J Oper Res"},{"key":"1204_CR12","doi-asserted-by":"crossref","unstructured":"Kunegis J (2013). KONECT: the Koblenz network collection. In: Proceedings of the 22nd International World Wide Web Conference (WWW\u00a0\u201913). International World Wide Web Conferences Steering Committee\/ACM, pp 1343\u20131350","DOI":"10.1145\/2487788.2488173"},{"issue":"6","key":"1204_CR13","doi-asserted-by":"publisher","first-page":"3181","DOI":"10.1287\/ijoc.2022.1231","volume":"34","author":"Y Lu","year":"2022","unstructured":"Lu Y, Salemi H, Balasundaram B, Buchanan A (2022) On fault-tolerant low-diameter clusters in graphs. INFORMS J Comput 34(6):3181\u20133199. https:\/\/doi.org\/10.1287\/ijoc.2022.1231","journal-title":"INFORMS J Comput"},{"issue":"2","key":"1204_CR14","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF00139635","volume":"13","author":"RJ Mokken","year":"1979","unstructured":"Mokken RJ (1979) Cliques, clubs and clans. Quality Quantity 13(2):161\u2013173","journal-title":"Quality Quantity"},{"issue":"6","key":"1204_CR15","doi-asserted-by":"publisher","first-page":"1466","DOI":"10.1287\/opre.2016.1500","volume":"64","author":"FM Pajouh","year":"2016","unstructured":"Pajouh FM, Balasundaram B, Hicks IV (2016) On the 2-club polytope of graphs. Oper Res 64(6):1466\u20131481","journal-title":"Oper Res"},{"issue":"1\u20132","key":"1204_CR16","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s10479-016-2279-0","volume":"249","author":"FM Pajouh","year":"2017","unstructured":"Pajouh FM, Moradi E, Balasundaram B (2017) Detecting large risk-averse 2-clubs in graphs with random edge failures. Ann Oper Res 249(1\u20132):55\u201373","journal-title":"Ann Oper Res"},{"issue":"1","key":"1204_CR17","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.ejor.2012.10.021","volume":"226","author":"J Pattillo","year":"2013","unstructured":"Pattillo J, Youssef N, Butenko S (2013) On clique relaxation models in network analysis. Eur J Oper Res 226(1):9\u201318","journal-title":"Eur J Oper Res"},{"key":"1204_CR18","doi-asserted-by":"crossref","unstructured":"Rossi RA, Ahmed NK (2015). The network data repository with interactive graph analytics and visualization. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI\u00a0\u201915). AAAI Press, , pp 4292\u20134293. http:\/\/networkrepository.com","DOI":"10.1609\/aaai.v29i1.9277"},{"issue":"3","key":"1204_CR19","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s12532-020-00175-6","volume":"12","author":"H Salemi","year":"2020","unstructured":"Salemi H, Buchanan A (2020) Parsimonious formulations for low-diameter clusters. Math Program Comput 12(3):493\u2013528","journal-title":"Math Program Comput"},{"issue":"5","key":"1204_CR20","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/s11590-011-0311-5","volume":"6","author":"A Sch\u00e4fer","year":"2012","unstructured":"Sch\u00e4fer A, Komusiewicz C, Moser H, Niedermeier R (2012) Parameterized computational complexity of finding small-diameter subgraphs. Optim Lett 6(5):883\u2013891","journal-title":"Optim Lett"},{"issue":"2","key":"1204_CR21","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1016\/j.ejor.2011.10.027","volume":"218","author":"A Veremyev","year":"2012","unstructured":"Veremyev A, Boginski V (2012) Identifying large robust network clusters via new compact formulations of maximum $$k$$-club problems. Eur J Oper Res 218(2):316\u2013326","journal-title":"Eur J Oper Res"},{"issue":"2","key":"1204_CR22","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1016\/j.ejor.2017.05.020","volume":"263","author":"O Yezerska","year":"2017","unstructured":"Yezerska O, Pajouh FM, Butenko S (2017) On biconnected and fragile subgraphs of low diameter. Eur J Oper Res 263(2):390\u2013400","journal-title":"Eur J Oper Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01204-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01204-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01204-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T19:09:12Z","timestamp":1729192152000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01204-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,21]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["1204"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01204-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,9,21]]},"assertion":[{"value":"24 May 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors do not have any competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"16"}}