View source for 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]].

==Detailed definition==
For an ordered subset <math>W = \{w_1, w_2,\dots, w_k\}</math> of vertices and a vertex ''v'' in a connected graph ''G'', the representation of ''v'' with respect to ''W'' is the ordered ''k''-tuple <math>r(v|W) = (d(v,w_1), d(v,w_2),\dots,d(v,w_k))</math>, 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 {{harvtxt|Slater|1975}} and {{harvtxt|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 [[Leonard_Blumenthal|Blumenthal]] in his monograph ''Theory and Applications of Distance Geometry''. Graphs are special examples of metric spaces with their intrinsic path metric.

==Trees==
If a tree is a path, its metric dimension is one. Otherwise, let ''L'' denote the set of leaves, degree-one vertices in the tree. 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''|&nbsp;&minus;&nbsp;|''K''|. A basis of this cardinality may be formed by removing from ''L'' one of the leaves associated with each vertex in ''K''.<ref>{{harvnb|Slater|1975}}; {{harvnb|Harary|Melter|1976}}; {{harvnb|Khuller|Raghavachari|Rosenfeld|1996}}. Note Slater's nonstandard definition of the leaves of a tree.</ref> The same algorithm is valid for the line graph of the tree, and thus any tree and its line graph have the same metric dimension.{{sfn|Feng|Xu|Wang|2013}}

==Properties==
In {{harvtxt|Chartrand|Eroh|Johnson|Oellermann|2000}}, it is proved that:
* The metric dimension of a graph {{mvar|G}} is 1 if and only if {{mvar|G}} is a path.
* The metric dimension of an {{mvar|n}}-vertex graph is {{math|''n'' &minus; 1}} if and only if it is a [[complete graph]].
* The metric dimension of an {{mvar|n}}-vertex graph is {{math|''n'' &minus; 2}} if and only if the graph is a [[complete bipartite graph]] {{math|''K''<sub>''s'', ''t''</sub>}}, a [[split graph]] <math>K_s+\overline{K_t} (s\geq 1, t\geq 2)</math>, or <math>K_s+(K_1\cup K_t) (s,t\geq 1) </math>.

===Relations between the order, the metric dimension and the diameter===
{{harvtxt|Khuller|Raghavachari|Rosenfeld|1996}} prove the inequality <math> n\leq D^{\beta}+\beta</math> for any {{mvar|n}}-vertex graph with [[diameter (graph theory)|diameter]] <math>D</math> and metric dimension <math>\beta</math>. 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 <math>\beta</math> with each entry being an integer between 1 and <math>D</math> (there are precisely <math>D^{\beta}</math> such vectors). However, the bound is only achieved for <math>D\leq 3</math> or <math>\beta=1</math>; the more precise bound <math display=block> n\leq \left(\lfloor 2D/3\rfloor+1\right)^\beta+\beta\sum_{i=1}^{\lceil D/3\rceil}(2i-1)^{\beta-1}</math>  is proved by {{harvtxt|Hernando|Mora|Pelayo|Seara|2010}}.

For specific graph classes, smaller bounds can hold. For example, {{harvtxt|Beaudou|Dankelmann|Foucaud|Henning|2018}} proved that <math>n\leq(\beta D+4)(D+2)/8</math> for trees (the bound being tight for even values of {{mvar|D}}), and a bound of the form <math>n= O(D^2\beta)</math> for [[outerplanar graph]]s. The same authors proved that <math>n\leq (D\beta+1)^{t-1}</math> for graphs with no [[complete graph]] of order {{mvar|t}} as a [[Graph minor|minor]] and also gave bounds for [[chordal graph]]s and graphs of bounded [[treewidth]]. The authors 
{{harvtxt|Foucaud|Mertzios|Naserasr|Parreau|2017a}} proved bounds of the form <math>n= O(D\beta^2)</math> for [[interval graph]]s and [[permutation graph]]s, and bounds of the form <math>n=O(D\beta)</math> for [[unit interval graph]]s, bipartite permutation graphs and [[cograph]]s.

==Computational complexity==

===Decision complexity===
Deciding whether the metric dimension of a graph is at most a given integer is NP-complete.{{sfn|Garey|Johnson|1979}} It remains NP-complete for bounded-degree [[planar graph]]s,{{sfn|Díaz|Pottonen|Serna|van Leeuwen|2012}} [[split graph]]s, [[bipartite graph]]s and their [[complement (graph theory)|complements]], [[line graph]]s of bipartite graphs,{{sfn|Epstein|Levin|Woeginger|2012}} [[unit disk graph]]s,{{sfn|Hoffmann|Wanke|2013}} [[interval graph]]s of diameter 2 and [[permutation graph]]s of diameter 2,{{sfn|Foucaud|Mertzios|Naserasr|Parreau|2017b}} and graphs of bounded [[treewidth]].{{sfn|Li|Pilipczuk|2022}}

For any fixed constant ''k'', the graphs of metric dimension at most ''k'' can be recognized in [[polynomial time]], by testing all possible ''k''-tuples of vertices, but this algorithm is not [[parameterized complexity|fixed-parameter tractable]] (for the natural parameter ''k'', the solution size). Answering a question posed by {{harvtxt|Lokshtanov|2010}}, {{harvtxt|Hartung|Nichterlein|2013}} show that the metric dimension decision problem is complete for the parameterized complexity class W[2], implying that a time bound of the form ''n''<sup>O(''k'')</sup> as achieved by this naive algorithm is likely optimal and that a fixed-parameter tractable algorithm (for the parameterization by ''k'') is unlikely to exist. Nevertheless, the problem becomes [[parameterized complexity|fixed-parameter tractable]] when restricted to [[interval graph]]s,{{sfn|Foucaud|Mertzios|Naserasr|Parreau|2017b}} and more generally to graphs of bounded tree-length,{{sfn|Belmonte|Fomin|Golovach|Ramanujan|2015}} such as [[chordal graph]]s, [[permutation graph]]s or asteroidal-triple-free graphs.

Deciding whether the metric dimension of a tree is at most a given integer can be done in linear time<ref>{{harvnb|Slater|1975}}; {{harvnb|Harary|Melter|1976}}.</ref> Other linear-time algorithms exist for [[cograph]]s,{{sfn|Epstein|Levin|Woeginger|2012}} [[chain graph]]s,{{sfn|Fernau|Heggernes|van 't Hof|Meister|2015}} and cactus block graphs{{sfn|Hoffmann|Elterman|Wanke|2016}} (a class including both [[cactus graph]]s and [[block graph]]s). The problem may be solved in polynomial time on [[outerplanar graph]]s.{{sfn|Díaz|Pottonen|Serna|van Leeuwen|2012}} It may also be solved in polynomial time for graphs of bounded [[cyclomatic number]],{{sfn|Epstein|Levin|Woeginger|2012}} but this algorithm is again not fixed-parameter tractable (for the parameter "cyclomatic number") because the exponent in the polynomial depends on the cyclomatic number. There exist fixed-parameter tractable algorithms to solve the metric dimension problem for the parameters "[[vertex cover]]",{{sfn|Hartung|Nichterlein|2013}} "max leaf number",{{sfn|Eppstein|2015}} and "modular width".{{sfn|Belmonte|Fomin|Golovach|Ramanujan|2015}} Graphs with bounded cyclomatic number, vertex cover number or max leaf number all have bounded [[treewidth]], however it is an open problem to determine the complexity of the metric dimension problem even on graphs of treewidth 2, that is, [[series–parallel graph]]s.{{sfn|Belmonte|Fomin|Golovach|Ramanujan|2015}}

===Approximation complexity===
The metric dimension of an arbitrary ''n''-vertex graph may be approximated in polynomial time to within an [[Approximation algorithm|approximation ratio]] of <math>2\log n</math> 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]]. {{sfn|Khuller|Raghavachari|Rosenfeld|1996}} In the set cover problem formed from a metric dimension problem, the elements to be covered are the <math>\tbinom{n}{2}</math> 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, <math>\log n+\log\log_2 n+1</math>.{{sfn|Hauptmann|Schmied|Viehmann|2012}} This approximation ratio is close to best possible, as under standard complexity-theoretic assumptions a ratio of <math>(1-\epsilon)\log n</math> cannot be achieved in polynomial time for any <math>\epsilon>0</math>.{{sfn|Hauptmann|Schmied|Viehmann|2012}} The latter hardness of approximation still holds for instances restricted to subcubic graphs,{{sfn|Hartung|Nichterlein|2013}} and even to [[Bipartite_graph|bipartite]] subcubic graphs.{{sfn|Hartung|2014}}

==References==
===Notes===
{{reflist}}

===Bibliography===
*{{citation|first1=Laurent|last1=Beaudou|first2=Peter|last2=Dankelmann|first3=Florent|last3=Foucaud|first4=Michael A.|last4=Henning|first5=Arnaud|last5=Mary|first6=Aline|last6=Parreau|title=Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension|journal=SIAM Journal on Discrete Mathematics|volume=32|issue=2|arxiv=1610.01475|doi=10.1137/16M1097833|pages=902–918|year=2018|s2cid=51882750}}
*{{citation|first1=R.|last1=Belmonte|first2=F. V.|last2=Fomin|first3=P. A.|last3=Golovach|last4=Ramanujan|first4=M. S.|contribution=Metric dimension of bounded width graphs|title=Mathematical Foundations of Computer Science 2015 – MFCS 2015: 40th International Symposium, Milan, Italy, August 24-28, 2015, Proceedings|volume=9235|series=[[Lecture Notes in Computer Science]]|pages=115–126|publisher=Springer|year=2015|editor1-first=G. F.|editor1-last=Italiano|editor2-first=G.|editor2-last=Pighizzini|editor3-first=D. T.|editor3-last=Sannella|doi=10.1007/978-3-662-48054-0_10|isbn=978-3-662-48053-3 }}.
*{{citation|first=L.M.|last=Blumenthal|title=Theory and Applications of Distance Geometry|publisher=Clarendon, Oxford|year=1953}}. 
*{{citation|first1=E.|last1=Bonnet|first2=N.|last2=Purohit|arxiv=1907.08093|contribution=Metric Dimension Parameterized by Treewidth|title=Parameterized and Exact Computation 2019 – IPEC 2019: 14th International Symposium, Proceedings|volume=148|series=Leibniz International Proceedings in Informatics (LIPIcs)|pages=5:1–5:15|publisher=Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik|year=2019|editor1-first=B. M. P.|editor1-last=Jansen|editor2-first=J. A.|editor2-last=Telle|doi=10.4230/LIPIcs.IPEC.2019.5|doi-access=free }}.
*{{citation|first1=P.|last1=Buczkowski|first2=G.|last2=Chartrand|author2-link=Gary Theodore Chartrand|first3=C.|last3=Poisson|first4=P.|last4=Zhang|title=On {{mvar|k}}-dimensional graphs and their bases|journal=Periodica Mathematica Hungarica|volume=46|issue=1|pages=9–15|year=2003|doi=10.1023/A:1025745406160|mr=1975342|s2cid=33390310}}.
*{{citation|first1=G.|last1=Chartrand|author1-link=Gary Theodore Chartrand|first2=L.|last2=Eroh|first3=M. A.|last3=Johnson|first4=O. R.|last4=Oellermann|author4-link= Ortrud Oellermann |title=Resolvability in graphs and the metric dimension of a graph|journal=[[Discrete Applied Mathematics]]|volume=105|issue=1–3|doi=10.1016/S0166-218X(00)00198-0|pages=99–113|year=2000|mr=1780464|hdl=10338.dmlcz/127843|hdl-access=free}}.
*{{citation|first1=J.|last1=Díaz|first2=O.|last2=Pottonen|first3=M. J.|last3=Serna|author3-link= Maria Serna |first4=E. J.|last4=van Leeuwen|contribution=On the complexity of metric dimension|title=Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012, Proceedings|volume=7501|series=Lecture Notes in Computer Science|pages=419–430|publisher=Springer|year=2012|contribution-url=http://www.lsi.upc.edu/~diaz/papersd/ESA-proc2.pdf|arxiv=1107.2256|editor1-first=Leah|editor1-last=Epstein|editor2-first=Paolo|editor2-last=Ferragina|doi=10.1007/978-3-642-33090-2_37|isbn=978-3-642-33089-6 }}.
*{{citation|first1=David|last1=Eppstein|authorlink=David Eppstein|title=Metric dimension parameterized by max leaf number|journal=[[Journal of Graph Algorithms and Applications]]|volume=19|issue=1|pages=313–323|year=2015|arxiv=1506.01749|doi=10.7155/jgaa.00360|s2cid=1318601}}.
*{{citation|first1=Leah|last1=Epstein|first2=Asaf|last2=Levin|first3=Gerhard J.|last3=Woeginger|author3-link=Gerhard J. Woeginger|contribution=The (weighted) metric dimension of graphs: hard and easy cases|title=Graph-Theoretic Concepts in Computer Science: 38th International Workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012, Revised Selected Papers|series=Lecture Notes in Computer Science|editor1-first=Martin Charles|editor1-last=Golumbic|editor1-link=Martin Charles Golumbic|editor2-first=Michal|editor2-last=Stern|editor3-first=Avivit|editor3-last=Levy|editor4-first=Gila|display-editors = 3 |editor4-last=Morgenstern|volume=7551|year=2012|pages=114–125|doi=10.1007/978-3-642-34611-8_14|isbn=978-3-642-34610-1 |url=https://research.tue.nl/nl/publications/the-weighted-metric-dimension-of-graphs--hard-and-easy-cases(f86db641-15c6-46a0-a1fc-6a69fd710049).html}}.
*{{citation|first1=Min|last1=Feng|first2=Min|last2=Xu|first3=Kaishun|last3=Wang|title=On the metric dimension of line graphs|journal=[[Discrete Applied Mathematics]]|volume=161|issue=6|doi=10.1016/j.dam.2012.10.018|pages=802–805|year=2013|arxiv=1107.4140|s2cid=36010185}}.
*{{citation
 | last1 = Fernau | first1 = Henning
 | last2 = Heggernes | first2 = Pinar | author2-link = Pinar Heggernes
 | last3 = van 't Hof | first3 = Pim
 | last4 = Meister | first4 = Daniel
 | last5 = Saei | first5 = Reza
 | doi = 10.1016/j.ipl.2015.04.006
 | journal = [[Information Processing Letters]]
 | pages = 671–676
 | title = Computing the metric dimension for chain graphs
 | volume = 115
 | issue = 9
 | year = 2015}}.
*{{citation|first1=Florent|last1=Foucaud|first2=George B.|last2=Mertzios|first3=Reza|last3=Naserasr|first4=Aline|last4=Parreau|first5=Petru|last5=Valicov|title=Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds|journal=Theoretical Computer Science|volume=68|arxiv=1507.08164|doi=10.1016/j.tcs.2017.01.006|pages=43–58|year=2017a|s2cid=25244200}}
*{{citation|first1=Florent|last1=Foucaud|first2=George B.|last2=Mertzios|first3=Reza|last3=Naserasr|first4=Aline|last4=Parreau|first5=Petru|last5=Valicov|title=Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity|journal=[[Algorithmica]]|volume=78|issue=3|pages=914–944|year=2017b|arxiv=1405.2424|doi=10.1007/s00453-016-0184-1|s2cid=1520161}}.
*{{citation|author1-link=Michael R. Garey|first1=M. R.|last1=Garey|author2-link=David S. Johnson|first2=D. S.|last2=Johnson | year = 1979 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher = W.H. Freeman | isbn = 0-7167-1045-5}} A1.5: GT61, p.&nbsp;204.
*{{citation|first1=F.|last1=Harary|author1-link=Frank Harary|first2=R. A.|last2=Melter|title=On the metric dimension of a graph|journal=[[Ars Combinatoria (journal)|Ars Combinatoria]]|volume=2|pages=191–195|year=1976|mr=0457289}}.
*{{citation|first=Sepp|last=Hartung|title=Exploring parameter spaces in coping with computational intractability, PhD thesis|year=2014|accessdate=2015-09-15|publisher=Technische Universität Berlin|url=https://opus4.kobv.de/opus4-tuberlin/frontdoor/index/index/docId/4644}}.
*{{citation|first1=Sepp|last1=Hartung|first2=André|last2=Nichterlein|contribution=On the parameterized and approximation hardness of metric dimension|title=2013 IEEE Conference on Computational Complexity (CCC), Stanford, CA, USA, June 5-7, 2013, Proceedings|publisher=IEEE|year=2013|pages=266–276|doi=10.1109/CCC.2013.36|arxiv=1211.1636|isbn=978-0-7695-4997-2 |s2cid=684505}}.
*{{citation
 | last1 = Hauptmann | first1 = Mathias
 | last2 = Schmied | first2 = Richard
 | last3 = Viehmann | first3 = Claus
 | doi = 10.1016/j.jda.2011.12.010
 | journal = Journal of Discrete Algorithms
 | mr = 2922072
 | pages = 214–222
 | title = Approximation complexity of metric dimension problem
 | volume = 14
 | year = 2012| doi-access = free
 }}.
*{{citation
 | last1 = Hernando | first1 = Carmen
 | last2 = Mora | first2 = Mercè
 | last3 = Pelayo | first3 = Ignacio M.
 | last4 = Seara | first4 = Carlos
 | last5 = Wood | first5 = David R. | author5-link = David Wood (mathematician)
 | journal = [[Electronic Journal of Combinatorics]]
 | url = http://www.combinatorics.org/Volume_17/Abstracts/v17i1r30.html
 | pages = #R30
 | title = Extremal graph theory for metric dimension and diameter
 | volume = 17
 | year = 2010| doi = 10.37236/302
 | doi-access = free
 | hdl = 2117/8261
 | hdl-access = free
 }}.
*{{citation|first1=Stefan|last1=Hoffmann|first2=Alina|last2=Elterman|first3=Egon|last3=Wanke|title=A linear time algorithm for metric dimension of cactus block graphs|journal=Theoretical Computer Science|volume=630|doi=10.1016/j.tcs.2016.03.024|pages=43–62|year=2016|doi-access=free}}
*{{citation|first1=Stefan|last1=Hoffmann|first2=Egon|last2=Wanke|contribution=Metric Dimension for Gabriel Unit Disk Graphs Is NP-Complete|title=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|volume=7718|series=Lecture Notes in Computer Science|date=2013 |pages=90–92|editor1-first=Amotz|editor1-last=Bar-Noy|editor2-first=Magnús M.|editor2-last=Halldórsson|publisher=Springer|doi=10.1007/978-3-642-36092-3_10|arxiv=1306.2187|isbn=978-3-642-36091-6 |s2cid=9740623}}.
*{{citation|last1=Khuller|first1=S.|authorlink=Samir Khuller|last2=Raghavachari|first2=B.|last3=Rosenfeld|first3=A.|title=Landmarks in graphs|journal=[[Discrete Applied Mathematics]]|volume=70|issue=3|doi=10.1016/0166-218x(95)00106-2|pages=217–229|year=1996|hdl=10338.dmlcz/140702|hdl-access=free}}.
*{{citation
 | last1 = Li | first1 = Shaohua
 | last2 = Pilipczuk | first2 = Marcin
 | date = July 2022
 | doi = 10.1007/s00453-022-01005-y
 | issue = 11
 | journal = Algorithmica
 | pages = 3110–3155
 | title = Hardness of metric dimension in graphs of constant treewidth
 | volume = 84| arxiv = 2102.09791
 | s2cid = 231979414
 }}
*{{citation
 | last = Lokshtanov | first = Daniel
 | editor1-last = Demaine | editor1-first = Erik D. | editor1-link = Erik Demaine
 | editor2-last = Hajiaghayi | editor2-first = MohammadTaghi
 | editor3-last = Marx | editor3-first = Dániel
 | contribution = Open problems – Parameterized complexity and approximation algorithms: Metric Dimension
 | location = Dagstuhl, Germany
 | publisher = [[Dagstuhl|Schloss Dagstuhl – Leibniz-Zentrum für Informatik]]
 | series = Dagstuhl Seminar Proceedings
 | title = Parameterized Complexity and Approximation Algorithms
 | url = http://drops.dagstuhl.de/opus/volltexte/2010/2499
 | year = 2010| pages = 1–10
 | doi = 10.4230/DagSemProc.09511.3
 | doi-access = free
 }}.
*{{citation|first=P. J.|last=Slater|contribution=Leaves of trees|title=Proc. 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975)|series=Congressus Numerantium|volume=14|pages=549–559|year=1975|publisher=Utilitas Math.|location=Winnipeg|mr=0422062}}.
*{{citation|first=P. J.|last=Slater|title=Dominating and reference sets in a graph|journal=Journal of Mathematical and Physical Sciences|volume=22|issue=4|pages=445–455|year=1988|mr=0966610}}.

[[Category:Graph invariants]]
[[Category:NP-complete problems]]