Complexity of finding semi-ordered Eulerian tours in a 4-regular graph
The SOET problem is NP-Complete as we show in the following paper:

Axel Dahlberg, Jonas Helsen, Stephanie Wehner, How to transform graph states using single-qubit operations: computational complexity and algorithms, 
 CoRR abs/1805.05306 (2018).

See Corollary 3.4.1