  For a graph $G$, a subset $S\subseteq V(G)$ is called a resolving set of $G$
if, for any two vertices $u,v\in V(G)$, there exists a vertex $w\in S$ such
that $d(w,u)\neq d(w,v)$. The Metric Dimension problem takes as input a graph
$G$ on $n$ vertices and a positive integer $k$, and asks whether there exists a
resolving set of size at most $k$. In another metric-based graph problem,
Geodetic Set, the input is a graph $G$ and an integer $k$, and the objective is
to determine whether there exists a subset $S\subseteq V(G)$ of size at most
$k$ such that, for any vertex $u \in V(G)$, there are two vertices $s_1, s_2
\in S$ such that $u$ lies on a shortest path from $s_1$ to $s_2$.
  These two classical problems turn out to be intractable with respect to the
natural parameter, i.e., the solution size, as well as most structural
parameters, including the feedback vertex set number and pathwidth. Some of the
very few existing tractable results state that they are both FPT with respect
to the vertex cover number $vc$.
  More precisely, we observe that both problems admit an FPT algorithm running
in time $2^{\mathcal{O}(vc^2)}\cdot n^{\mathcal{O}(1)}$, and a kernelization
algorithm that outputs a kernel with $2^{\mathcal{O}(vc)}$ vertices. We prove
that unless the Exponential Time Hypothesis fails, Metric Dimension and
Geodetic Set, even on graphs of bounded diameter, neither admit an FPT
algorithm running in time $2^{o(vc^2)}\cdot n^{\mathcal(1)}$, nor a
kernelization algorithm that reduces the solution size and outputs a kernel
with $2^{o(vc)}$ vertices. The versatility of our technique enables us to apply
it to both these problems.
  We only know of one other problem in the literature that admits such a tight
lower bound. Similarly, the list of known problems with exponential lower
bounds on the number of vertices in kernelized instances is very short.
