For a graph G, a subset S ⊆ V(G) is called a resolving set of G if, for any two vertices u, v ∈ V(G), there exists a vertex w ∈ S such that d(w, u) ≠ 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 ⊆ V(G) of size at most k such that, for any vertex u ∈ V(G), there are two vertices s1, s2 ∈ S such that u lies on a shortest path from s1to s2. 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 2O(vc2)·nO(1) time, and a kernelization algorithm that outputs a kernel with 2O(vc) vertices. We prove that unless the Exponential Time Hypothesis (ETH) fails, Metric Dimension and Geodetic Set, even on graphs of bounded diameter, do not admit · an FPT algorithm running in 2o(vc2)·nO(1) time, nor · a kernelization algorithm that does not increase the solution size and outputs a kernel with 2o(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.

Funding Florent Foucaud: ANR project GRALMECO (ANR-21-CE48-0004), French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25), International Research Center “Innovation Transportation and Production Systems” of the I-SITE CAP 20-25. Liana Khazaliya: Vienna Science and Technology Fund (WWTF) [10.47379/ICT22029]; Austrian Science Fund (FWF) [10.55776/Y1329]; European Union’s Horizon 2020 COFUND programme [LogiCS@TUWien, grant agreement No. 101034440]. Shaohua Li: National Natural Science Foundation of China under Grant 62472449. Fionn Mc Inerney: Smart Networks and Services Joint Undertaking (SNS JU) under the EU’s Horizon Europe and innovation programme under Grant Agreement No. 101139067 (ELASTIC).