Abstract
Let G be a 3-connected ordered graph with n vertices and m edges. Let be a randomly chosen mapping of these n vertices to the integer range {1, 2, 3, ... 2b} for b β₯ m2. Let be the vector of m Euclidean lengths of Gβs edges under p. In this paper, we show that, with high probability over p, we can efficiently reconstruct both G and p from π. This reconstruction problem is NP-HARD in the worst case, even if both G and π are given. We also show that our results stand in the presence of small amounts of error in π, 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.
Original language | English |
---|---|
Number of pages | 27 |
Journal | Combinatorica |
Volume | First online |
Early online date | 11 Jul 2024 |
DOIs | |
Publication status | E-pub ahead of print - 11 Jul 2024 |
Keywords
- Rigidity theory
- Distance geometry
- Graph realization problem