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

  • 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

Consider the first backward edge $(u,v)$ on the requested path from $s$ to $t$, then $u$ must be reachable from $s$ in the graph $D$. Now, for each such reachable backward edge $(u,v)$, it suffices to show that there is a path from $v$ to $t$ in $G$, such that this path avoids a path (in $D$) from $s$ to $u$.

The problem is in $P$ if this can be decided in polynomial time, since there are $O(E')$ candidates for the first backward edge.

Update: (I'm don't think the following works, because flow from $v$ to $t$ might propagate back into the path from $s$ to $u$)

To decide whether such path exists, consider the following flow network: In the graph $G$ let every edge of $E$ have capacity $|E'|+2$, and all edges of $E'$ have capacity $1$. Now add a source and sink $S$ and $T$ with edges $(S,s)$ and $(u,T)$ of capacity $|E'|+2$, and edges $(S,v)$ and $(t,T)$ of capacity $1$. Now the maximum flow from $S$ to $T$ is $|E'|+3$ if and only if there were edge-disjoint paths from $s$ to $u$ in $D$ and $v$ to $t$ in $G$. For vertex-disjoint paths, we can treat each vertex as a pair vertices (one for incoming edges, one for outgoing edges) with a capacity $|E'|+2$ between them.

  • $\begingroup$ How do you show there is an adequate path from $v$ to $t$ in polynomial time? $\endgroup$ – Joseph Stack Apr 16 '15 at 13:22
  • $\begingroup$ First remove all vertices of $G$ that must be on a path from $s$ to $u$ in $D$, and then a straightforward reachability query. The removed vertices are those that when removed make $u$ unreachable from $s$. $\endgroup$ – Tim Apr 16 '15 at 13:24
  • $\begingroup$ I fear this is not exact: there can be two parallel paths leading from $s$ to $u$, both of which are cut by the path from $v$ to $t$ $\endgroup$ – Joseph Stack Apr 16 '15 at 13:42
  • $\begingroup$ I did indeed not consider that. But in that case there must be a path containing a backedge between the parallel paths, so we could as well have taken that path instead of the one containing $(u,v)$. $\endgroup$ – Tim Apr 16 '15 at 13:45
  • $\begingroup$ I'm not so sure I understand: a forward edge is enough to cut the parallel paths, because the edge $(u,v)$ may bring the path back to the lowest levels of the DAG $\endgroup$ – Joseph Stack Apr 16 '15 at 13:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.