Given functions $h,k:\Bbb R\to \Bbb R$, is it possible to determine whether $f,g:\Bbb R\to\Bbb R$ exist so that $g\circ f=h$ and $f\circ g=k$?
This is an addendum to the very brilliant analysis already given by orangeskid. In light of their analysis, I'll provide some easy facts about topological conjugation over the reals.
Claim 1: If $f:\mathbf{R}\to\mathbf{R}$ is strictly increasing, continuous, unbounded above and below, and such that $f(0)>0$, then there is a strictly increasing and continuous $\varphi:\mathbf{R}\to\mathbf{R}$ such that $\varphi(0)=0$ and $f\circ\varphi(x)=\varphi(x+1)$. Moreover if $f(x)>x$ for all $x\in\mathbf{R}$, then $\varphi$ is also unbounded above and below.
Proof: Since we know $f(0)>0$, let $\varphi(a)=af(0)$ for all $a\in[0,1)$. We will define the rest of $\varphi$ by extending in the obvious fasion: $\varphi(x)=f^{(\lfloor x\rfloor)}\circ\varphi\left(x-\lfloor x\rfloor\right)$, where $f^{(-)}$ denotes functional iteration, as $f$ is bijective. Clearly the next thing to do is to check that this fits the requirements:
We forced $f\circ\varphi(x)=\varphi(x+1)$ by contsruction, so that is done.
To check continuity, note that $f^{(\lfloor x\rfloor)}$ is always continuous, so by functional composition $\varphi$ is continuous over $\mathbf{R}\smallsetminus\mathbf{Z}$. To check continuity on $\mathbf{Z}$, it suffices to check continuity as $x\to 1^-$. For this note that $$\varphi(1)=f\circ\varphi(0)=f(0)=\lim_{x\to 1^-}\varphi(x)$$
To see $\varphi$ is strictly increasing, note that $f^{(\lfloor x\rfloor)}$ is strictly increasing by assumption and that $\varphi$ is strictly increasing over $[0,1)$, so we get $\varphi$ is strictly increasing over all intervals $[z,z+1)$ where $z\in\mathbf{Z}$. However $\varphi$ is continuous, and so it is strictly increasing over $\mathbf{R}$.
Now to check the "moreover" part.
- If $\varphi$ is not unbounded, then by monotone convergence, there is a bound $M=\lim_{x\to A}\varphi(x)$ where $A\in\pm\infty$. However, as $f$ is continuous, $$f(M)=f\left(\lim_{x\to A}\varphi(x)\right)=\lim_{x\to A}f(\varphi(x))=\lim_{x\to A}\varphi(x+1)=M$$ This contradicts that $f(x)>x$ for all $x\in\mathbf{R}$.
Claim 2: If $f:[0,\infty)\to[0,\infty)$ is strictly increasing and continuous, such that $f(0)=0$ and $f(x)>x$ for all $x>0$, then there is a strictly increasing, continuous, and unbounded $\varphi:[0,\infty)\to[0,\infty)$ such that $\varphi(0)=0$ and $f\circ\varphi(x)=\varphi(2x)$.
Proof: Let $g:\mathbf{R}\to\mathbf{R}$ be given by $g(x)=\log_2 f(2^x)$. By Claim 1, there is some $\psi:\mathbf{R}\to\mathbf{R}$ that is strictly increasing, continuous, unbounded above and below, and such that $g\circ\psi(x)=\psi(x+1)$. Then let $\varphi(x)=2^{\psi(\log_2 x)}$, so we see that $$\varphi(2x)=2^{\psi(1+\log_2 x)}=2^{g\circ\psi(\log_2 x)}=f(2^{\psi(\log_2 x)})=f\circ\varphi(x)$$
Claim 3: If $f:\mathbf{R}\to\mathbf{R}$ is strictly increasing, continuous, and has exactly one unstable fixed point $c$, that is, $f(x)>x$ for all $x>c$ and $f(x)<x$ for all $x<c$, then there is an increasing homeomorphism $\varphi:\mathbf{R}\to\mathbf{R}$ such that $\varphi^{-1}\circ f\circ \varphi(x)=2x$.
Proof: Let $g:\mathbf{R}\to\mathbf{R}$ be given by $g(x)=f(x+c)-c$, thus $g$ shares all properties with $f$ except $0$ is the fixed point of $g$. By Claim 2, there are increasing homeomorphisms $\varphi_{\pm}:[0,\infty)\to[0,\infty)$ such that $\varphi_{\pm}(0)=0$, and moreover both $\varphi_+^{-1}\circ g\circ\varphi_+(x)=2x$ and $\varphi_-^{-1}(-g(-\varphi_-(x)))=2x$. Let $\psi:\mathbf{R}\to\mathbf{R}$ be given by $$\psi(x)=\begin{cases} \varphi_+(x)&\text{if }x\ge 0\\ -\varphi_-(-x)&\text{if }x<0 \end{cases}$$ Then it is not hard to see that $\psi$ is an increasing homeomorphism such that $\psi^{-1}\circ g\circ\psi(x)=2x$. Finally let $\varphi:\mathbf{R}\to\mathbf{R}$ be given by $\varphi(x)=\psi(x)+c$, so then $$2x=\varphi^{-1}(\psi(2x)+c)=\varphi^{-1}(g\circ\psi(x)+c)=\varphi^{-1}\circ f\circ\varphi(x)$$
As a corollary, note that both $x^3+1$ and $x^3+2$ satisfies Claim 3, so both are conjugate to $2x$.
Also note that it is completely possible to modify the proof such that both $x^3+1$ and $x^3+2$ are conjugate to $2x$ via a homeomorphism that is smooth on all of $\mathbf{R}$ except at the fixed point.
This is unavoidable:
Added Claim 4: Consider the two linear functions $f(x)=2x$ and $g(x)=4x$. Let $\varphi:\mathbf{R}\to\mathbf{R}$ be any homeomorphism such that $\varphi\circ f=g\circ\varphi$. Then $\varphi$ cannot be continuously twice differentiable at $0$.
Proof: Assuming not, then by Taylor's theorem we have $$\varphi(x)=ax+bx^2+h(x)\cdot x^2$$ where $h$ is continuous at $h(0)=0$. Then by expanding on $\varphi\circ f=g\circ\varphi$, we eventually get $$h(2x)-h(x)=\frac{a}{2x}$$ Taking the limit $x\to 0$ on both sides, we see that $a=0$, and $h(2x)=h(x)$. However the continuity of $h$ at $0$ implies that $h$ is identically $0$, meaning that $\varphi(x)=bx^2$, and $\varphi$ cannot be a homeomorphism.
If $h= g\circ f$ and $k= f\circ g$, one of the $h,k$ is surjective, and the other injective, then $f$, $g$, $h$, $k$ are all bijective and $$k = f\circ h \circ f^{-1}$$, that is $h$, $k$ are conjugate. Conversely, if $h$, $k$ are conjugate, then you can find $f$, and then $g$. Now, the conjugation is an equivalence relation.
Now in our example $h(x) = x^3+1$, $k(x) = (x+1)^3 + 1$, so $k(x-1) + 1 = x^3+2$, a conjugate of $k$. So now we want to see whether $h_1(x) = x^3+1$ and $h_2(x) =x^3+2$ are conjugate. Note that both have a unique fixed point $\xi_1$, $\xi_2$, and for $x> \xi_i$ we have $h_i^{n}(x) \to \infty$ as $n\to \infty$, $h_i^{n}(x) \to \xi_i$, as $n\to -\infty$, while for $x< \xi_i$, we have $h_i^{n}(x) \to -\infty$ as $n\to \infty$, $h_i^{n}(x) \to \xi_i$, as $n\to -\infty$. Therefore, all the orbits of $h_i$ -except the one containing the fixed point- are infinite. So there exists a bijection $\phi\colon \mathbb{R}\to \mathbb{R}$ such that $h_2= \phi\circ h_1\circ \phi^{-1}$. It is clearly not unique, so a nice $\phi$ would be desired. Note that $\phi$ takes the fixed point of $h_1$ to the fixed point of $h_2$.
It appears that both $h_1$, $h_2$ behave like the map $x\to 2 x$. Are they topologically conjugate to it? Note that $l(x) = 2x$ is part of a $1$-parameter group of diffeomorphism of $\mathbb{R}$, $(t,x)\mapsto 2^{t}\cdot x$. If $h_1$, $h_2$ are conjugate to $l$, then they are also each part of a $1$-parameter group of homeomorphisms of $\mathbb{R}$. In particular, there exists $\psi$ a homeomorphism of $\mathbb{R}$ such that $\psi\circ \psi(x) = x^3+1$. What would be such a homeomorphism?
$\bf{Added:}$ The case where both $k$, $k$ are bijections is simpler, it reduces to the question of when two maps are conjugate under a bijection. They are if and only if the "graph" of the maps are isomorphic, where the graph consists of vertices $x$, and edges $(x, h(x))$. For bijections, their cycle structure has to be the same.
Consider for instance the maps $x\mapsto 2 x$, and $x\mapsto 4 x$. They are conjugate under the bijection $x\mapsto x^{2_+}\colon = x^2 \operatorname{sign} x$. The maps $x\mapsto 2x$, and $x\mapsto 3x$ are conjugate under the map $x\mapsto x^{\log_2 3_+}$.