We are given a polynomial $$P_n(x):=a_nx^n + a_{n-1}x^{n-1}+\cdots+a_1x+a_0$$ with real coefficients.

Questions.

$\boldsymbol{(i)}$ How can we determine if there are $\epsilon_1,\ldots,\epsilon_n\in\{-1,+1\}$ such that $$P_n(x;\pmb{\epsilon}):=\epsilon_n a_nx^n + \epsilon_{n-1} a_{n-1}x^{n-1}+\cdots+\epsilon_1 a_1x+a_0$$ has only real roots? Here $\pmb{\epsilon}=(\epsilon_1,\dots,\epsilon_n)$.

$\boldsymbol{(ii)}$ If there is a solution, how can we find it?

Obviously an exhaustive search is hopelessly slow. This question might just possibly (on a good day) be of relevance to a problem on graph polynomials.