Reconstructing Graphs from Subgraph Compositions

We study a generalization of the problem of reconstructing strings from their substring compositions first proposed by Acharya et al. in 2015. This problem is linked to information retrieval from polymer-based data storage systems where the information is read from polymers with tandem mass (MS/MS) spectrometers. Previously the problem has been studied when the polymers are strings/paths. However, polymers allow different structures, which motivates the more general problem of reconstructing graphs from their connected subgraphs compositions. We present some graph classes for which graphs are reconstructable. In particular, we present an infinite subclass of subdivided stars which are reconstructable, allow storing more information than strings, have a simple reconstruction algorithm and structure. Besides positive results, we also give some graph classes where a large number of non-isomorphic labelings yield the same composition multisets.