Optimal, Robust, and Information-Theoretic Graph Reconstruction from Distance Vectors
A finite connected graph can be represented by the distances of its vertices to a selected set of landmarks. Metric dimension asks for the smallest landmark set that gives every vertex a distinct distance vector. Link dimension strengthens this requirement: the distance vectors must determine the entire adjacency relation, not merely identify the vertices. We develop an optimization and uncertainty framework for this reconstruction problem. First, we give an exact binary integer-programming formulation of link dimension. The constraints require every edge to be witnessed by a unit distance difference and every non edge to be witnessed by a distance difference of at least two. Second, after fixing an initial resolving set, we reduce the selection of additional landmarks to set cover and obtain the standard harmonic approximation guarantee for this restricted augmentation problem. Third, we establish a deterministic stability theorem for bounded additive measurement errors. A threshold of 3/2 recovers the exact adjacency relation whenever the error in each landmark-to-vertex measurement is less than 1/4. Fourth, we formulate adaptive landmark selection as Bayesian experimental design. The information gained by a landmark is a conditional mutual information; it is nonnegative and yields a monotone information objective, although submodularity is not asserted without additional assumptions.Finally, exhaustive subset enumeration provides reproducible small-instance checks for paths, cycles, complete graphs, stars, wheels, and rectangular grids. The paper distinguishes exact theorems from algorithmic formulations and computational observations. The resulting framework connects graph reconstruction to combinatorial optimization, approximation algorithms, robust inference, and information theory.
Authors
- Rajit Chatterjea (ORCID: https://orcid.org/0009-0004-6742-3101)
Publication Details
- Journal
- Figshare
- Published
- 2026-11-17
- DOI
- https://doi.org/10.6084/m9.figshare.35033842
- Primary Topic
- Graph Labeling and Dimension Problems
- Type
- article
- Field-Weighted Citation Impact
- 0.00