{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T14:26:34Z","timestamp":1781533594984,"version":"3.54.5"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","funder":[{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"crossref","award":["ANR-17-CE40-0015"],"award-info":[{"award-number":["ANR-17-CE40-0015"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"crossref","award":["ANR-16-CE40-0009"],"award-info":[{"award-number":["ANR-16-CE40-0009"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p xml:lang=\"en\">We prove that, given a closure function the smallest preimage of a closed set can be calculated in polynomial time in the number of closed sets. This implies that there is a polynomial time algorithm to compute the convex hull number of a graph, when all its convex subgraphs are given as input. We then show that deciding if the smallest preimage of a closed set is logarithmic in the size of the ground set is LOGSNP-hard if only the ground set is given. A special instance of this problem is to compute the dimension of a poset given its linear extension graph, that is conjectured to be in P.The intent to show that the latter problem is LOGSNP-complete leads to several interesting questions and to the definition of the isometric hull, i.e., a smallest isometric subgraph containing a given set of vertices $S$. While for $|S|=2$ an isometric hull is just a shortest path, we show that computing the isometric hull of a set of vertices is NP-complete even if $|S|=3$. Finally, we consider the problem of computing the isometric hull number of a graph and show that computing it is $\\Sigma^P_2$ complete.<\/jats:p>","DOI":"10.23638\/dmtcs-21-1-11","type":"journal-article","created":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T12:51:53Z","timestamp":1743684713000},"source":"Crossref","is-referenced-by-count":0,"title":["Computing metric hulls in graphs"],"prefix":"10.23638","volume":"vol. 21 no. 1, ICGT 2018","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8151-2184","authenticated-orcid":false,"given":"Kolja","family":"Knauer","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/0257sgk90","id-type":"ROR","asserted-by":"publisher"}],"name":"Laboratoire d'Informatique et Syst\u00e8mes","acronym":["LIS"]},{"name":"Laboratoire d'Informatique et des Syst\u00e8mes"},{"name":"Laboratoire d'Informatique et des Syst\u00e8mes (LIS) (Marseille, Toulon)"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4500-5078","authenticated-orcid":false,"given":"Nicolas","family":"Nisse","sequence":"additional","affiliation":[{"name":"Combinatorics, Optimization and Algorithms for Telecommunications"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2019,5,23]]},"container-title":["Discrete Mathematics &amp; Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/hal.science\/hal-01612515v4\/document","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/hal.science\/hal-01612515v4\/document","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T12:51:54Z","timestamp":1743684714000},"score":1,"resource":{"primary":{"URL":"http:\/\/dmtcs.episciences.org\/4720"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,23]]},"references-count":0,"URL":"https:\/\/doi.org\/10.23638\/dmtcs-21-1-11","relation":{"has-preprint":[{"id-type":"uri","id":"https:\/\/hal.science\/hal-01612515v3","asserted-by":"subject"},{"id-type":"uri","id":"https:\/\/hal.science\/hal-01612515v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"uri","id":"https:\/\/hal.science\/hal-01612515v4","asserted-by":"subject"}]},"ISSN":["1365-8050"],"issn-type":[{"value":"1365-8050","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,23]]},"article-number":"4720"}}