A very general notion of local constraints is to simply forbid some pairs
of edges from occuring consecutively in a path – what has been called a
path avoiding forbidden transitions (we will also speak of
compatible paths). Finding a compatible path has been proven to be
NP-complete in general [1]}, with a dichotomy theorem
(the tractable case covers in particular properly colored cycles). However, the
question for compatible trails does not seem to have been asked before in
its full generality (despite previous work on Eulerian trails avoiding
forbidden transitions [2]}).
