The existence of a rainbow path is equivalent to the existence of a rainbow trail between two vertices.

Alternating directed trails for a perfect matching – with the
right definition of the latter in a directed graph – are a special case of
properly colored directed trail, so the linear algorithm mentioned in the
penultimate row applies. However, NP-hardness works the other way around
(while membership in NP is always trivial here): our result on alternating
directed paths is slightly stronger than the one on properly colored paths
in [1]} (though we derive the former quite easily
from the latter).
