for any -vertex graph with diameter 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 (there are precisely such vectors). However, the bound is only achieved for or ; the more precise bound is proved by . For specific graph classes, smaller bounds can hold. For example, proved that for trees (the bound being tight for even values of ), and a bound of the form for outerplanar graphs. The same authors proved that for graphs with no complete graph of order as a minor and also gave bounds for chordal graphs and graphs of bounded treewidth. The authors proved bounds of the form for interval graphs and permutation graphs, and bounds of the form 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. It remains NP-complete for bounded-degree planar graphs, split graphs, bipartite graphs and their complements, line graphs of bipartite graphs, unit disk graphs, interval graphs of diameter 2 and permutation graphs of diameter 2, and graphs of bounded treewidth. 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 , 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, and more generally to graphs of bounded tree-length, 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, chain graphs, and cactus block graphs (a class including both cactus graphs and block graphs). The problem may be solved in polynomial time on outerplanar graphs. It may also be solved in polynomial time for graphs of bounded cyclomatic number,