The metric dimension 
(Tillquist et al. 2021) or 
(Tomescu and Javid 2007, Ali et al. 2016) of a
graph 
is the smallest number of nodes required to identify all other nodes based on shortest
path distances uniquely. More explicitly, following Foster-Greenwood and Uhl (2022),
let 
be a finite connected graph with vertex
set 
.
For vertices 
,
the graph distance 
is the length of the shortest path between 
and 
in 
. Consider a subset of vertices 
and refer to the vertices in 
as "landmarks." Then 
is called a resolving set if, for every pair of distinct vertices
, there exists a landmark 
such that 
. A resolving set of smallest possible size is
called a metric basis for 
, and the metric dimension of 
is the size of a metric basis.
Tillquist et al. (2021) summarize known results and give closed forms for a number of parametrized families of graphs.
A minimal resolving set is a resolving set that ceases to resolve the graph when any landmark is removed. Huang (2026) completely
characterized and enumerated such minimal resolving
sets for every rectangular grid graph 
with 
. Their possible cardinalities are 2, 3, and the even
integers from 4 through 
.
The decision problem associated with metric dimension is difficult even for graphs with very small treewidth. Benoit (2026) proved that
deciding whether a connected graph has metric
dimension at most a given integer 
is an NP-complete
problem for graphs of treewidth
at most two. This is the first possible hardness threshold, since a minimum resolving
set of a tree can be found in linear
time. Benoit (2026) attributes the mathematical construction and proof
to Claude, directed by the author. The accompanying Lean development formalizes the
reduction's metric-dimension values and treewidth bound,
but not NP membership or the running-time bounds.
