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 for graphs were introduced independently by Template:Harvtxt and Template:Harvtxt, 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.

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| − |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, and thus any tree and its line graph have the same metric dimension.Template:Sfn

Properties

In Template:Harvtxt, it is proved that:

• The metric dimension of a graph Template:Mvar is 1 if and only if Template:Mvar is a path.
• The metric dimension of an Template:Mvar-vertex graph is Template:Math if and only if it is a complete graph.
• The metric dimension of an Template:Mvar-vertex graph is Template:Math if and only if the graph is a complete bipartite graph Template:Math, a split graph $K_s+\overline{K_t}(s\ge 1,t\ge 2)$, or $K_s+(K_1\cup K_t)(s,t\ge 1)$.

Relations between the order, the metric dimension and the diameter

Template:Harvtxt prove the inequality $n\le D^{\beta }+\beta$ for any Template:Mvar-vertex graph with diameter $D$ and metric dimension $\beta$. 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 $\beta$ 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\le 3$ or $\beta =1$; the more precise bound $$n\le {(\lfloor 2D/3\rfloor +1)}^{\beta }+\beta \sum _{i=1}^{\lceil D/3\rceil }(2i-1{)}^{\beta -1}$$ is proved by Template:Harvtxt.

For specific graph classes, smaller bounds can hold. For example, Template:Harvtxt proved that $n\le (\beta D+4)(D+2)/8$ for trees (the bound being tight for even values of Template:Mvar), and a bound of the form $n=O(D^2\beta )$ for outerplanar graphs. The same authors proved that $n\le (D\beta +1{)}^{t-1}$ for graphs with no complete graph of order Template:Mvar as a minor and also gave bounds for chordal graphs and graphs of bounded treewidth. The authors Template:Harvtxt proved bounds of the form $n=O(D{\beta }^2)$ for interval graphs and permutation graphs, and bounds of the form $n=O(D\beta )$ for unit interval graphs, bipartite permutation graphs and cographs.

Computational complexity

Decision complexity

Deciding whether the metric dimension of a graph is at most a given integer is NP-complete.Template:Sfn It remains NP-complete for bounded-degree planar graphs,Template:Sfn split graphs, bipartite graphs and their complements, line graphs of bipartite graphs,Template:Sfn unit disk graphs,Template:Sfn interval graphs of diameter 2 and permutation graphs of diameter 2,Template:Sfn and graphs of bounded treewidth.Template:Sfn

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 Template:Harvtxt, Template:Harvtxt 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^O(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,Template:Sfn and more generally to graphs of bounded tree-length,Template:Sfn 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 Other linear-time algorithms exist for cographs,Template:Sfn chain graphs,Template:Sfn and cactus block graphsTemplate:Sfn (a class including both cactus graphs and block graphs). The problem may be solved in polynomial time on outerplanar graphs.Template:Sfn It may also be solved in polynomial time for graphs of bounded cyclomatic number,Template:Sfn 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",Template:Sfn "max leaf number",Template:Sfn and "modular width".Template:Sfn 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.Template:Sfn

Approximation complexity

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. Template:Sfn In the set cover problem formed from a metric dimension problem, the elements to be covered are the $(\genfrac{}{}{0ex}{}{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$.Template:Sfn This approximation ratio is close to best possible, as under standard complexity-theoretic assumptions a ratio of $(1-ϵ)\log n$ cannot be achieved in polynomial time for any $ϵ>0$.Template:Sfn The latter hardness of approximation still holds for instances restricted to subcubic graphs,Template:Sfn and even to bipartite subcubic graphs.Template:Sfn

References

Bibliography

• Template:Citation
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation
• Template:Citation.
• Template:Citation A1.5: GT61, p. 204.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation
• Template:Citation.
• Template:Citation.
• Template:Citation
• Template:Citation.
• Template:Citation.
• Template:Citation.