Complexity results in graph reconstruction (Q867853)

This paper takes a look at the reconstruction problem mainly from the point of view of space and time complexity, in particular the relative complexity of the graph isomorphism problem and variants of the legitimate deck problem. The authors extend these variants to the situations where \(c\geq1\) vertices or edges are deleted and also where only a subdeck of the full (alleged) deck is given. For example, if LED denotes the problem of determining whether a given set of graphs is the legitimate edge-deck of some graph, then \(k\text{-LED}_c\) denotes the variant in which \(c\) edges are removed and only \(k\) subgraphs from the full deck are given. Various results are given, for example, that the graph isomorphism problem is polynomial-time isomorphic to \(k\text{-LED}_c\). In the last part of the paper the authors consider reconstruction numbers. This is basically the problem of determining how few subgraphs from the deck are required to reconstruct a graph. Strengthening a result of \textit{R. M. Bryant} [J. Comb. Theory 11, 139--141 (1971; Zbl 0196.27402)] they show that, for all \(k\geq2\) and \(n\geq1\), there is a partial deck of \(k\) endvertex-deleted subgraphs on \((2^{k-1}+1)n+k\) vertices with at least \(2^n\) graphs having all of these subgraphs in their deck. This paper is highly recommended to anyone interested in graph reconstruction from the computational point of view.