Complexity Results in Graph Reconstruction
<|reference_start|>Complexity Results in Graph Reconstruction: We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts $c \geq 1$ of deletion:   1) $GI \equiv^{l}_{iso} VDC_{c}$, $GI \equiv^{l}_{iso} EDC_{c}$, $GI \leq^{l}_{m} LVD_c$, and $GI \equiv^{p}_{iso} LED_c$.   2) For all $k \geq 2$, $GI \equiv^{p}_{iso} k-VDC_c$ and $GI \equiv^{p}_{iso} k-EDC_c$.   3) For all $k \geq 2$, $GI \leq^{l}_{m} k-LVD_c$.   4)$GI \equiv^{p}_{iso} 2-LVC_c$.   5) For all $k \geq 2$, $GI \equiv^{p}_{iso} k-LED_c$.   For many of these results, even the $c = 1$ case was not previously known.   Similar to the definition of reconstruction numbers $vrn_{\exists}(G)$ [HP85] and $ern_{\exists}(G)$ (see page 120 of [LS03]), we introduce two new graph parameters, $vrn_{\forall}(G)$ and $ern_{\forall}(G)$, and give an example of a family $\{G_n\}_{n \geq 4}$ of graphs on $n$ vertices for which $vrn_{\exists}(G_n) < vrn_{\forall}(G_n)$. For every $k \geq 2$ and $n \geq 1$, we show that there exists a collection of $k$ graphs on $(2^{k-1}+1)n+k$ vertices with $2^{n}$ 1-vertex-preimages, i.e., one has families of graph collections whose number of 1-vertex-preimages is huge relative to the size of the graphs involved.<|reference_end|>
@article{hemaspaandra2004complexity,
    title={Complexity Results in Graph Reconstruction},
    author={Edith Hemaspaandra, Lane A. Hemaspaandra, Stanislaw P. Radziszowski,
  Rahul Tripathi},
    journal={arXiv preprint arXiv:cs/0410021},
    year={2004},
    number={URCS-TR-2004-852},
    archivePrefix={arXiv},
    eprint={cs/0410021},
    primaryClass={cs.CC cs.DM}
}