7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ "The other student" here :) I was wondering if one could try to direct G and H such that we have a solution for the directed case (A.K.A. that product graph described above is eulerian). Maybe we're lucky and one can find a "good" direction with an LP? $\endgroup$
    – MadTux
    Aug 21, 2020 at 7:00
  • $\begingroup$ Orienting an undirected eulerian graph G to become a directed eulerian graph can be formulated as a b-flow on an arbitrary orientation of G, with b(v) = (outdegree(v) - indegree(v))/2. So at least that LP is integral ... $\endgroup$
    – MadTux
    Aug 21, 2020 at 7:34

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.