8
$\begingroup$

Note: I posted a similar question regarding undirected graph.

Given

  • A digraph $G$ with no multiple-edges or loops
  • A source node $s$
  • A target node $t$
  • Maximal path length $l$

I am looking for $G'$ - A subgraph of $G$ that contains any node and any edge in $G$ (and only those), that are part of at least one simple path from $s$ to $t$ with length $\leq l$.

Note that I don't need to enumerate the paths.

$\endgroup$
  • $\begingroup$ Are there more constraints to your problem? Recall that the following problem is NP-complete: Given digraph $G$ and vertices $s,t,v$, does there exist a $(s,t)$ path also containing $v$? $\endgroup$ – Kristoffer Arnsfelt Hansen Dec 9 '13 at 17:56
  • $\begingroup$ @KristofferArnsfeltHansen, interesting! Would you like to add that as an answer and provide a reference for that result? It sounds like it answers the original question in the negative. $\endgroup$ – D.W. Dec 9 '13 at 18:24
  • $\begingroup$ @KristofferArnsfeltHansen: There are no more constraints. $\endgroup$ – Lior Kogan Dec 9 '13 at 18:26
6
$\begingroup$

As the question is stated, having $l$ as part of the input, the problem is $\mathsf{NP}$-hard. This follows as a special case of the classification of the class of patterns for which the directed subgraph homeomorphism problem is $\mathsf{NP}$-complete by Fortune, Hopcroft, and Wyllie's paper: The directed subgraph homeomorphism problem.

In particular the following problem is $\mathsf{NP}$-complete: Given a directed graph $G$ and vertices $s,t,v$, does there exist a (simple) $(s,t)$-path through $v$?

$\endgroup$
  • $\begingroup$ How does it fit with the accepted solution here? stackoverflow.com/questions/10825249/… Is it NP-hard just when the graph is directed? $\endgroup$ – Lior Kogan Dec 10 '13 at 14:25
  • 1
    $\begingroup$ Correct, the above problem can be solved efficiently for the variant when the graph is undirected as described in the answer you link to. $\endgroup$ – Kristoffer Arnsfelt Hansen Dec 10 '13 at 14:33
0
$\begingroup$

Update: this answer appears to be flawed. See the comment from Kristoffer Arnsfelt Hansen.


I don't know how to solve your problem, but here is a technique to solve a simpler version of your problem: namely, given an edge $e$, test whether there exists any simple path from $s$ to $t$ that includes edge $e$. (This corresponds to the special case of your problem where $l=\infty$.)

You can solve this simpler problem using "max-flow with lower bounds" as a subroutine. In the standard max-flow problem, the capacity of each edge gives us an upper bound on the amount of flow going through that edge, and we require that the amount of flow on edge be lower-bounded by 0. In "max-flow with lower bounds", we are allowed to specify both a lower bound and an upper bound on the amount of flow through that edge. It is known that "max-flow with lower bounds" can be solved in polynomial time.

Now, suppose we have an edge $e \in E$, and we want to test whether there exists a simple path from $s$ to $t$ that includes edge $e$. We're going to set up a max-flow with lower bounds problem. In particular, take graph $G$ and add a new node $s_0$ with edge $s_0 \to s$ and a new node $t_1$ with edge $t \to t_1$. Make the capacity (upper-bound) on each edge 1. The lower-bound on all edges will be 0, except that the lower-bound on edge $e$ is 1. Now check whether there exists a feasible flow from $s$ to $t$ that satisfies all the bounds (this test can be done in polynomial time, as mentioned above). If there is no flow, then there is no simple path from $s$ to $t$. If there is such a flow, then tracing out that flow yields a simple path from $s$ to $t$ that includes edge $e$, so there does exist such a simple path.

How do we solve a "max-flow with lower bounds" problem? In this case, only one edge has a non-zero lower bound. Therefore, we can use a standard approach to network flow, where at each point we choose an augmenting path by computing shortest paths in the residual graph -- except that here we ask (roughly) that one of the augmenting paths includes the edge $e$.

I learned this idea from the following paper:

  • Finding a Simple Path with Multiple Must-include Nodes. Hars Vardhan, Shreejith Billenahalli, Wanjun Huang, Miguel Razo, Arularasi Sivasankaran, Limin Tang,Paolo Monti, Marco Tacca, and Andrea Fumagalli. The University of Texas at Dallas, Technical Report UTD/EE/2/2009. June 2009.

(Make sure to read the techreport version, not the published version. This idea is found in the second paragraph of the introduction.)

Unfortunately, I don't know how to extend this technique to solve your original problem, with your upper-bound $l$ on the length of the simple path.


Alternatively, we could solve your problem in a straightforward way using integer linear programming (ILP). In practice, ILP solvers are pretty good on many problems. However, their worst-case running time is still exponential, so this is not going to give an algorithm with polynomial worst-case running time. Let me know if you want me to elaborate on how to formulate this using ILP.

$\endgroup$
  • 1
    $\begingroup$ Thanks. Also look here: stackoverflow.com/questions/10825249/… $\endgroup$ – Lior Kogan Dec 9 '13 at 18:47
  • 1
    $\begingroup$ The problem of finding a simple $(s,t)$-path through a specified edge in a directed graph is also $NP$-hard. The argument in the paper you reference above is flawed: A feasible flow could be a simple path avoiding the specified edge together with a cycle through the specified edge. Such a flow can exist even if there is no simple path through the specified edge. $\endgroup$ – Kristoffer Arnsfelt Hansen Dec 10 '13 at 11:56
0
$\begingroup$

We can compute the subgraph $G$ using two breadth-first searches and a scan through the nodes and edges in time $O(V + E)$.

We perform a breadth-first search from $s$ in $G$ to get the BFS numbering $d_s(v)$ for each node $v$ in $G$. The BFS number denotes the number of edges in the shortest path from $s$ to $v$. We also perform a breadth-first search from $t$ in the transpose of $G$ (that is the graph with an edge $(v,u)$ for each edge $(u,v)$ in $G$) to get the BFS numbering $d_t(v)$ for each node $v$ in $G$.

For each node $v$ in G, the shortest simple path from $s$ to $t$ that goes through $v$ has length $d_s(v) + d_t(v)$.

The subgraph $G'$ contains the node $v$ from $G$ if and only if $d_s(v) + d_t(v) \leq l$ and an edge $(u,v)$ if and only if $d_s(u) + d_t(v) \leq l-1$.

$\endgroup$
  • 5
    $\begingroup$ It may return paths which are not simple (e.g. for the graph s<-->a<-->b<-->c<-->t ; b<-->d: node d is a dead-end and should not be part of the solution). $\endgroup$ – Lior Kogan Dec 9 '13 at 7:09
0
$\begingroup$

Here's a simple FPT algorithm (where $l$ is the parameter), which works for both the directed and the undirected case in time $O(2^l\cdot m(n+m))$, which might be feasible if your graph is large but $l$ is small enough. In my other answer I give a poly time algorithm for the undirected case.

First, the question is equivalent (up to a factor $m$ in the runtime) to asking if there's a path of size at most $l$ that goes through some specific edge $e$. Next, the idea is to force the simplicity of the path by partitioning the vertices into those that can appear before the examined edge and those that can only appear after it in the pass.

Foreach $e=(u,v)\in E$: 
a. do for $O(2^l)$ times:
  1. Compute a random partition of the vertices set $V=(S,V\setminus S)$ 
   such that $s,u\in S$, $v,t\not \in S$ (and every other vertex is in $S$ w.p. 1/2).
  2.Find the shortest path from $s$ to $u$ in the subgraph induced by $S$.
    And the shortest path from $v$ to $t$ in the subgraph of $V\setminus S$. 
  3.If the sum of distances is no more than $l-1$, add $e$ to the output graph.

Analysis
a. Obviously, if there was no simple path of size $\leq l$ in $G$ which goes through $e$, the algorithm will not return it.

b. If there is such path, it would partition correctly (i.e. all of the vertices before $u$ will be in $S$ and the rest in $V\setminus S$) w.p. $2^{-l}$, therefore if we run the partition iteration $O(2^l)$ times we'll discover it with high probability.

Derandomization

If you're willing to pay $2^{polylog(l)}$ factor to the runtime, it can be derandomized as follows:

Take a $(n,l)$-universal-set and replace the random partition stage by running over all of the strings in the universal set, interpreting $S$ as the set of vertices whose value in the string is 1. The size of the universal set is $O(2^{l+ log^3(l)}\cdot poly(n))$ which determines the runtime.

$\endgroup$

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.