Journal article
Shotgun Assembly of Labeled Graphs
E Mossel, N Ross
IEEE Transactions on Network Science and Engineering | IEEE COMPUTER SOC | Published : 2019
Abstract
We consider the problem of reconstructing graphs or labeled graphs from neighborhoods of a given radius $r$r. Special instances of this problem include the well-known: DNA shotgun assembly; the lesser-known: neural network reconstruction; and a new problem: assembling random jigsaw puzzles. We provide some necessary and some sufficient conditions for correct recovery both in combinatorial terms and for some generative models including random labelings of lattices, ErdÅ's-Rényi random graphs, and a random jigsaw puzzle model. Many open problems and conjectures are provided.
Grants
Awarded by Simons Foundation
Funding Acknowledgements
E.M. would like to acknowledge the support of the following grants: US National Science Foundation grants DMS 1106999 and CCF 1320105, DOD ONR grant N00014-14-1-0823, and grant 328025 from the Simons Foundation. N. R. received support from ARC grant DP150101459 and thanks Aslan Tchamkerten for helpful discussions about DNA shotgun assembly. We thank James Lee for suggesting the terminology "jigs", Chenchao Chen for helpful comments, and reviewers.