2026-07-25T22:07:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15407 2024-03-06T10:55:40Z ddc:004 open_access

Hardness of Metric Dimension in Graphs of Constant Treewidth Li, Shaohua Pilipczuk, Marcin Graph algorithms parameterized complexity width parameters NP-hard The Metric Dimension problem asks for a minimum-sized resolving set in a given (unweighted, undirected) graph G. Here, a set S ⊆ V(G) is resolving if no two distinct vertices of G have the same distance vector to S. The complexity of Metric Dimension in graphs of bounded treewidth remained elusive in the past years. Recently, Bonnet and Purohit [IPEC 2019] showed that the problem is W[1]-hard under treewidth parameterization. In this work, we strengthen their lower bound to show that Metric Dimension is NP-hard in graphs of treewidth 24. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shaohua Li and Marcin Pilipczuk 2021 Is Part Of LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2021.24 urn:nbn:de:0030-drops-154071 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.24 eng https://creativecommons.org/licenses/by/4.0/legalcode