Get Metric Dimension Graph Theory essential facts below. View Videos or join the Metric Dimension Graph Theory discussion. Add Metric Dimension Graph Theory to your PopFlock.com topic list for future reference or share this resource on social media.
Metric Dimension Graph Theory
In graph theory, the metric dimension of a graph G is the minimum cardinality of a subset S of vertices such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.
For an ordered subset of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the ordered k-tuple , where d(x,y) represents the distance between the vertices x and y. The set W is a resolving set (or locating set) for G if every two vertices of G have distinct representations. The metric dimension of G is the minimum cardinality of a resolving set for G. A resolving set containing a minimum number of vertices is called a basis (or reference set) for G. Resolving sets for graphs were introduced independently by Slater (1975) and Harary & Melter (1976), while the concept of a resolving set and that of metric dimension were defined much earlier in the more general context of metric spaces by Blumenthal in his monograph Theory and Applications of Distance Geometry. Graphs are special examples of metric spaces with their intrinsic path metric.
Slater (1975) (see also Harary & Melter (1976) and Khuller, Raghavachari & Rosenfeld (1996)) provides the following simple characterization of the metric dimension of a tree. If the tree is a path, its metric dimension is one. Otherwise, let L denote the set of degree-one vertices in the tree (usually called leaves, although Slater uses that word differently). Let K be the set of vertices that have degree greater than two, and that are connected by paths of degree-two vertices to one or more leaves. Then the metric dimension is |L| − |K|. A basis of this cardinality may be formed by removing from L one of the leaves associated with each vertex in K. The same algorithm is valid for the line graph of the tree, as proved by Feng, Xu & Wang (2013) (and thus any tree and its line graph have the same metric dimension).
Relations between the order, the metric dimension and the diameter
Khuller, Raghavachari & Rosenfeld (1996) prove the inequality for any n-vertex graph with diameterD and metric dimension ?. This bounds follows from the fact that each vertex that is not in the resolving set is uniquely determined by a distance vector of length ? with each entry being an integer between 1 and D (there are precisely such vectors). However, the bound is only achieved for or ; the more precise bound is proved by Hernando et al. (2010).
The metric dimension of an arbitrary n-vertex graph may be approximated in polynomial time to within an approximation ratio of by expressing it as a set cover problem, a problem of covering all of a given collection of elements by as few sets as possible in a given family of sets (Khuller, Raghavachari & Rosenfeld 1996). In the set cover problem formed from a metric dimension problem, the elements to be covered are the pairs of vertices to be distinguished, and the sets that can cover them are the sets of pairs that can be distinguished by a single chosen vertex. The approximation bound then follows by applying standard approximation algorithms for set cover. An alternative greedy algorithm that chooses vertices according to the difference in entropy between the equivalence classes of distance vectors before and after the choice achieves an even better approximation ratio, (Hauptmann, Schmied & Viehmann 2012). This approximation ratio is close to best possible, as under standard complexity-theoretic assumptions a ratio of cannot be achieved in polynomial time for any (Hauptmann, Schmied & Viehmann 2012). The latter hardness of approximation still holds for instances restricted to subcubic graphs (Hartung & Nichterlein 2013), and even to bipartite subcubic graphs as shown in Hartung's PhD thesis (Hartung 2014).
Beaudou, Laurent; Dankelmann, Peter; Foucaud, Florent; Henning, Michael A.; Mary, Arnaud; Parreau, Aline (2018), "Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension", SIAM Journal on Discrete Mathematics, 32 (2): 902-918, arXiv:1610.01475, doi:10.1137/16M1097833, S2CID51882750
Belmonte, R.; Fomin, F. V.; Golovach, P. A.; Ramanujan, M. S. (2015), "Metric dimension of bounded width graphs", in Italiano, G. F.; Pighizzini, G.; Sannella, D. T. (eds.), Mathematical Foundations of Computer Science 2015 - MFCS 2015: 40th International Symposium, Milan, Italy, August 24-28, 2015, Proceedings, Lecture Notes in Computer Science, 9235, Springer, pp. 115-126, doi:10.1007/978-3-662-48054-0_10.
Blumenthal, L.M. (1953), Theory and Applications of Distance Geometry, Clarendon, Oxford.
Bonnet, E.; Purohit, N. (2019), "Metric Dimension Parameterized by Treewidth", in Jansen, B. M. P.; Telle, J. A. (eds.), Parameterized and Exact Computation 2019 - IPEC 2019: 14th International Symposium, Proceedings, Leibniz International Proceedings in Informatics (LIPIcs), 148, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, pp. 5:1-5:15, arXiv:1907.08093, doi:10.4230/LIPIcs.IPEC.2019.5.
Hartung, Sepp; Nichterlein, André (2013), "On the parameterized and approximation hardness of metric dimension", 2013 IEEE Conference on Computational Complexity (CCC), Stanford, CA, USA, June 5-7, 2013, Proceedings, IEEE, pp. 266-276, arXiv:1211.1636, doi:10.1109/CCC.2013.36, S2CID684505.
Hoffmann, Stefan; Elterman, Alina; Wanke, Egon (2016), "A linear time algorithm for metric dimension of cactus block graphs", Theoretical Computer Science, 630: 43-62, doi:10.1016/j.tcs.2016.03.024
Hoffmann, Stefan; Wanke, Egon (2012), "Metric Dimension for Gabriel Unit Disk Graphs Is NP-Complete", in Bar-Noy, Amotz; Halldórsson, Magnús M. (eds.), Algorithms for Sensor Systems: 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2012, Ljubljana, Slovenia, September 13-14, 2012, Revised Selected Papers, Lecture Notes in Computer Science, 7718, Springer, pp. 90-92, arXiv:1306.2187, doi:10.1007/978-3-642-36092-3_10, S2CID9740623.
Slater, P. J. (1975), "Leaves of trees", Proc. 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), Congressus Numerantium, 14, Winnipeg: Utilitas Math., pp. 549-559, MR0422062.
Slater, P. J. (1988), "Dominating and reference sets in a graph", Journal of Mathematical and Physical Sciences, 22 (4): 445-455, MR0966610.