Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

Abstract

For a graph G, a subset S ⊆ V (G) is called a resolving set 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 and a positive integer k, and asks whether there exists a resolving set of size at most k. This problem was introduced in the 1970s and is known to be NP-hard [M. R. Garey and D. S. Johnson, Computers and Intractability—A Guide to NP-Completeness, Freeman, San Francisco, 1979]. In the realm of parameterized complexity, Hartung and Nichterlein [28th Conference on Computational Complexity, IEEE, Piscataway, NJ, 2013, pp. 266–276] proved that the problem is W[2]-hard when parameterized by the natural parameter k. They also observed that it is fixed parameter tractable (FPT) when parameterized by the vertex cover number and asked about its complexity under smaller parameters, in particular, the feedback vertex set number. We answer this question by proving that Metric Dimension is W[1]-hard when parameterized by the combined parameter feedback vertex set number plus pathwidth. This also improves the result of Bonnet and Purohit [IPEC 2019] which states that the problem is W[1]-hard parameterized by the pathwidth. On the positive side, we show that Metric Dimension is FPT when parameterized by either the distance to cluster or the distance to cocluster, both of which are smaller parameters than the vertex cover number.