A1 Refereed original research article in a scientific journal
Reconstructing graphs with subgraph compositions
Authors: Dailly, Antoine; Lehtilä, Tuomo
Publisher: Elsevier BV
Publication year: 2026
Journal: Discrete Applied Mathematics
Volume: 390
First page : 198
Last page: 219
ISSN: 0166-218X
eISSN: 1872-6771
DOI: https://doi.org/10.1016/j.dam.2026.04.023
Publication's open availability at the time of reporting: Open Access
Publication channel's open availability : Partially Open Access publication channel
Web address : https://doi.org/10.1016/j.dam.2026.04.023
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/523237668
Self-archived copy's licence: CC BY NC
Self-archived copy's version: Publisher`s PDF
We generalize the problem of reconstructing strings from their substring compositions first introduced by Acharya et al. in 2015 motivated by polymer-based advanced data storage systems utilizing mass spectrometry. Namely, we see strings as labeled path graphs, and as such try to reconstruct labeled graphs. For a given integer t, the subgraph compositions contain either vectors of labels for each connected subgraph of order t (t-multiset-compositions) or the sum of all labels of all connected subgraphs of order t (t-sum-composition). We ask whether, given a graph with a known structure and an oracle that can be queried for compositions, one can reconstruct the labeling of the graph. If it is possible, then the graph is reconstructible; otherwise, it is confusable, and two labeled graphs with the same compositions are called equicomposable. We prove that reconstructing through a brute-force algorithm is wildly inefficient, before giving methods for reconstructing several graph classes using as few compositions as possible. We also give negative results, finding the smallest confusable graphs and trees, as well as families with a large number of equicomposable non-isomorphic graphs. An interesting result occurs when twinning one leaf of a path: some paths are confusable, creating a twin out of a leaf sees the graph alternating between reconstructible and confusable depending on the parity of the path, and creating a false twin out of a leaf makes the graph reconstructible using only sum-compositions in all cases.
Downloadable publication This is an electronic reprint of the original article. |  |
