2023/02/12 by Paul Gutkovich, Gutkovich, Paul, Zi Song Yeoh +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2302.05960
openalex publication_date 2023/02/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G=(V,E) be a simple, unweighted, connected graph. Let d(u,v) denote the distance between vertices u,v. A resolving set of G is a subset S of V such that knowing the distance from a vertex v to every vertex in S uniquely identifies v. The metric dimension of G is defined as the size of the smallest resolving set of G. We define the k-truncated resolving set and k-truncated metric dimension of a graph similarly, but with the notion of distance replaced with dk(u,v) := min(d(u,v),k+1). In this paper, we demonstrate that computing k-truncated dimension of trees is NP-Hard for general k. We then present a polynomial-time algorithm to compute k-truncated dimension of trees when k is a fixed constant.