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 W = \{w_1, w_2,\dots, w_k\} of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the ordered k-tuple r(v|W) = (d(v,w_1), d(v,w_2),\dots,d(v,w_k)), 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 were introduced independently by Slater (1975) and Harary & Melter (1976).

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 n\leq D^{\beta}+\beta for any n-vertex graph with diameter D 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 D^{\beta} such vectors). However, the bound is only achieved for D\leq 3 or \beta=1; the more precise bound n\leq \left(\lfloor 2D/3\rfloor+1\right)^\beta+\beta\sum_{i=1}^{\lceil D/3\rceil}(2i-1)^{\beta-1} is proved by Hernando et al. (2010).

Computational complexity

For any 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. Answering a question posed by Lokshtanov (2010), Hartung & Nichterlein (2013) show that metric dimension 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 (parameterized by the metric dimension) is unlikely to exist.

The metric dimension of an arbitrary n-vertex graph may be approximated in polynomial time to within an approximation ratio of 2\log n 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 \tbinom{n}{2} 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, \log n+\log\log_2 n+1 (Hauptmann, Schmied & Viehmann 2012). This approximation ratio is close to best possible, as under standard complexity-theoretic assumptions a ratio of (1-\epsilon)\log n cannot be achieved in polynomial time for any \epsilon>0 (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)).

Metric dimension is NP-complete (Garey & Johnson 1979) and remains so for bounded-degree planar graphs (Díaz et al. 2012). It is also NP-complete for split graphs, bipartite graphs and their complements, line graphs of bipartite graphs (Epstein, Levin & Woeginger 2012) and unit disk graphs (Hoffmann & Wanke 2012). It 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, 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 (Epstein, Levin & Woeginger 2012).

References

This article is issued from Wikipedia - version of the Tuesday, April 05, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.