  A set of vertices $W$ in a graph $G$ is called resolving if for any two
distinct $x,y\in V(G)$, there is $v\in W$ such that ${\rm dist}_G(v,x)\neq{\rm
dist}_G(v,y)$, where ${\rm dist}_G(u,v)$ denotes the length of a shortest path
between $u$ and $v$ in the graph $G$. The metric dimension ${\rm md}(G)$ of $G$
is the minimum cardinality of a resolving set. The Metric Dimension problem,
i.e. deciding whether ${\rm md}(G)\le k$, is NP-complete even for interval
graphs (Foucaud et al., 2017). We study Metric Dimension (for arbitrary graphs)
from the lens of parameterized complexity. The problem parameterized by $k$ was
proved to be $W[2]$-hard by Hartung and Nichterlein (2013) and we study the
dual parameterization, i.e., the problem of whether ${\rm md}(G)\le n- k,$
where $n$ is the order of $G$. We prove that the dual parameterization admits
(a) a kernel with at most $3k^4$ vertices and (b) an algorithm of runtime
$O^*(4^{k+o(k)}).$ Hartung and Nichterlein (2013) also observed that Metric
Dimension is fixed-parameter tractable when parameterized by the vertex cover
number $vc(G)$ of the input graph. We complement this observation by showing
that it does not admit a polynomial kernel even when parameterized by $vc(G) +
k$. Our reduction also gives evidence for non-existence of polynomial Turing
kernels.
