Enumerar todos los pares de caminos disjuntos

Dado un grafo dirigido y dos vértices . Un par de rutas simples de a es un borde disjunto si no comparten un borde.s , t ∈ V p 1 , p 2 s $G = (V,E)$$s,t \in V$$p_1,p_2$$s$$t$

Utilizando el flujo máximo, es fácil decidir si hay un par de caminos disjuntos borde de a . Ahora, hay un algoritmo de retardo de tiempo polinómico para enumerar todos los pares de ruta disjunta borde de a ?t s $s$$t$$s$$t$

Creo que la respuesta de Artem Kaznatcheev es correcta, pero no da espacio polinomial. Así que aquí hay un enfoque diferente que debería funcionar un poco mejor a ese respecto.

Usando el flujo máximo es posible resolver un problema un poco más general: encontrar un par de caminos disjuntos de borde desde algunos dos vértices {s1, s2} a algún otro par de vértices {t1, t2}, pero sin controlar qué vértice fuente está conectado a qué destino vértice.

Supongamos que tenemos un gráfico G y vértices s1, s2, t1, t2 para los que queremos enumerar todos los pares de caminos. Encuentre un solo par de rutas P1, P2 y deje que e = (s1, v) sea el primer borde en una de esas rutas. Luego podemos dividir el espacio del problema en dos subproblemas: los pares de caminos que usan e son los mismos que los caminos de {v, s2} a {t1, t2} en G-s1, y los pares de caminos que no usan e son los mismos que los caminos de {s1, s2} a {t1, t2} en Ge. Recurre en estos dos subproblemas y (para evitar duplicaciones) solo informa una ruta cuando estás en la parte inferior de la recursión.

Esta es la primera vez que leo sobre algoritmos de retraso polinómico, por lo que no estoy 100% seguro de mi respuesta, pero creo que algo como lo siguiente debería funcionar.

Elija alguna convención para representar rutas que tengan un orden total natural definido en ella. (Un ejemplo sería solo enumerar los vértices de la ruta y el orden lexicográficamente). Elija su estructura de datos D in situ favorita que admita la búsqueda e inserción logarítmica (digamos un árbol rojo-negro). Deja que G sea ​​tu gráfico$<$$D$$G$

Definir un algoritmo :$F$

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

(aquí ∗ D significa una referencia a una estructura de datos D in situ )$^*D$$D$

1. ejecutar su algoritmo de tiempo poli para el retorno de un par de caminos de borde-disjuntos con P < Q de s a t .$(P,Q)$$P < Q$$s$$t$

2. Si no se encuentra en D .$(P,Q)$$D$

   2.1. Inserte en D (y haga salir si se supone que debe salir mientras se ejecuta el algoritmo).$(P,Q)$$D$

   $uv \in E(P\cup Q)$$F(s,t,G - \{uv\}, ^*D)$

$D$$s,t \in V(G)$$s < t$$s \neq t$$F(s,t,G,*D)$

$PSPACE$$PSPACE$

$O(m)$