What is the complexity of the following problem ($\in$ P? NP-hard?):
Input: a directed acyclic graph $D=(V,E)$, a set of backward edges $E'\subset V\times V$, and two distinct nodes $s$ and $t$.
Question: Let $G=(V,E\cup E')$ denote the graph formed by adding to $D$ the edges from $E'$. Is there a simple path from $s$ to $t$ in $G$ that uses at least one backward edge?
Note: 0) A simple path is a path in which no vertex is repeated, A backward edge is an edge that contradicts the partial order implied by the DAG. 1) the problem is easy if we request the simple path to use exactly one backward edge (or a constant number) by trivial reduction to the disjoint path problem, which admits a simple PTime solution in DAGs (Perl and Shiloach, JACM'78) 2) the disjoint path problem is NP-complete in general graphs (Fortune et al., TCS'80).