  Evaluation of regular path queries (RPQs) is a central problem in graph
databases. We investigate the corresponding enumeration problem, that is, given
a graph and an RPQ, enumerate all paths in the graph that match the RPQ. We
consider several versions of this problem, corresponding to different semantics
of RPQs that have recently been considered: arbitrary paths, shortest paths,
simple paths, and trails. Whereas arbitrary and shortest paths can be
enumerated in polynomial delay, the situation is much more intricate for simple
paths and trails. For instance, already the question if a given graph contains
a simple path or trail of a certain length has cases with highly non-trivial
solutions and cases that are long-standing open problems. In this setting, we
study RPQ evaluation from a parameterized complexity perspective. We define a
class of simple transitive expressions that is prominent in practice and for
which we can prove two dichotomy-like results: one for simple paths and one for
trails paths. We observe that, even though simple path semantics and trail
semantics are intractable for RPQs in general, they are feasible for the vast
majority of the kinds of RPQs that users use in practice. At the heart of this
study is a result of independent interest on the parameterized complexity of
finding disjoint paths in graphs: the two disjoint paths problem is W[1]-hard
if parameterized by the length of one of the two paths.
