Abstract
Given an input undirected graph \(G=(V,E)\), we say that a vertex \(\ell \) separates \(u\) from \(v\) (where \(u,v\in V\)) if the distance between \(u\) and \(\ell \) differs from the distance from \(v\) to \(\ell \). A set of vertices \(L\subseteq V\) is a feasible solution if for every pair of vertices, \(u,v\in V\) (\(u\ne v\)), there is a vertex \(\ell \in L\) that separates \(u\) from \(v\). Such a feasible solution is called a landmark set, and the metric dimension of a graph is the minimum cardinality of a landmark set. Here, we extend this well-studied problem to the case where each vertex \(v\) has a non-negative cost, and the goal is to find a feasible solution with a minimum total cost. This weighted version is NP-hard since the unweighted variant is known to be NP-hard. We show polynomial time algorithms for the cases where \(G\) is a path, a tree, a cycle, a cograph, a \(k\)-edge-augmented tree (that is, a tree with additional \(k\) edges) for a constant value of \(k\), and a (not necessarily complete) wheel. The results for paths, trees, cycles, and complete wheels extend known polynomial time algorithms for the unweighted version, whereas the other results are the first known polynomial time algorithms for these classes of graphs even for the unweighted version. Next, we extend the set of graph classes for which computing the unweighted metric dimension of a graph is known to be NP-hard. We show that for split graphs, bipartite graphs, co-bipartite graphs, and line graphs of bipartite graphs, the problem of computing the unweighted metric dimension of the graph is NP-hard.
Similar content being viewed by others
Notes
In [19], a hairy cycle is defined to be a cycle such that each of its vertices has a leg of one vertex. Here we allow an arbitrary number of vertices in each leg (for each cycle vertex) including the option of zero vertices (in such a case, the considered cycle vertex does not have a leg).
References
Babai, L.: On the order of uniprimitive permutation groups. Ann. Math. 113(3), 553–568 (1981)
Beerliova, Z., Eberhard, F., Erlebach, T., Hall, A., Hoffmann, M., Mihalák, M., Ram, L.S.: Network discovery and verification. IEEE J. Sel. Areas Commun. 24(12), 2168–2181 (2006)
Cáceres, J., Hernando, M.C., Mora, M., Pelayo, I.M., Puertas, M.L., Seara, C., Wood, D.R.: On the metric dimension of cartesian products of graphs. SIAM J. Discr. Math. 21(2), 423–441 (2007)
Chartrand, G., Eroh, L., Johnson, M.A., Oellermann, O.R.: Resolvability in graphs and the metric dimension of a graph. Discr. Appl. Math. 105(1–3), 99–113 (2000)
Chartrand, G., Zhang, P.: The theory and applications of resolvability in graphs: A survey. Congressus Numerantium 160, 47–68 (2003)
Chvátal, V.: Mastermind. Combinatorica 3(3), 325–329 (1983)
Corneil, D., Perl, Y., Stewart, L.: A linear recognition algorithm for cographs. SIAM J. Comput. 14(4), 926–934 (1985)
Díaz, J., Pottonen, O., Serna, M.J., van Leeuwen, E.J.: On the complexity of metric dimension. In: Epstein, L., Ferragina, P. (eds.) ESA, Lecture Notes in Computer Science, vol. 7501, pp. 419–430. Springer, Berlin (2012)
Harary, F., Melter, R.: The metric dimension of a graph. Ars Combinatoria 2, 191–195 (1976)
Hartung, S., Nichterlein, A.: On the parameterized and approximation hardness of metric dimension. In: Umans, C. (ed.) Proceedings of IEEE Conference on Computational Complexity (CCC), pp. 266–276 (2013)
Hauptmann, M., Schmied, R., Viehmann, C.: Approximation complexity of metric dimension problem. J. Discr. Algorithms 14, 214–222 (2012)
Hoffmann, S., Wanke, E.: Metric dimension for Gabriel unit disk graphs is NP-complete. In: Bar-Noy, A., Halldórsson, Magnús, M. (eds.) ALGOSENSORS: Lecture Notes in Computer Science, vol. 7718, pp. 90–92. Springer, Berlin (2013). Also in CoRR, abs/1306.2187 (2013)
Johnson, D.: The NP-completeness column: an ongoing guide. J. Algorithms 6(3), 434–451 (1985)
Khuller, S., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs. Discr. Appl. Math. 70(3), 217–229 (1996)
Melter, R.A., Tomescu, I.: Metric bases in digital geometry. Comput. Vis. Graph. Image Process. 25, 113–121 (1984)
Sebö, A., Tannier, E.: On metric generators of graphs. Math. Oper. Res. 29(2), 383–393 (2004)
Shanmukha, B., Sooryanarayana, B., Harinath, K.S.: Metric dimension of wheels. Far East J. Appl. Math. 8(3), 217–229 (2002)
Slater, P.J.: Leaves of trees. Congressus Numerantium 14, 549–559 (1975)
Wojciechowski, J.: Minimal equitability of hairy cycles. J. Combin. Math. Combin. Comput. 57, 129–150 (2006)
Author information
Authors and Affiliations
Corresponding author
Additional information
An extended abstract of this paper appears in Proc. WG2012, pages 114–125.
Rights and permissions
About this article
Cite this article
Epstein, L., Levin, A. & Woeginger, G.J. The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases. Algorithmica 72, 1130–1171 (2015). https://doi.org/10.1007/s00453-014-9896-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-014-9896-2