Alternative parameterizations of Metric Dimension

A set of vertices in a graph is called if for any two distinct , there is such that , where denotes the length of a shortest path between and in the graph . The metric dimension of is the minimum cardinality of a resolving set. The problem, i.e. deciding whether , is NP-complete even for interval graphs (Foucaud et al., 2017). We study (for arbitrary graphs) from the lens of parameterized complexity. The problem parameterized by was proved to be -hard by Hartung and Nichterlein (2013) and we study the dual parameterization, i.e., the problem of whether , where is the order of . We prove that the dual parameterization admits (a) a kernel with at most vertices and (b) a randomized algorithm of runtime . Hartung and Nichterlein (2013) also observed that is fixed-parameter tractable when parameterized by the vertex cover number of the input graph. We complement this observation by showing that it does not admit a polynomial kernel even when parameterized by , unless NP ⊆ coNP/poly. Our reduction also gives evidence for non-existence of polynomial Turing kernels. We also prove that parameterized by bandwidth or cutwidth does not admit a polynomial kernel, unless NP ⊆ coNP/poly. Finally, using Eppstein's results (2015) we show that parameterized by max-leaf number does admit a polynomial kernel.