11
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Marzio De Biasi
    Commented Apr 16, 2015 at 21:17
  • 1
    $\begingroup$ 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'$. $\endgroup$
    – David Eppstein
    Commented Apr 17, 2015 at 4:55
  • $\begingroup$ 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. $\endgroup$
    – Antoine Amarilli 'a3nm'
    Commented May 22, 2015 at 11:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – Saeed
    Commented Jun 18, 2015 at 20:39

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.