{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T23:33:07Z","timestamp":1777591987836,"version":"3.51.4"},"reference-count":37,"publisher":"EDP Sciences","issue":"5","license":[{"start":{"date-parts":[[2024,9,24]],"date-time":"2024-09-24T00:00:00Z","timestamp":1727136000000},"content-version":"vor","delay-in-days":23,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["001"],"award-info":[{"award-number":["001"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["001"],"award-info":[{"award-number":["001"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004901","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de Minas Gerais","doi-asserted-by":"publisher","award":["APQ-01707-21"],"award-info":[{"award-number":["APQ-01707-21"]}],"id":[{"id":"10.13039\/501100004901","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["312069\/2021-9"],"award-info":[{"award-number":["312069\/2021-9"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["406036\/2021-7"],"award-info":[{"award-number":["406036\/2021-7"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["404479\/2023-5"],"award-info":[{"award-number":["404479\/2023-5"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2024,5,30]]},"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:p>A strong geodetic set of a graph <jats:italic>G<\/jats:italic> = (<jats:italic>V, E<\/jats:italic>) is a vertex set <jats:italic>S<\/jats:italic> <jats:italic>\u2286<\/jats:italic> <jats:italic>V<\/jats:italic> (<jats:italic>G<\/jats:italic>) in which it is possible to cover all the remaining vertices of <jats:italic>V<\/jats:italic> (<jats:italic>G<\/jats:italic>) <jats:italic>\u2216<\/jats:italic> <jats:italic>S<\/jats:italic> by assigning a unique shortest path between each vertex pair of <jats:italic>S<\/jats:italic>. In the Strong Geodetic problem (SG) a graph <jats:italic>G<\/jats:italic> and a positive integer <jats:italic>k<\/jats:italic> are given as input and one has to decide whether <jats:italic>G<\/jats:italic> has a strong geodetic set of cardinality at most <jats:italic>k<\/jats:italic>. This problem is known to be NP-hard for general graphs. In this work we introduce the Strong Geodetic Recognition problem (SGR), which consists in determining whether a given vertex set <jats:italic>S<\/jats:italic> <jats:italic>\u2286<\/jats:italic> <jats:italic>V<\/jats:italic> (<jats:italic>G<\/jats:italic>) is strong geodetic. We demonstrate that this version is NP-complete. We investigate and compare the computational complexity of both decision problems restricted to some graph classes, deriving polynomial-time algorithms, NP-completeness proofs, and initial parameterized complexity results, including an answer to an open question in the literature for the complexity of SG for chordal graphs.<\/jats:p>","DOI":"10.1051\/ro\/2024120","type":"journal-article","created":{"date-parts":[[2024,6,4]],"date-time":"2024-06-04T19:23:41Z","timestamp":1717529021000},"page":"3755-3770","source":"Crossref","is-referenced-by-count":2,"title":["On the computational complexity of the strong geodetic recognition problem"],"prefix":"10.1051","volume":"58","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6666-0533","authenticated-orcid":false,"given":"Carlos V.G.C.","family":"Lima","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4608-4559","authenticated-orcid":false,"given":"Vinicius F.","family":"dos Santos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jo\u00e3ao H.G.","family":"Sousa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebasti\u00e1n A.","family":"Urrutia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2024,9,24]]},"reference":[{"key":"R1","first-page":"1","volume":"1","author":"Alom","year":"2010","journal-title":"DUET J."},{"key":"R2","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1080\/00207160210954","volume":"79","author":"Atici","year":"2002","journal-title":"Int. J. Comput. Math."},{"key":"R3","doi-asserted-by":"crossref","first-page":"853","DOI":"10.1080\/0020716031000103376","volume":"80","author":"Atici","year":"2003","journal-title":"Int. J. Comput. Math."},{"key":"R4","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/j.dam.2009.09.024","volume":"158","author":"Behtoei","year":"2010","journal-title":"Discrete Appl. Math."},{"key":"R5","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0020-0190(84)90126-1","volume":"19","author":"Bertossi","year":"1984","journal-title":"Inf. Process. Lett."},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Blokhuis A. and Brouwer A.E., Geodetic graphs of diameter two, edited by Aschbacher M., Cohen A.M. and Kantor W. M.. In: Geometries and Groups. Dordrecht, Springer Netherlands (1988) 527-533.","DOI":"10.1007\/978-94-009-4017-8_20"},{"key":"R7","doi-asserted-by":"crossref","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"Bodlaender","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"R8","doi-asserted-by":"crossref","first-page":"5555","DOI":"10.1016\/j.disc.2007.10.007","volume":"308","author":"Brear","year":"2008","journal-title":"Discrete Math"},{"key":"R9","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.ipl.2018.02.012","volume":"135","author":"Bueno","year":"2018","journal-title":"Inf. Process. Lett."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Cao J., Wu B. and Shi M., The geodetic number of Cm \u00d7 Cn. In: International Conference on Management and Service Science (MASS\u201909) (2009) 1\u20133.","DOI":"10.1109\/ICMSS.2009.5304507"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Cygan M., Fomin F.V., Kowalik L., Lokshtanov D., Marx D., Pilipczuk M., Pilipczuk M. and Saurabh S., Parameterized Algorithms. Springer (2015).","DOI":"10.1007\/978-3-319-21275-3"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Davot T., Isenmann L. and Thiebaut J., On the approximation hardness of geodetic set and its variants. In: Computing and Combinatorics: 27th International Conference, COCOON 2021, Tainan, Taiwan, October 24\u201326, 2021, Proceedings 27. Springer (2021) 76\u201388.","DOI":"10.1007\/978-3-030-89543-3_7"},{"key":"R13","unstructured":"de Sousa J.H.G., Exact algorithms and computational complexity for the strong geodetic set problem, Master\u2019s thesis, Universidade Federal de Minas Gerais (2018)."},{"key":"R14","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1016\/j.disc.2009.09.018","volume":"310","author":"Dourado","year":"2010","journal-title":"Discrete Math."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Downey R.G. and Fellows M.R., Parameterized Complexity. Springer Science & Business Media (2012).","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"Downey R.G. and Fellows M.R., Fundamentals of Parameterized Complexity. Texts in Computer Science, Springer (2013).","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"R17","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1051\/ro\/2014019","volume":"48","author":"Ekim","year":"2014","journal-title":"RAIRO:RO"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"Ekim T., Erey A., Heggernes P., van \u2019t Hof P. and Meister D., Computing minimum geodetic sets of proper interval graphs, edited by Fern\u00b4andez-Baca D.. In: LATIN 2012: Theoretical Informatics. Berlin, Heidelberg, Springer (2012) 279\u2013290.","DOI":"10.1007\/978-3-642-29344-3_24"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Fellows M.R., Jafke L., Kir\u00b4aly A.I., Rosamond F.A. and Weller M., What Is Known About Vertex Cover Kernelization?. Springer International Publishing, Cham (2018) 330\u2013356.","DOI":"10.1007\/978-3-319-98355-4_19"},{"key":"R20","unstructured":"Fitzpatrick S.L., Aspects of domination and dynamic domination, Ph.D. thesis, Dalhousie University (1997)."},{"key":"R21","doi-asserted-by":"crossref","first-page":"2757","DOI":"10.1007\/s40840-019-00833-6","volume":"43","author":"Gledel","year":"2020","journal-title":"Bull. Malays. Math. Sci. Soc."},{"key":"R22","first-page":"124609","volume":"363","author":"Gledel","year":"2019","journal-title":"Appl. Math. Comput."},{"key":"R23","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0895-7177(93)90259-2","volume":"17","author":"Harary","year":"1993","journal-title":"Math. Comput. Model."},{"key":"R24","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/j.disc.2004.08.039","volume":"293","author":"Hernando","year":"2005","journal-title":"Discrete Math."},{"key":"R25","doi-asserted-by":"crossref","first-page":"2134","DOI":"10.1016\/j.disc.2008.04.034","volume":"309","author":"Hung","year":"2009","journal-title":"Discrete Math."},{"key":"R26","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/s00373-018-1885-9","volume":"34","author":"Ir\u0161i\u010d","year":"2018","journal-title":"Graphs Combin."},{"key":"R27","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1051\/ro\/2018003","volume":"52","author":"Ir\u0161i\u010d","year":"2018","journal-title":"RAIRO:RO"},{"key":"R28","doi-asserted-by":"crossref","first-page":"481","DOI":"10.26493\/1855-3974.1725.2e5","volume":"17","author":"Ir\u0161i\u010d","year":"2019","journal-title":"Ars Math. Contemp."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"Karp R.M., Reducibility among Combinatorial Problems. Springer US, Boston, MA (1972) 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R30","doi-asserted-by":"crossref","first-page":"1671","DOI":"10.1007\/s40840-018-0609-x","volume":"41","author":"Klav\u017ear","year":"2018","journal-title":"Bull. Malays. Math. Sci. Soc."},{"key":"R31","doi-asserted-by":"crossref","first-page":"307","DOI":"10.7151\/dmgt.2139","volume":"40","author":"Manuel","year":"2020","journal-title":"Discuss. Math. Graph Theory"},{"key":"R32","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1023\/A:1021715219620","volume":"52","author":"Nebesky`","year":"2002","journal-title":"Czech. Math. J."},{"key":"R33","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1145\/254180.254190","volume":"29","author":"Paschos","year":"1997","journal-title":"ACM Comput. Surv."},{"key":"R34","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/0095-8956(84)90034-0","volume":"36","author":"Plesn\u00b4\u0131k","year":"1984","journal-title":"J. Combin. Theory Ser. B"},{"key":"R35","doi-asserted-by":"crossref","first-page":"1571","DOI":"10.1016\/j.dam.2008.06.005","volume":"157","author":"Santhakumaran","year":"2009","journal-title":"Discrete Appl. Math."},{"key":"R36","doi-asserted-by":"crossref","unstructured":"Schaefer T.J., The complexity of satisfability problems. In: Proceedings of the tenth annual ACM symposium on Theory of computing. ACM (1978) 216\u2013226.","DOI":"10.1145\/800133.804350"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"Wang Z., Mao Y., Ge H. and Magnant C., Strong geodetic number of graphs and connectivity. Bull. Malays. Math. Sci. Soc. (2019) 1\u201311.","DOI":"10.1007\/s40840-019-00809-6"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024120\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,24]],"date-time":"2024-09-24T08:00:44Z","timestamp":1727164844000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024120"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9]]},"references-count":37,"journal-issue":{"issue":"5"},"alternative-id":["ro230151"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2024120","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"2804-7303","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9]]}}}