2018/06/27 by Vietz, Duygu, Hoffmann, Stefan, Wanke, Egon
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1806.10389
A vertex set U ⊆ V of an undirected graph G=(V,E) is a resolving set for G, if for every two distinct vertices u,v ∈ V there is a vertex w ∈ U such that the distances between u and w and the distance between v and w are different. The Metric Dimension of G is the size of a smallest resolving set for G. Deciding whether a given graph G has Metric Dimension at most k for some integer k is well-known to be NP-complete. Many research has been done to understand the complexity of this problem on restricted graph classes. In this paper, we decompose a graph into its so called extended biconnected components and present an efficient algorithm for computing the metric dimension for a class of graphs having a minimum resolving set with a bounded number of vertices in every extended biconnected component. Further we show that the decision problem METRIC DIMENSION remains NP-complete when the above limitation is extended to usual biconnected components.