Reconstructibility

Reconstructibility is a property of mathematical objects describing whether the original object can be uniquely determined from a collection of derived data, rather than from direct observation of the object itself. In this sense, an object is reconstructible if its essential structure is identifiable from the related subobjects, invariants, or observations that are systematically related to it.

In graph theory, reconstructibility is most often discussed through the reconstruction problem. For a graph G with vertex set V, its deck is the multiset of graphs obtained by deleting each vertex in turn (G − v for v in V), up to isomorphism. A graph is reconstructible if it is uniquely determined, up to isomorphism, by its deck. The Reconstruction Conjecture, formulated independently by Kelly and Ulam in 1942, posits that every graph with at least three vertices is reconstructible. The conjecture remains open in general, though many graph classes are known to be reconstructible, and the deck often suffices to distinguish most graphs in practice.

Outside graph theory, reconstructibility appears in various disciplines where objects are recovered from partial information. In algebra, model theory, and data analysis, one speaks of reconstructing a structure from substructures, invariants, or partial measurements. The notion underpins ideas of identifiability and data sufficiency: what partial data are needed to recover the original object uniquely?

Limitations and variations abound. Reconstructibility may depend on the category of objects under consideration, the type of derived data allowed, and the notion of equivalence used (e.g., isomorphism).