Complexity Results in Graph Reconstruction

Abstract 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. We show that the problems are rather closely related for all amounts c of deletion: For all c ≥ 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. For all c ≥ 1 and k ≥ 2, \({\rm GI} \equiv^{p}_{iso} {k\textnormal{-}\rm VDC}_c\) and \({\rm GI} \equiv^{p}_{iso} {k\textnormal{-}\rm EDC}_c\). For all c ≥ 1 and k ≥ 2, \({\rm GI} \leq^{l}_{m} {k\textnormal{-}\rm LVD}_c\). In particular, for all c ≥ 1, \({\rm GI} \equiv^{p}_{iso} {2\textnormal{-}\rm LVD}_c\). For all c ≥ 1 and k ≥ 2, \({\rm GI} \equiv^{p}_{iso} {k\textnormal{-}\rm LED}_c\). For many of these, even the c = 1 cases were not known. Similar to the definition of reconstruction numbers vrn ∃ ( G ) [10] and ern ∃ ( G ) (see p. 120 of [17]), we introduce two new graph parameters, vrn ∀ ( G ) and ern ∀ ( G ), and give an example of a family { G n } n ≥ 4 of graphs on n vertices for which vrn ∃ ( G n ) < vrn ∀ ( G n ). For every k ≥ 2 and n ≥ 1, we show 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.

Authors

• Edith Hemaspaandra
• Lane A. Hemachandra
• Stanislaw P. Radziszowski
• Rahul Tripathi

Keywords

No keywords are indexed for this paper.