14.10.2010

We study the approximation complexity of the Metric Dimension problem in bounded degree, dense as well as in general graphs. For the general case, we prove that the Metric Dimension problem is not approximable within (1-ε) ln(n) for any ε > 0, unless NP ⊆ DTIME(n^log(log(n))), and we give an approximation algorithm which matches the lower bound.
Even for bounded degree instances it is APX-hard to determine (compute) the value of the metric dimension which we prove by constructing an approximation preserving reduction from the bounded degree Vertex Cover problem.
The special case, in which the underlying graph is superdense turns out to be APX-complete. In particular, we present a greedy constant factor approximation algorithm for these kind of instances and construct an approximation preserving reduction from the bounded degree Dominating Set problem. We also provide first explicit approximation lower bounds for the Metric Dimension problem restricted to dense and bounded degree graphs.