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.
Contents
Detailed definition
For an ordered subset
Trees
Slater (1975) 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.
Properties
In Chartrand et al. (2000), it is proved that:
Khuller, Raghavachari & Rosenfeld (1996) prove the inequality
Decision complexity
Deciding whether the metric dimension of a graph is at most a given integer is NP-complete (Garey & Johnson 1979). It remains NP-complete for bounded-degree planar graphs (Díaz et al. 2012), split graphs, bipartite graphs and their complements, line graphs of bipartite graphs (Epstein, Levin & Woeginger 2012), unit disk graphs (Hoffmann & Wanke 2012), interval graphs of diameter 2 and permutation graphs of diameter 2 (Foucaud et al. 2016).
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 fixed-parameter tractable (for the natural parameter k, the solution size). Answering a question posed by Lokshtanov (2010), 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 nO(k) 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 fixed-parameter tractable when restricted to interval graphs (Foucaud et al. 2016), and more generally to graphs of bounded tree-length (Belmonte et al. 2015), such as chordal graphs, permutation graphs 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 (Slater 1975; Harary & Melter 1976). The problem may be solved in polynomial time on outerplanar graphs (Díaz et al. 2012), on cographs (Epstein, Levin & Woeginger 2012) and on chain graphs (Fernau et al. 2015). It may also be solved in polynomial time for graphs of bounded cyclomatic number (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" (Hartung & Nichterlein 2013) and "max leaf number" (Eppstein 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 graphs (Belmonte et al. 2015).
Approximation complexity
The metric dimension of an arbitrary n-vertex graph may be approximated in polynomial time to within an approximation ratio of