{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:34:09Z","timestamp":1787322849608,"version":"build-2736575974"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["725978"],"award-info":[{"award-number":["725978"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>For a graph [Formula: see text], a subset [Formula: see text] is called a resolving set if for any two vertices [Formula: see text], there exists a vertex [Formula: see text] such that [Formula: see text]. The Metric Dimension problem takes as input a graph [Formula: see text] and a positive integer [Formula: see text], and asks whether there exists a resolving set of size at most [Formula: see text]. This problem was introduced in the 1970s and is known to be NP -hard [M. R. Garey and D. S. Johnson, Computers and Intractability\u2014A Guide to NP-Completeness, Freeman, San Francisco, 1979]. In the realm of parameterized complexity, Hartung and Nichterlein [28 th Conference on Computational Complexity, IEEE, Piscataway, NJ, 2013, pp. 266\u2013276] proved that the problem is W [2]-hard when parameterized by the natural parameter [Formula: see text]. They also observed that it is fixed parameter tractable ( FPT) when parameterized by the vertex cover number and asked about its complexity under smaller parameters, in particular, the feedback vertex set number. We answer this question by proving that Metric Dimension is W [1]-hard when parameterized by the combined parameter feedback vertex set number plus pathwidth. This also improves the result of Bonnet and Purohit [IPEC 2019] which states that the problem is W [1]-hard parameterized by the pathwidth. On the positive side, we show that Metric Dimension is FPT when parameterized by either the distance to cluster or the distance to cocluster, both of which are smaller parameters than the vertex cover number.<\/jats:p>","DOI":"10.1137\/22m1510911","type":"journal-article","created":{"date-parts":[[2023,10,10]],"date-time":"2023-10-10T05:00:30Z","timestamp":1696914030000},"page":"2241-2264","source":"Crossref","is-referenced-by-count":4,"title":["Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters"],"prefix":"10.1137","volume":"37","author":[{"given":"Esther","family":"Galby","sequence":"first","affiliation":[{"name":"Hamburg University of Technology, Institute for Algorithms and Complexity, Hamburg, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Liana","family":"Khazaliya","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Wien, Vienna, Austria."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5634-9506","authenticated-orcid":true,"given":"Fionn","family":"Mc Inerney","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Wien, Vienna, Austria."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roohani","family":"Sharma","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbr\u00fccken, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prafullkumar","family":"Tale","sequence":"additional","affiliation":[{"name":"Indian Institute of Science Education and Research Pune, Pune, India."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,10,10]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1137\/0209018"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2006.884015"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/16M1057383"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2007.12.009"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00707-5"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2020.09.013"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00808-9"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.37236\/7488"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.04.017"},{"key":"ref10","unstructured":"K. Bringmann , \nD. Hermelin , \nM. Mnich , and \nE. J. van Leeuwen  , Parameterized complexity dichotomy for Steiner multicut, in 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), Leibniz International Proceedings in Informatics (LIPIcs) 30, 2015, pp. 157\u2013170."},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00198-0"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.06.006"},{"key":"ref14","series-title":"Grad. Texts in Math. 173","volume-title":"Graph Theory","author":"Diestel R.","year":"2012","edition":"4"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00360"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9896-2"},{"key":"ref17","first-page":"2829","volume":"9","author":"Estrada-Moreno A.","year":"2015","journal-title":"Appl. Math. Inform. Sci."},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1002\/net.21560"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0184-1"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2022.04.021"},{"key":"ref21","unstructured":"E. Galby , \nL. Khazaliya , \nF. Mc Inerney , \nR. Sharma , and \nP. Tale  , Metric dimension parameterized by feedback vertex set and other structural parameters, in 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), LIPIcs. Leibniz Int. Proc. Inform. 241, Wadern, Germany, 2022, 51."},{"key":"ref22","volume-title":"Computers and Intractability\u2014A Guide to NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2022.03.021"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.01.028"},{"key":"ref25","first-page":"191","volume":"2","author":"Harary F.","year":"1976","journal-title":"Ars Combin."},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"S. Hartung  and \nA. Nichterlein  , On the parameterized and approximation hardness of metric dimension, in Proceedings of the 28th Conference on Computational Complexity, CCC, IEEE, Piscataway, NJ, 2013, pp. 266\u2013276.","DOI":"10.1109\/CCC.2013.36"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2017.08.028"},{"key":"ref28","doi-asserted-by":"crossref","first-page":"1130","DOI":"10.1007\/s00453-014-9896-2","volume":"72","author":"Hoffmann S.","year":"2015","journal-title":"Algorithmica"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1080\/10543409308835060"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1109\/18.661507"},{"key":"ref31","unstructured":"D. Kuziak  and \nI. G. Yero  , Metric Dimension Related Parameters in Graphs: A Survey on Combinatorial, Computational and Applied Results, preprint, arXiv:2107.04877, 2021."},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-022-01005-y"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1016\/0734-189X(84)90051-3"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.11.015"},{"key":"ref35","first-page":"549","author":"Slater P. J.","year":"1975","journal-title":"Util. Math."},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230170105"},{"key":"ref37","unstructured":"R. C. Tillquist , \nR. M. Frongillo , and \nM. E. Lladser  , Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications, preprint, arXiv:2104.07201, 2021."},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/s00285-019-01348-1"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30179-0_16"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1510911","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:29:07Z","timestamp":1787318947000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1510911"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,10]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1137\/22M1510911"],"URL":"https:\/\/doi.org\/10.1137\/22m1510911","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,10]]}}}