<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-05-25T23:55:23.417Z
is it obvious that the algorithm is polynomial delay if we wait until the bottom of the recursion?
Artem Kaznatcheev
CC BY-SA 3.0
2011-05-26T04:53:13.523Z
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.
David Eppstein
CC BY-SA 3.0
2011-05-25T15:33:00.310Z
2011-05-25T15:33:00.310Z
David Eppstein
<p>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.</p>

<p>Pick some convention for representing paths that has a natural total ordering $&lt;$ 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</p>

<p>Define an algorithm $F$:</p>

<hr>

<p>$F(s,t,G, ^*D)$:</p>

<p>(here $^*D$ means a reference to an inplace datastructure $D$)</p>

<ol>
<li>run your poly-time algorithm for returning a pair of edge-disjoint paths $(P,Q)$ with $P &lt; Q$ from $s$ to $t$.</li>
<li><p>If $(P,Q)$ is not in $D$.</p>

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

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

<hr>

<p>Now, to enumerate all your paths, create an empty $D$ and for each pair $s,t \in V(G)$ with $s &lt; 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).</p>

<p>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.</p>

CC BY-SA 3.0
2011-05-25T04:12:53.913Z
2011-05-25T11:50:39.937Z
2011-05-25T11:50:39.937Z
Artem Kaznatcheev
<p>Birmelé et al show a $O(m)$ delay algorithm from the vertex-disjoint version of the problem in "Efficient Bubble Enumeration in Directed Graphs".</p>

CC BY-SA 3.0
2013-04-03T22:59:51.543Z
2013-04-03T22:59:51.543Z
Rui Ferreira
<p>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. </p>

<p>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$? </p>

CC BY-SA 3.0
2011-05-25T02:27:17.640Z
No, since there might be exponentially many such paths.
Kaveh
CC BY-SA 3.0
2011-05-25T03:26:00.157Z
@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.
Robin Kothari
CC BY-SA 3.0
2011-05-25T03:34:50.220Z
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.
Artem Kaznatcheev
CC BY-SA 3.0
2011-05-25T03:55:19.553Z
@Robin, you are right, I didn't pay attention to the word "delay".
Kaveh
<cc.complexity-theory><graph-algorithms>
Enumerating all pairs of disjoint paths
Amateur
# Enumerating all pairs of disjoint paths

(Asked by: username_0 on 2011-05-24)

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$?

**Tags:** cc.complexity-theory, graph-algorithms

> **Comments:**
> **username_1**: No, since there might be exponentially many such paths.  
> **username_2**: @username_1: 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.  
> **username_3**: 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.  
> **username_1**: @Robin, you are right, I didn't pay attention to the word "delay".  

---

## 3 answers

### Answer by username_4 on 2011-05-25. Score: 6

I believe username_3'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.

> **Comments:**
> **username_3**: is it obvious that the algorithm is polynomial delay if we wait until the bottom of the recursion?  
> **username_4**: 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.  

---

### Answer by username_3 on 2011-05-25. Score: 5

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.


---

### Answer by username_5 on 2013-04-03. Score: 2

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


---

