Reducing Sensor Requirements by Relaxing the Network Metric Dimension

Source localization in graphs aims to identify the origin of events like epidemics or misinformation by leveraging structural graph properties. A key tool is the metric dimension, which measures the minimum number of sensors needed to uniquely identify all vertices based on their distances. However, this often involve placing a large number of sensors. Hence, we propose a relaxed version of the metric dimension, by allowing vertices at a distance less than k to have identical distances to the sensors. This relaxation lowers sensor requirements while preserving practical resolution. Our contributions include an analysis of this k -relaxed metric dimension in both deterministic and random trees, highlighting the role of graph structure in sensor placement. Numerical experiments on various graphs show the relaxed metric dimension is much smaller than the traditional one.