10
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ No, since there might be exponentially many such paths. $\endgroup$ – Kaveh May 25 '11 at 2:27
  • 6
    $\begingroup$ @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. $\endgroup$ – Robin Kothari May 25 '11 at 3:26
  • 3
    $\begingroup$ 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. $\endgroup$ – Artem Kaznatcheev May 25 '11 at 3:34
  • $\begingroup$ @Robin, you are right, I didn't pay attention to the word "delay". $\endgroup$ – Kaveh May 25 '11 at 3:55
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ is it obvious that the algorithm is polynomial delay if we wait until the bottom of the recursion? $\endgroup$ – Artem Kaznatcheev May 25 '11 at 23:55
  • $\begingroup$ 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. $\endgroup$ – David Eppstein May 26 '11 at 4:53
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\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.