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. We show that the problems are rather closely related for all amounts c of deletion: 1. For all c ≥ 1, GI ≡_(iso)~l VDC_C, GI ≡_(iso)~l EDC_C, GI ≤_m~l LVD_C, and GI ≡_(iso)~p LED_C. 2. For all c ≥ 1 and k ≥ 2, GI ≡_(iso)~p k-VDC_c and GI ≡_(iso)~p k-EDC_c. 3. For all c ≥ 1 and k ≥ 2, GI ≤_m~l k-LVD_c. In particular, for all c ≥ 1, GI ≡_(iso)~p 2-LVD_c. 4. For all c ≥ 1 and k ≥ 2, GI ≡_(iso)~p k-LED_c. For many of these, even the c = 1 cases were not known. Similar to the definition of reconstruction numbers vrn_(" exist ")(G) and ern_(" exist ")(G) (see p. 120 of), we introduce two new graph parameters, vrn(any)(G) and ern_(any)(G), and give an example of a family {G_n}_n≥4 of graphs on n vertices for which vrn_(" exist ")(G_n) < vrn_(any)(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.