Complexity Results in Graph Reconstruction

Original · EN

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 ≥ 1 of deletion: 1) GI ≡ˡiso VDCc, GI ≡ˡiso EDCc, GI ≤ˡₘ LVDc, and GI ≡ᵖiso LEDc. 2) For all k ≥ 2, GI ≡ᵖiso k-VDCc and GI ≡ᵖiso k-EDCc. 3) For all k ≥ 2, GI ≤ˡₘ k-LVDc. 4)GI ≡ᵖiso 2-LVCc. 5) For all k ≥ 2, GI ≡ᵖiso k-LEDc. For many of these results, even the c = 1 case was not previously known. Similar to the definition of reconstruction numbers vrn∃(G) [HP85] and ern∃(G) (see page 120 of [LS03]), we introduce two new graph parameters, vrn∀(G) and ern∀(G), and give an example of a family {Gₙ}ₙ ≥ ₄ of graphs on n vertices for which vrn∃(Gₙ) < vrn∀(Gₙ). For every k ≥ 2 and n ≥ 1, we show that there exists a collection of k graphs on (2ᵏ⁻¹+1)n+k vertices with 2ⁿ 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.