# Simple path on dag with backward edges

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).

• This is surely not optimal, but it is enough to show that your problem is in P (unless I misunderstood something): let $e_1,...,e_m$ be the edges of $E$; apply a shortest path algorithm from $s$ to $t$ to the graph $G_i = (V, E' \cup \bigcup_{j=1}^i \{ e_j \} )$ for $i = 1,2,...,m$. In other words keep adding an edge picked from $E$ to the graph $G' = (V, E')$ until you find a path from $s$ to $t$. Apr 16, 2015 at 21:17
• Marzio: but what if the path you find uses only edges in $E$, and none in $E'$? There might still exist a different path that also includes an edge of $E'$. Apr 17, 2015 at 4:55
• What's very annoying about your problem is that the following related problem is easily seen to be NP-hard: given a graph and two vertex pairs (s, t), (s', t'), to determine whether there are vertex-disjoint paths from s to t and from s' to t', even when t = s', and even on graphs that are the union of two DAGs. Still, this doesn't seem to help for the question that you ask.
– a3nm
May 22, 2015 at 11:58
• Disjoint paths problem is W-hard even on DAGs, and it's a homework to show that it's NP-Hard in DAGs. Shiloach algorithm is for two disjoint paths problem, and in somewhat similar way works for k disjoint paths problem in DAGs but it takes time n^k. But at least admits an XP algorithm for your problem. Jun 18, 2015 at 20:39