What is the shortest polynomial divisible by $(x-1)(y-1)(x^2y-1)$

$$1-y^3-x^2+y^3x^8+y^4x^2-y^4x^8$$

is divisible by all three brackets, that is seen from three couplings of terms: $(1-y^3)+(y^4x^2-x^2)+(y^3x^8-y^4x^8)$ is divisible by $y-1$, $(1-x^2)+(y^4x^2-y^4x^8)+(y^3x^8-y^3)$ by $x-1$ and $(1-y^4x^8)+(y^4x^2-y^3)+(y^3x^8-x^2)$ by $x^2y-1$. Thus the answer is 6.

It may be easily found by studying the Newton hexagon: its sides and diagonals have prescribed directions.

A simpler answer is given by $x^4y^2 - x^4y - x^2y^2 + x^2 + y - 1=(x+1)f$, where $f$ is the generator of the ideal.

Your general question for $n=1$ (univariate polynomials) is the subject of "Computing sparse multiples of polynomials" by Mark Giesbrecht, Daniel S. Roche, Hrushikesh Tilak:

We consider the problem of finding a sparse multiple of a polynomial. Given f in F[x] of degree d over a field F, and a desired sparsity t, our goal is to determine if there exists a multiple h in F[x] of f such that h has at most t non-zero terms, and if so, to find such an h. When F=Q and t is constant, we give a polynomial-time algorithm in d and the size of coefficients in h. When F is a finite field, we show that the problem is at least as hard as determining the multiplicative order of elements in an extension field of F (a problem thought to have complexity similar to that of factoring integers), and this lower bound is tight when t=2.

There are some talk slides from 2010 by Roche here which state on the last slide the multivariate case as an open problem.