  Provided a complete set of putative $k$-body reductions of a multipartite
quantum state, can one determine if a joint state exists? We derive necessary
conditions for this to be true. In contrast to what is known as the quantum
marginal problem, we consider a setting where the labeling of the subsystems is
unknown. The problem can be seen in analogy to Ulam's reconstruction conjecture
in graph theory. The conjecture - still unsolved - claims that every graph on
at least three vertices can uniquely be reconstructed from the set of its
vertex-deleted subgraphs. When considering quantum states, we demonstrate that
the non-existence of joint states can, in some cases, already be inferred from
a set of marginals having the size of just more than half of the parties. We
apply these methods to graph states, where many constraints can be evaluated by
knowing the number of stabilizer elements of certain weights that appear in the
reductions. This perspective links with constraints that were derived in the
context of quantum error-correcting codes and polynomial invariants. Some of
these constraints can be interpreted as monogamy-like relations that limit the
correlations arising from quantum states. Lastly, we provide an answer to
Ulam's reconstruction problem for generic quantum states.
