A similar feature exists in the SPARQL query language as "property paths".
would select pairs of a node x and a descendant y of x, with a path from x to y of "parent" edges having length 1 or more.
The answers to RPQs can consist of endpoint pairs, i.e., pairs of nodes x and y that are connected by some path satisfying the regular expression; or it can consist of the list of all paths satisfying the regular expression.
[2] The evaluation of regular path queries (RPQ), in the sense of returning all endpoint pairs, can be performed in polynomial time.
To do this, for every endpoint pair, we can see the graph database as a finite automaton, also represent the regular path query as a finite automaton, and check if a suitable path exists by checking that the intersection of both languages is nonempty (i.e., solving the emptiness problem), for instance via the product automaton construction.