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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Optimal, Robust, and Information-Theoretic Graph Reconstruction from Distance Vectors

Rajit Chatterjea
Figshare
Graph Labeling and Dimension Problems
article

Optimal, Robust, and Information-Theoretic Graph Reconstruction from Distance Vectors

Rajit Chatterjea
article en

Abstract

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.

Figshare
Graph Labeling and Dimension Problems
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon