Metric Dimension Parameterized by Treewidth in Chordal Graphs

The metric dimension has been introduced independently by Harary, Melter [11] and Slater [15] in 1975 to identify vertices of a graph G using its distances to a subset of vertices of G. A resolving set X of a graph G is a subset of vertices such that, for every pair (u, v) of vertices of G, there is a vertex x in X such that the distance between x and u and the distance between x and v are distinct. The metric dimension of the graph is the minimum size of a resolving set. Computing the metric dimension of a graph is NP-hard even on split graphs and interval graphs. Bonnet and Purohit [2] proved that the metric dimension problem is W[1]-hard parameterized by treewidth. Li and Pilipczuk strengthened this result by showing that it is NP-hard for graphs of treewidth 24 in [14]. In this article, we prove that metric dimension is FPT parameterized by treewidth in chordal graphs.