ON THE COMPLEXITY OF GRAPH RECONSTRUCTION

In the wake of the resolution of the four-color conjecture, the graph reconstruction conjecture has emerged as one focal point of graph theo ry. This paper considers the computational complexity of decision prob lems (DECK CHECKING and LEGITIMATE DECK), construction problems (PREIM AGE CONSTRUCTION), and counting problems (PREIMAGE COUNTING) related t o the graph reconstruction conjecture. We show that: 1. GRAPH ISOMORPH ISM less-than-or-equal-to m(l) LEGITIMATE DECK, and 2. GRAPH ISOMORPHI SM =iso(l) DECK CHECKING. Relatedly, we display the first natural GI-h ard NP set lacking obvious padding functions. Finally, we show that LE GITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE counting are solvab le in polynomial time for graphs of bounded degree, partial k-trees fo r any fixed k, and graphs of bounded genus, in particular for planar g raphs.