# Complexity of finding a Eulerian path such that the image under a bijection is also a Eulerian path

Problem input: undirected graphs $$G$$, $$H$$ and a bijection $$f: E(G) \to E(H)$$
Question: Is there a Eulerian path $$p: \{1,\dots,|E(G)|\} \to E(G)$$ in $$G$$ such that $$f \circ p$$ is a Eulerian path in $$H$$?

Is this problem in $$P$$, $$NP$$-complete or maybe equivalent to some other well-known problem that isn’t known to be either yet?

The problem turned up as a special case of a more general problem first in the Bachelors thesis of another student last year and now in mine as well (I was improving some of the results of the other thesis). All other cases of the problem are now known to be either NP-hard or solvable in polynomial time, but neither one of us managed to make any progress on that case. On the other hand it feels like a much more "natural" problem than the other cases, so I think we may have missed a simple proof.

If undirected graphs are replaced by directed graphs in the problem statement there is a simple polynomial time algorithm (find a Eulerian path in the graph with vertex set $$V(G)\times V(H)$$ and edge set $$\{((v_1, w_1), (v_2, w_2)) | (v_1, v_2)=e \in E(G), f(e) = (w_1, w_2)\}$$ ignoring isolated vertices). The analogous graph for the undirected case contains 2 edges for each edge in $$G$$, so just finding a Eulerian path is no longer enough.

Posted on Categories proxies