Summary: We investigate the inverse protein folding (IPF) problem under the canonical model on 3D and 2D lattices. In this problem, we are given a contact graph $G=(V,E)$ of a protein sequence that is embeddable in a 3D (respectively, 2D) lattice and an integer $1\le K\le|V|$. The goal is to find an induced subgraph of $G=(V,E)$ of a protein sequence that is embeddable in a 3D) lattice and an integer $1\le K\le|V|$. The goal is to find an induced subgraph of $G$ of at most $K$ vertices with the maximum number of edges. We prove the following results: An earlier proof of NP-completeness of the IPF problem on 3D lattices of {\it W. E. Hart} [On the computational complexity of sequence design problems. Proc. First Ann. Int. Conf. Comput. Molecular Biol. 1997, 128‒136 (1997)] is based on the NP-completeness of the IPF problem on 2D lattices. However, the reduction was not correct and we show that the IPF problem for 2D lattices can be solved in $O(K|V|)$ time. But, we show that the IPF problem on 3D lattices is indeed NP-complete by a providing a different reduction from a different NP-complete problem. We design a polynomial-time approximation scheme for the IPF problem on 3D lattices using the shifted slice-and-dice approach [see {\it P. Berman, B. DasGupta} and {\it S. Muthukrishnan}, Approximation algorithms for MAX-MIN tiling. J. Algorithms 47, No. 2, 122‒134 (2003; Zbl 1045.68149); {\it D. Hochbaum}, Approximation algorithms for NP-hard problems. (1997)] thereby improving the previous best polynomial-time approximation algorithm which had a performance ratio of 1/2 [{\it W. E. Hart}, op. cit.]