Enumerating all pairs of disjoint paths

Given a directed graph $G = (V,E)$ and two vertices $s,t \in V$. A pair of simple paths $p_1,p_2$ from $s$ to $t$ is edge disjoint if they don't share an edge.

Using max flow, it is easy to decide if there is a pair of edge disjoint paths from $s$ to $t$. Now, is there a polynomial time delay algorithm to enumerate all pairs of edge disjoint path from $s$ to $t$?

• No, since there might be exponentially many such paths. May 25 '11 at 2:27
• @Kaveh: I think a "polynomial delay algorithm" is allowed to take exponential time, as long as the delay between outputs is polynomially long. For example, there is a polynomial delay algorithm that lists all maximal cliques in increasing order, even though the number of maximal cliques is exponential. May 25 '11 at 3:26
• Is it possible to include the explanation of polynomial delay in the question? I was not familiar with it until I read Robin's comment. May 25 '11 at 3:34
• @Robin, you are right, I didn't pay attention to the word "delay". May 25 '11 at 3:55

I believe Artem Kaznatcheev's answer is correct, but it does not give polynomial space. So here's a different approach that should work a little better in that respect.

Using max flow it is possible to solve a slightly more general problem: find a pair of edge disjoint paths from some two vertices {s1,s2} to some other pair of vertices {t1,t2}, but without controlling which source vertex is connected to which destination vertex.

Suppose we have a graph G and vertices s1,s2,t1,t2 for which we want to list all pairs of paths. Find a single pair of paths P1,P2, and let e = (s1,v) be the first edge on one of those paths. Then we can split the problem space into two subproblems: the pairs of paths that use e are the same as the paths from {v,s2} to {t1,t2} in G-s1, and the pairs of paths that do not use e are the same as the paths from {s1,s2} to {t1,t2} in G-e. Recurse in both of these two subproblems, and (to avoid duplication) only report a path when you're at the bottom of the recursion.

• is it obvious that the algorithm is polynomial delay if we wait until the bottom of the recursion? May 25 '11 at 23:55
• The recursion takes polynomially many levels to bottom out (as each level deletes something from the graph), and each branch either returns immediately (because it can't find a pair of paths) or does bottom out and return something, so yes, it does take only polynomial delay. May 26 '11 at 4:53

This is the first time I have read about polynomial delay algorithms, so I am not 100% sure of my answer, but I think something like the following should work.

Pick some convention for representing paths that has a natural total ordering $<$ defined on it. (One example would be just to list the vertexes of the path and order lexicographically). Pick your favorite in-place data-structure $D$ that supports logarithmic search and insert (say a red-black tree). Let $G$ be your graph

Define an algorithm $F$:

$F(s,t,G, ^*D)$:

(here $^*D$ means a reference to an inplace datastructure $D$)

1. run your poly-time algorithm for returning a pair of edge-disjoint paths $(P,Q)$ with $P < Q$ from $s$ to $t$.
2. If $(P,Q)$ is not in $D$.

2.1. Insert $(P,Q)$ into $D$ (and output if you are suppose to output as the algorithm runs).

2.2. For each edge $uv \in E(P\cup Q)$ run $F(s,t,G - \{uv\}, ^*D)$

Now, to enumerate all your paths, create an empty $D$ and for each pair $s,t \in V(G)$ with $s < t$ (if the graph is undirected, $s \neq t$ otherwise) run $F(s,t,G,*D)$. You will output every path the first time you see them, and you will also have a nice searchable data-structure that contains all paths when you are done. Note that this algorithm also runs in polynomial time in the size of the input + output (just like any polynomial delay algorithm would).

I doubt that this is the best way to do this, in particular this approach is not in $PSPACE$ (in size of the input). I think by thinking carefully you could find something that runs in $PSPACE$, although it won't be able to build the data-structure as it goes along.

Birmelé et al show a $O(m)$ delay algorithm from the vertex-disjoint version of the problem in "Efficient Bubble Enumeration in Directed Graphs".