1
$\begingroup$

Given a directed graph, consider the problem of finding the largest number of edge-disjoint paths from a source node $s$ to a destination node $t$. I know this can be done in polynomial time, for example by reducing it to a max flow problem.

The question I am wondering about is a slight variation of this: you can have paths which use the same edge, they just can't use it at the same time. More specifically, suppose we have two paths, the first of which traverses the edges $e^1, e^2, \ldots, e^k$ in that order, while the second traverses the edges $w^1, w^2, \ldots, w^l$, also in that order; then we should have $e^i \neq w^i$ for all $i$. It is perfectly OK, on the other hand, to have e.g., $e^1 = w^2$.

For example, consider the graph $$~~~~~~~~3 \rightarrow 2 \leftarrow 4 \leftarrow 5$$ $$\downarrow$$ $$0$$

The pairs of paths $\{(3,2),(2,0)\}$ and $\{(5,4), (4,2), (2,0)\}$ are considered not to intersect since the common edge $(2,0)$ is traversed at different times.

Thus if we add a source node $s$ with out-edges to $3$ and $5$ and a destination node $t$ with an incoming edge from zero, we will have that there are two paths from $s$ to $t$ with the desired non-intersection property.

On the other hand, if the outgoing edges from $s$ go to $3$ and $4$, only one such path would exist, since the paths $\{(3,2),(2,0)\}$ and $\{(4,2),(2,0)\}$ use the same edge $(2,0)$ at the same time.

This is a very natural setup to consider if you study the problem of scheduling shipments across a network.

My question is: does the problem of finding the largest number of paths between $s$ and $t$ in a directed graph which are non-intersecting in this sense have a name? Has it ever been studied before? I strongly suspect the answer is positive but I don't know what to google for.

Also, it it known (or obvious) whether it can be solved in polynomial time?

$\endgroup$
  • $\begingroup$ Try using a layer graph. $\endgroup$ – Yuval Filmus May 7 '16 at 7:32
  • $\begingroup$ @YuvalFilmus -- I assume this means creating a bunch of copies of the original directed graph and having the edges go from each copy to the next one. If so, I thought about that, but how many layers should you take? Clearly $2^n$ suffices to recast the original problem as a max flow problem in the layered graph, but can you take a polynomial number of layers? $\endgroup$ – Richard Clem May 7 '16 at 7:47
  • $\begingroup$ The number of layers is the maximal length of a path that you allow. $\endgroup$ – Yuval Filmus May 7 '16 at 8:02
  • $\begingroup$ @YuvalFilmus - the paths can be of any length. Of course this implies their length is at most exponential in the number of nodes $n$. If it was just one path, clearly length would be at most $n$; but if there are, say, $n/2$ paths, then there is the possibility that they move through various sets (of which there are exponentially many) before reaching the destination. Thus it seems that, unless I'm missing something, this approach seems to leave open the question of whether the problem is solvable in polynomial time. $\endgroup$ – Richard Clem May 7 '16 at 8:17
  • 1
    $\begingroup$ If the solution paths have exponential length, perhaps the solution is not so realistic. $\endgroup$ – Yuval Filmus May 7 '16 at 8:19

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.