- INSTANCE:
Graph
.
- SOLUTION:
A metric basis for
*G*, i.e., a subset such that for each pair there is a such that the length of the shortest path from*u*to*w*is different from the length of the shortest path from*v*to*w*. - MEASURE:
The cardinality of the metric basis, i.e., .

*Good News:*Approximable within [313].*Garey and Johnson:*GT61