Metric dimension and geodetic set parameterized by vertex cover

Abstract

For a graph G, a subset 𝑆 ⊆𝑉⁡(𝐺) is called a resolving set of G if, for any two vertices 𝑢,𝑣 ∈𝑉⁡(𝐺), there exists a vertex 𝑤 ∈𝑆 such that 𝑑⁡(𝑤,𝑢) ≠𝑑⁡(𝑤,𝑣). 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 𝑆 ⊆𝑉⁡(𝐺) of size at most k such that, for any vertex 𝑢 ∈𝑉⁡(𝐺), there are two vertices 𝑠1,𝑠2 ∈𝑆 such that u lies on a shortest path from 𝑠1 to 𝑠2. These two classical problems are intractable with respect to the solution size, as well as most structural parameters, including the feedback vertex set number and pathwidth. The very few existing tractable results state that they are both FPT with respect to the vertex cover number vc. Specifically, we observe that both problems admit an FPT algorithm running in 2𝒪⁡(𝚟𝚌2) ⋅𝑛𝒪⁡(1) time, and a kernelization algorithm that outputs a kernel with 2𝒪⁡(𝚟𝚌) vertices. For these problems, we also prove that, unless the Exponential Time Hypothesis fails, the established running time is asymptotically the best possible.