Shotgun Assembly of Graphs

We will present some results and some open problems related to shotgun assembly of graphs for random generating models.Shotgun assembly of graphs is the problem of recovering a random graph or a randomly labelled graphs from small pieces.
This problem generalizes the theoretically elegant and practically important problem of shotgun assembly of DNA sequences.
The general problem of shotgun assembly presents novel problems in random graphs, percolation, and random constraint satisfaction problems.
Based on joint works with Nathan Ross, with Nike Sun and with Charles Bordenave and Uri Feige.