Polygon within polygon generalization problem
I don't know how your polygons look, but perhaps a simplified version of the Ramer–Douglas–Peucker algorithm is enough:


for each convex part, calculate the area $A_j$ of of the triangles $P_i P_{i+1} P_{i+2}$ formed by three consecutive points;
for each concave part, calculate the area $B_k$ of of the two triangles $P_i P'_i P_{i+1}$ and $P_{i+1} P'_{i+2} P_{i+2}$ formed by the extension of the two points $P_i, P_{i+2}$ and the middle point $P_{i+1}$
calculate the $min\{A_j,B_k\}$ and delete the corresponding point (and shift points if the operation is done on the concave part);
loop until $n-m$ points have been deleted.



The border of the polygon ($A_j$ green triangles, $B_k$ red triangles). On the right, the border after the elimination of two points.

For more complex algorithms you can search for "polygon generalization techniques" though your first condition (points in A are contained in B) implies some additional scaling operations.