<p>What is the complexity of the following problem ($\in$ P? NP-hard?):</p>

<p><strong>Input:</strong> a directed acyclic graph $D=(V,E)$, a set of backward edges $E'\subset V\times V$, and two distinct nodes $s$ and $t$.</p>

<p><strong>Question:</strong> 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?</p>

<p><em>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
(<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.3962&amp;rep=rep1&amp;type=pdf" rel="nofollow">Perl and Shiloach, JACM'78</a>) 
2) the disjoint path problem is NP-complete in general graphs (<a href="http://www.sciencedirect.com/science/article/pii/0304397580900092" rel="nofollow">Fortune et al., TCS'80</a>).</em></p>

CC BY-SA 3.0
2015-04-16T21:17:48.597Z
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$.
Marzio De Biasi
CC BY-SA 3.0
2015-04-17T04:55:17.293Z
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'$.
David Eppstein
CC BY-SA 3.0
2015-05-22T11:58:09.923Z
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.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-06-18T20:39:28.073Z
Disjoint paths problem is W[1]-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.
Saeed
<graph-algorithms><time-complexity><disjoint-paths>
Simple path on dag with backward edges
Joseph Stack
# Simple path on dag with backward edges

(Asked by: username_0 on 2015-04-16)

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.3962&rep=rep1&type=pdf))
2) the disjoint path problem is NP-complete in general graphs ([Fortune et al., TCS'80](http://www.sciencedirect.com/science/article/pii/0304397580900092)).*

**Tags:** graph-algorithms, time-complexity, disjoint-paths
> **Comments:**
> **username_1**: 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$.  
> **username_2**: 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'$.  
> **username_3**: 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.  
> **username_4**: Disjoint paths problem is W[1]-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.  

---

## 0 answers

