Reconstruction in one dimension from unlabeled Euclidean lengths

arXiv2007.06550MaRDI QIDQ6344993FDOQ6344993

Authors: Robert Connelly, Steven J. Gortler, Louis Theran 

Publication date: 13 July 2020

Abstract: Let $G$ be a $3$-connected graph with $n$ vertices and $m$ edges. Let $mathbfp$ be a randomly chosen mapping of these $n$ vertices to the integer range $[\mathrm{1..}{2}^b]$ for $bge{m}^2$. Let $mathbfl$ be the vector of $m$ Euclidean lengths of $G$'s edges under $mathbfp$. In this paper, we show that, WHP over $mathbfp$, we can efficiently reconstruct both $G$ and $mathbfp$ from $mathbfl$. In contrast to this average case complexity, this reconstruction problem is NP-HARD in the worst case. In fact, even the labeled version of this problem (reconstructing $mathbfp$ given both $G$ and $mathbfl$) is NP-HARD. We also show that our results stand in the presence of small amounts of error in $mathbfl$, and in the real setting with approximate length measurements. Our method is based on older ideas that apply lattice reduction to solve certain SUBSET-SUM problems, WHP. We also rely on an algorithm of Seymour that can efficiently reconstruct a graph given an independence oracle for its matroid.

This page was built for publication: Reconstruction in one dimension from unlabeled Euclidean lengths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6344993)