10
$\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).

$\endgroup$
  • 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 Apr 16 '15 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 Apr 17 '15 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$ – a3nm May 22 '15 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 Jun 18 '15 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.