{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:54Z","timestamp":1740109374906,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,8,12]],"date-time":"2023-08-12T00:00:00Z","timestamp":1691798400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,12]],"date-time":"2023-08-12T00:00:00Z","timestamp":1691798400000},"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"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2023,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The <jats:italic>s<\/jats:italic>-<jats:sc>Club<\/jats:sc> problem asks whether a given undirected graph\u00a0<jats:italic>G<\/jats:italic> contains a vertex set\u00a0<jats:italic>S<\/jats:italic> of size at least <jats:italic>k<\/jats:italic> such that\u00a0<jats:italic>G<\/jats:italic>[<jats:italic>S<\/jats:italic>], the subgraph of\u00a0<jats:italic>G<\/jats:italic> induced by\u00a0<jats:italic>S<\/jats:italic>, has diameter at most\u00a0<jats:italic>s<\/jats:italic>. We consider variants of <jats:italic>s<\/jats:italic>-<jats:sc>Club<\/jats:sc> where one additionally demands that each vertex of\u00a0<jats:italic>G<\/jats:italic>[<jats:italic>S<\/jats:italic>] is contained in at least <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\u00a0<jats:italic>G<\/jats:italic>[<jats:italic>S<\/jats:italic>], that each edge of\u00a0<jats:italic>G<\/jats:italic>[<jats:italic>S<\/jats:italic>] is contained in at least <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\u00a0<jats:italic>G<\/jats:italic>[<jats:italic>S<\/jats:italic>], or that\u00a0<jats:italic>S<\/jats:italic> contains a given set\u00a0<jats:italic>W<\/jats:italic> of seed vertices. We show that in general these variants are W[1]-hard when parameterized by the solution size\u00a0<jats:italic>k<\/jats:italic>, making them significantly harder than the unconstrained\u00a0<jats:italic>s<\/jats:italic>-<jats:sc>Club<\/jats:sc> problem. On the positive side, we obtain some FPT algorithms for the case when\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell =1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u2113<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and for the case when\u00a0<jats:italic>G<\/jats:italic>[<jats:italic>W<\/jats:italic>], the graph induced by the set of seed vertices, is a clique.<\/jats:p>","DOI":"10.1007\/s00224-023-10135-x","type":"journal-article","created":{"date-parts":[[2023,8,12]],"date-time":"2023-08-12T05:01:30Z","timestamp":1691816490000},"page":"1050-1081","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Parameterized Complexity of\u00a0s-Club with Triangle and Seed Constraints"],"prefix":"10.1007","volume":"67","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8762-8567","authenticated-orcid":false,"given":"Jaroslav","family":"Garvardt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0829-7032","authenticated-orcid":false,"given":"Christian","family":"Komusiewicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4034-525X","authenticated-orcid":false,"given":"Frank","family":"Sommer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,8,12]]},"reference":[{"key":"10135_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, M.T., Br\u00e1s, R.: The maximum l-triangle k-club problem: Complexity, properties, and algorithms. Comput. Oper. Res. 111, 258\u2013270 (2019)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"10135_CR2","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.: Novel approaches for analyzing biological networks. J. Comb. Optim. 10(1), 23\u201339 (2005)","journal-title":"J. Comb. Optim."},{"issue":"8","key":"10135_CR3","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10135_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.: An exact algorithm for the maximum $$k$$-club problem in an undirected graph. Eur. J. Oper. Res. 138(1), 21\u201328 (2002)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"10135_CR5","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1007\/s10878-016-0009-9","volume":"33","author":"FD Carvalho","year":"2017","unstructured":"Carvalho, F.D., Almeida, M.T.: The triangle $$k$$-club problem. J. Comb. Optim. 33(3), 814\u2013846 (2017)","journal-title":"J. Comb. Optim."},{"issue":"9","key":"10135_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.: Finding large $$k$$-clubs in undirected graphs. Computing 95(9), 739\u2013758 (2013)","journal-title":"Computing"},{"key":"10135_CR7","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"10135_CR8","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer (2013)","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"10135_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.socnet.2016.01.001","volume":"46","author":"Z Ertem","year":"2016","unstructured":"Ertem, Z., Veremyev, A., Butenko, S.: Detecting large cohesive subgroups with high clustering coefficients in social networks. Soc. Netw. 46, 1\u201310 (2016)","journal-title":"Soc. Netw."},{"key":"10135_CR10","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.dam.2014.04.016","volume":"174","author":"PA Golovach","year":"2014","unstructured":"Golovach, P.A., Heggernes, P., Kratsch, D., Rafiey, A.: Finding clubs in graph classes. Discret. Appl. Math. 174, 57\u201365 (2014)","journal-title":"Discret. Appl. Math."},{"key":"10135_CR11","unstructured":"Gr\u00fcttemeier, N., Ke\u00dfler, P.H., Komusiewicz, C., Sommer, F.: Efficient branch-and-bound algorithms for finding triangle-constrained 2-clubs. CoRR arXiv:2211.01701. https:\/\/doi.org\/10.48550\/arXiv.2211.01701 (2022)"},{"issue":"1","key":"10135_CR12","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.: Parameterized algorithmics and computational experiments for finding 2-clubs. J. Graph. Algorithms Appl. 19(1), 155\u2013190 (2015)","journal-title":"J. Graph. Algorithms Appl."},{"key":"10135_CR13","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.dam.2014.11.026","volume":"185","author":"S Hartung","year":"2015","unstructured":"Hartung, S., Komusiewicz, C., Nichterlein, A., Such\u00fd, O.: On structural parameterizations for the 2-club problem. Discret. Appl. Math. 185, 79\u201392 (2015)","journal-title":"Discret. Appl. Math."},{"key":"10135_CR14","doi-asserted-by":"crossref","unstructured":"Kanawati, R.: Seed-centric approaches for community detection in complex networks. In: Proceedings of the 6th International Conference on Social Computing and Social Media (SCSM\u00a0\u201914), Lecture Notes in Computer Science, vol. 8531, pp. 197\u2013208. Springer (2014)","DOI":"10.1007\/978-3-319-07632-4_19"},{"issue":"1","key":"10135_CR15","doi-asserted-by":"publisher","first-page":"21","DOI":"10.3390\/a9010021","volume":"9","author":"C Komusiewicz","year":"2016","unstructured":"Komusiewicz, C.: Multivariate algorithmics for finding cohesive subnetworks. Algorithms 9(1), 21 (2016)","journal-title":"Algorithms"},{"issue":"3","key":"10135_CR16","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.: Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: Theory and experiments. Eur. J. Oper. Res. 275(3), 846\u2013864 (2019)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"10135_CR17","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF00139635","volume":"13","author":"RJ Mokken","year":"1979","unstructured":"Mokken, R.J., et al.: Cliques, clubs and clans. Qual. Quant. 13(2), 161\u2013173 (1979)","journal-title":"Qual. Quant."},{"issue":"1","key":"10135_CR18","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.: On clique relaxation models in network analysis. Eur. J. Oper. Res. 226(1), 9\u201318 (2013)","journal-title":"Eur. J. Oper. Res."},{"issue":"5","key":"10135_CR19","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.: Parameterized computational complexity of finding small-diameter subgraphs. Optim. Lett. 6(5), 883\u2013891 (2012)","journal-title":"Optim. Lett."},{"issue":"2","key":"10135_CR20","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.: Identifying large robust network clusters via new compact formulations of maximum $$k$$-club problems. Eur. J. Oper. Res. 218(2), 316\u2013326 (2012)","journal-title":"Eur. J. Oper. Res."},{"key":"10135_CR21","doi-asserted-by":"crossref","unstructured":"Whang, J.J., Gleich, D.F., Dhillon, I.S.: Overlapping community detection using seed set expansion. In: Proceedings of the 22nd ACM International Conference on Information and Knowledge Management (CIKM\u00a0\u201913), pp. 2099\u20132108. ACM (2013)","DOI":"10.1145\/2505515.2505535"},{"issue":"2","key":"10135_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, F.M., Butenko, S.: On biconnected and fragile subgraphs of low diameter. Eur. J. Oper. Res. 263(2), 390\u2013400 (2017)","journal-title":"Eur. J. Oper. Res."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10135-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-023-10135-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10135-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,3]],"date-time":"2023-10-03T09:03:30Z","timestamp":1696323810000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-023-10135-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,12]]},"references-count":22,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["10135"],"URL":"https:\/\/doi.org\/10.1007\/s00224-023-10135-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2023,8,12]]},"assertion":[{"value":"8 June 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}