On the Parameterized and Approximation Hardness of Metric Dimension

The NP-hard METRIC DIMENSION problem is to decide for a given graph G and a positive integer k whether there is a vertex subset of size at most k that separates all vertex pairs in G. Herein, a vertex v separates a pair {u, w} if the distance (length of a shortest path) between v and u is different from the distance of v and w. We give a polynomial-time computable reduction from the BIPARTITE DOMINATING SET problem to METRIC DIMENSION on maximum degree three graphs such that there is a one-to-one correspondence between the solution sets of both problems. There are two main consequences of this: First, it proves that METRIC DIMENSION on maximum degree three graphs is W[2]-hard with respect to the parameter k. This answers an open question concerning the parameterized complexity of METRIC DIMENSION posed by Lokshtanov [Dagstuhl seminar, 2009] and also by Diaz et al. [ESA'12]. Additionally, it implies that a trivial n(O(k))-time algorithm cannot be improved to an n(o(k))-time algorithm, unless the assumption FPT not equal W[1] fails. Second, as BIPARTITE DOMINATING SET is inapproximable within o(log n), it follows that METRIC DIMENSION on maximum degree three graphs is also inapproximable by a factor of o(log n), unless NP = P. This strengthens the result of Hauptmann et al. [JDA'12] who proved APX-hardness on bounded-degree graphs.