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

The problem is: how can we determine if there are $\epsilon_1,\ldots,\epsilon_n\in\{-1,+1\}$ such that $$\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? And, if there is a solution, how do 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