{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T15:29:04Z","timestamp":1772033344146,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,2,23]],"date-time":"2021-02-23T00:00:00Z","timestamp":1614038400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,2,23]],"date-time":"2021-02-23T00:00:00Z","timestamp":1614038400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of Bergen"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,8]]},"abstract":"Abstract<\/jats:title>A resolving set S<\/jats:italic> of a graph G<\/jats:italic> is a subset of its vertices such that no two vertices of G<\/jats:italic> have the same distance vector to S<\/jats:italic>. The Metric Dimension<\/jats:sc> problem asks for a resolving set of minimum size, and in its decision form, a resolving set of size at most some specified integer. This problem is NP-complete, and remains so in very restricted classes of graphs. It is also W[2]-complete with respect to the size of the solution. Metric Dimension<\/jats:sc> has proven elusive on graphs of bounded treewidth. On the algorithmic side, a polynomial time algorithm is known for trees, and even for outerplanar graphs, but the general case of treewidth at most two is open. On the complexity side, no parameterized hardness is known. This has led several papers on the topic to ask for the parameterized complexity of Metric Dimension<\/jats:sc> with respect to treewidth. We provide a first answer to the question. We show that Metric Dimension<\/jats:sc> parameterized by the treewidth of the input graph is W[1]-hard. More refinedly we prove that, unless the Exponential Time Hypothesis fails, there is no algorithm solving Metric Dimension<\/jats:sc> in time $$f(\\text {pw})n^{o(\\text {pw})}$$<\/jats:tex-math>\n \n f<\/mml:mi>\n \n (<\/mml:mo>\n pw<\/mml:mtext>\n )<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n \n o<\/mml:mi>\n (<\/mml:mo>\n pw<\/mml:mtext>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> on n<\/jats:italic>-vertex graphs of constant degree, with $$\\text {pw}$$<\/jats:tex-math>\n pw<\/mml:mtext>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> the pathwidth of the input graph, and f<\/jats:italic> any computable function. This is in stark contrast with an FPT algorithm of Belmonte et al. (SIAM J Discrete Math 31(2):1217\u20131243, 2017) with respect to the combined parameter $$\\text {tl}+\\Delta$$<\/jats:tex-math>\n \n tl<\/mml:mtext>\n +<\/mml:mo>\n \u0394<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where $$\\text {tl}$$<\/jats:tex-math>\n tl<\/mml:mtext>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the tree-length and $$\\Delta$$<\/jats:tex-math>\n \u0394<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> the maximum-degree of the input graph.<\/jats:p>","DOI":"10.1007\/s00453-021-00808-9","type":"journal-article","created":{"date-parts":[[2021,2,23]],"date-time":"2021-02-23T07:03:15Z","timestamp":1614063795000},"page":"2606-2633","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Metric Dimension Parameterized By Treewidth"],"prefix":"10.1007","volume":"83","author":[{"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4869-0031","authenticated-orcid":false,"given":"Nidhi","family":"Purohit","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,23]]},"reference":[{"key":"808_CR1","doi-asserted-by":"publisher","unstructured":"Barbero, F., Isenmann, L., Thiebaut, J.: On the distance identifying set meta-problem and applications to the complexity of identifying problems on graphs. In: 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, August 20\u201324, 2018, Helsinki, Finland, pp. 10:1\u201310:14 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2018.10","DOI":"10.4230\/LIPIcs.IPEC.2018.10"},{"issue":"12","key":"808_CR2","doi-asserted-by":"publisher","first-page":"2168","DOI":"10.1109\/JSAC.2006.884015","volume":"24","author":"Z Beerliova","year":"2006","unstructured":"Beerliova, Z., Eberhard, F., Erlebach, T., Hall, A., Hoffmann, M., Mihal\u00e1k, M., Ram, L.S.: Network discovery and verification. IEEE J. Sel. Areas Commun. 24(12), 2168\u20132181 (2006). https:\/\/doi.org\/10.1109\/JSAC.2006.884015","journal-title":"IEEE J. Sel. Areas Commun."},{"issue":"2","key":"808_CR3","doi-asserted-by":"publisher","first-page":"1217","DOI":"10.1137\/16M1057383","volume":"31","author":"R Belmonte","year":"2017","unstructured":"Belmonte, R., Fomin, F.V., Golovach, P.A., Ramanujan, M.S.: Metric dimension of bounded tree-length graphs. SIAM J. Discrete Math. 31(2), 1217\u20131243 (2017). https:\/\/doi.org\/10.1137\/16M1057383","journal-title":"SIAM J. Discrete Math."},{"issue":"1\u20133","key":"808_CR4","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0166-218X(00)00198-0","volume":"105","author":"G Chartrand","year":"2000","unstructured":"Chartrand, G., Eroh, L., Johnson, M.A., Oellermann, O.: Resolvability in graphs and the metric dimension of a graph. Discrete Appl. Math. 105(1\u20133), 99\u2013113 (2000). https:\/\/doi.org\/10.1016\/S0166-218X(00)00198-0","journal-title":"Discrete Appl. Math."},{"key":"808_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"issue":"1","key":"808_CR6","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.jcss.2016.06.006","volume":"83","author":"J D\u00edaz","year":"2017","unstructured":"D\u00edaz, J., Pottonen, O., Serna, M.J., van Leeuwen, E.J.: Complexity of metric dimension on planar graphs. J. Comput. Syst. Sci. 83(1), 132\u2013158 (2017). https:\/\/doi.org\/10.1016\/j.jcss.2016.06.006","journal-title":"J. Comput. Syst. Sci."},{"key":"808_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"issue":"1","key":"808_CR8","doi-asserted-by":"publisher","first-page":"313","DOI":"10.7155\/jgaa.00360","volume":"19","author":"D Eppstein","year":"2015","unstructured":"Eppstein, D.: Metric dimension parameterized by max leaf number. J. Graph. Algorithms Appl. 19(1), 313\u2013323 (2015). https:\/\/doi.org\/10.7155\/jgaa.00360","journal-title":"J. Graph. Algorithms Appl."},{"issue":"4","key":"808_CR9","doi-asserted-by":"publisher","first-page":"1130","DOI":"10.1007\/s00453-014-9896-2","volume":"72","author":"L Epstein","year":"2015","unstructured":"Epstein, L., Levin, A., Woeginger, G.J.: The (weighted) metric dimension of graphs: hard and easy cases. Algorithmica 72(4), 1130\u20131171 (2015). https:\/\/doi.org\/10.1007\/s00453-014-9896-2","journal-title":"Algorithmica"},{"issue":"9","key":"808_CR10","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/j.ipl.2015.04.006","volume":"115","author":"H Fernau","year":"2015","unstructured":"Fernau, H., Heggernes, P., van\u2019t Hof, P., Meister, D., Saei, R.: Computing the metric dimension for chain graphs. Inf. Process. Lett. 115(9), 671\u2013676 (2015). https:\/\/doi.org\/10.1016\/j.ipl.2015.04.006","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"808_CR11","doi-asserted-by":"publisher","first-page":"914","DOI":"10.1007\/s00453-016-0184-1","volume":"78","author":"F Foucaud","year":"2017","unstructured":"Foucaud, F., Mertzios, G.B., Naserasr, R., Parreau, A., Valicov, P.: Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. Algorithmica 78(3), 914\u2013944 (2017). https:\/\/doi.org\/10.1007\/s00453-016-0184-1","journal-title":"Algorithmica"},{"key":"808_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"issue":"191\u2013195","key":"808_CR13","first-page":"1","volume":"2","author":"F Harary","year":"1976","unstructured":"Harary, F., Melter, R.A.: On the metric dimension of a graph. Ars Combin. 2(191\u2013195), 1 (1976)","journal-title":"Ars Combin."},{"key":"808_CR14","doi-asserted-by":"publisher","unstructured":"Hartung, S., Nichterlein, A.: On the parameterized and approximation hardness of metric dimension. In: Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K. lo Alto, California, USA, 5\u20137 June, 2013, pp. 266\u2013276 (2013) https:\/\/doi.org\/10.1109\/CCC.2013.36","DOI":"10.1109\/CCC.2013.36"},{"key":"808_CR15","doi-asserted-by":"publisher","unstructured":"Hoffmann, S., Wanke, E.: Metric dimension for Gabriel unit disk graphs is NP-complete. In: Algorithms for Sensor Systems, 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2012, Ljubljana, Slovenia, September 13\u201314, 2012. Revised Selected Papers, pp. 90\u201392 (2012). https:\/\/doi.org\/10.1007\/978-3-642-36092-3_10","DOI":"10.1007\/978-3-642-36092-3_10"},{"key":"808_CR16","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.tcs.2016.03.024","volume":"630","author":"S Hoffmann","year":"2016","unstructured":"Hoffmann, S., Elterman, A., Wanke, E.: A linear time algorithm for metric dimension of cactus block graphs. Theor. Comput. Sci. 630, 43\u201362 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2016.03.024","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"808_CR17","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"808_CR18","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/0166-218X(95)00106-2","volume":"70","author":"S Khuller","year":"1996","unstructured":"Khuller, S., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs. Discrete Appl. Math. 70(3), 217\u2013229 (1996). https:\/\/doi.org\/10.1016\/0166-218X(95)00106-2","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"808_CR19","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0012-365X(85)90046-9","volume":"55","author":"LM Kirousis","year":"1985","unstructured":"Kirousis, L.M., Papadimitriou, C.H.: Interval graphs and searching. Discrete Math. 55(2), 181\u2013184 (1985). https:\/\/doi.org\/10.1016\/0012-365X(85)90046-9","journal-title":"Discrete Math."},{"key":"808_CR20","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011)","journal-title":"Bull. EATCS"},{"issue":"4","key":"808_CR21","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci. 67(4), 757\u2013771 (2003). https:\/\/doi.org\/10.1016\/S0022-0000(03)00078-3","journal-title":"J. Comput. Syst. Sci."},{"issue":"549\u2013559","key":"808_CR22","first-page":"37","volume":"14","author":"PJ Slater","year":"1975","unstructured":"Slater, P.J.: Leaves of trees. Congr. Numer. 14(549\u2013559), 37 (1975)","journal-title":"Congr. Numer."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00808-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00808-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00808-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,22]],"date-time":"2021-07-22T14:03:57Z","timestamp":1626962637000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00808-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,23]]},"references-count":22,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["808"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00808-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,23]]},"assertion":[{"value":"6 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}