Abstract:
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 s1 to s2.
These two classical problems are known 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. 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, where vc is the
vertex cover number. 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.
We only know of one other problem in the literature that admits such a tight algorithmic lower
bound with respect to vc. Similarly, the list of known problems with exponential lower bounds on
the number of vertices in kernelized instances is very short.