Enumerando todos os pares de caminhos separados

Dado um gráfico dirigido e dois vértices . Um par de caminhos simples de a é separado da aresta se eles não compartilharem uma aresta.s , t ∈ V p 1 , p 2 s $G = (V,E)$$s,t \in V$$p_1,p_2$$s$$t$

Usando o fluxo máximo, é fácil decidir se há um par de caminhos separados de arestas de a . Agora, existe um algoritmo polinomial de atraso de tempo para enumerar todos os pares de caminhos disjuntos de arestas de a ?t s $s$$t$$s$$t$

Acredito que a resposta de Artem Kaznatcheev esteja correta, mas não fornece espaço polinomial. Então, aqui está uma abordagem diferente que deve funcionar um pouco melhor nesse sentido.

Usando o fluxo máximo, é possível resolver um problema um pouco mais geral: encontre um par de caminhos separados de arestas de alguns dois vértices {s1, s2} para outro par de vértices {t1, t2}, mas sem controlar qual vértice de origem está conectado para qual vértice de destino.

Suponha que tenhamos um gráfico G e os vértices s1, s2, t1, t2 para os quais queremos listar todos os pares de caminhos. Encontre um único par de caminhos P1, P2 e deixe e = (s1, v) ser a primeira aresta de um desses caminhos. Em seguida, podemos dividir o espaço do problema em dois subproblemas: os pares de caminhos que usam e são os mesmos de {v, s2} a {t1, t2} em G-s1 e os pares de caminhos que não usam e são os mesmos que os caminhos de {s1, s2} para {t1, t2} em Ge. Recupere-se nesses dois subproblemas e (para evitar duplicação) apenas relate um caminho quando estiver na parte inferior da recursão.

Esta é a primeira vez que li sobre algoritmos de atraso polinomial, por isso não tenho 100% de certeza da minha resposta, mas acho que algo como o seguinte deve funcionar.

Escolha uma convenção para representar caminhos que tenham uma ordem total natural definida nela. (Um exemplo seria apenas para listar os vértices do caminho e ordenar lexicograficamente). Escolha sua estrutura de dados preferida no local que suporta pesquisa e inserção logarítmica (por exemplo, uma árvore vermelha e preta). Seja seu gráfico$<$$D$$G$

Defina um algoritmo :$F$

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

(aqui significa uma referência a uma estrutura de dados local )$^*D$$D$

1. execute seu algoritmo poli-tempo para retornar um par de caminhos separados por arestas com de para .$(P,Q)$$P < Q$$s$$t$

2. Se não é em .$(P,Q)$$D$

   2.1 Insira em (e faça a saída, se você pretende que a saída seja executada conforme o algoritmo).$(P,Q)$$D$

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

Agora, para enumerar todos os seus caminhos, crie um vazio e para cada par com (se o gráfico não for direcionado, caso contrário), execute . Você exibirá todos os caminhos na primeira vez em que os visualizar e também terá uma boa estrutura de dados pesquisável que contém todos os caminhos quando terminar. Observe que esse algoritmo também é executado em tempo polinomial no tamanho da entrada + saída (como qualquer algoritmo de atraso polinomial).s , t ∈ V ( G ) s < t s ≠ t F ( s , t , G , ∗ D $D$$s,t \in V(G)$$s < t$$s \neq t$$F(s,t,G,*D)$

Duvido que esta seja a melhor maneira de fazer isso, em particular essa abordagem não está no (no tamanho da entrada). Penso que, pensando bem, você poderá encontrar algo que funcione no , embora não seja capaz de construir a estrutura de dados à medida que avança.P S P A C $PSPACE$$PSPACE$

Birmelé et al. Mostram um algoritmo de atraso da versão do vértice-disjunta do problema em "Enumeração eficiente de bolhas em gráficos direcionados".$O(m)$