MINIMUM METRIC DIMENSION

• INSTANCE: Graph $G=\left(V,E\right)$.

• SOLUTION: A metric basis for G, i.e., a subset $V' \subseteq V$ such that for each pair $u,v \in V$ there is a $w\in V'$ 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., $\vert V'\vert$.

  
  

• Good News: Approximable within $O(\log \vert V\vert)$ [313].

• Garey and Johnson: GT61