This is in some ways a refinement of this question about specific maps. That got me wondering about the question of topological conjugacy of polynomials by polynomial maps: if we have polynomials $f, g\in\mathbb{Z}[x]$, is it decidable whether there's a polynomial $h\in\mathbb{Z}[x]$ with $f\circ h=h\circ g$? There are obvious conditions; $f$ and $g$ have to have the same degree, and the leading coefficients have to satisfy some specific relations. But it's not clear to me what can be said above and beyond that; for instance, if such an $h$ exists, must there be one (or all) with $\deg(h)\leq\deg(f)$? Does it have to be the case that there's some polynomial $j$ such that $f = h\circ j$ and $g=j\circ h$? This would obviously imply the above, and by the answers to this question it would seem to imply decidability (though non-trivially, since representing the roots of an arbitrary polynomial is challenging; there are computational bounds and procedures that can handle this, though). I'd also be curious as to whether any of the answers are different over $\mathbb{Q}[x]$, though in this particular case I would expect that 'clearing denominators' makes that relatively straightforward.
(I also kind of want to ask the same question about rational functions rather than just polynomials, but that seems well beyond reach...)