Reconstruction in one dimension from unlabeled Euclidean lengths

Let \(G\) be a \(3\)-connected ordered graph with \(n\) vertices and \(m\) edges. Let \(\mathbf{p}\) be a randomly chosen mapping of these \(n\) vertices to the integer range \(\{1, 2,3, \ldots, 2^b\}\) for \(b\ge m^2\). Let \(\ell\) be the vector of \(m\) Euclidean lengths of \(G\)'s edges und...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-06
Main Authors: Connelly, Robert, Gortler, Steven J, Theran, Louis
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Euclidean geometry
Graph theory
Mapping
Reconstruction
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let \(G\) be a \(3\)-connected ordered graph with \(n\) vertices and \(m\) edges. Let \(\mathbf{p}\) be a randomly chosen mapping of these \(n\) vertices to the integer range \(\{1, 2,3, \ldots, 2^b\}\) for \(b\ge m^2\). Let \(\ell\) be the vector of \(m\) Euclidean lengths of \(G\)'s edges under \(\mathbf{p}\). In this paper, we show that, with high probability over \(\mathbf{p}\), we can efficiently reconstruct both \(G\) and \(\mathbf{p}\) from \(\ell\). This reconstruction problem is NP-HARD in the worst case, even if both \(G\) and \(\ell\) are given. We also show that our results stand in the presence of small amounts of error in \(\ell\), and in the real setting, with sufficiently accurate length measurements. Our method combines lattice reduction, which has previously been used to solve random subset sum problems, with an algorithm of Seymour that can efficiently reconstruct an ordered graph given an independence oracle for its matroid.
ISSN:2331-8422