Hardness of Metric Dimension in Graphs of Constant Treewidth

Shaohua Li, Marcin Pilipczuk

The Metric Dimension problem asks for a minimum-sized resolving set in a given (unweighted, undirected) graph $G$. Here, a set $S\subseteq V(G)$ is resolving if no two distinct ve…