Zliczanie wszystkich par rozłącznych ścieżek

Z uwagi na skierowany wykres , a dwa wierzchołki s , t ∈ V . Para prostych ścieżek p 1 , p 2 od s do t jest rozłącznymi krawędziami, jeśli nie dzielą krawędzi.$G = (V,E)$$s,t \in V$$p_1,p_2$$s$$t$

Za pomocą maksymalnego przepływu łatwo jest zdecydować, czy istnieje para rozłącznych ścieżek krawędzi od do t . Czy istnieje algorytm wielomianowego opóźnienia czasowego do wyliczenia wszystkich par rozłącznych ścieżek brzegowych od s do t ?$s$$t$$s$$t$

Uważam, że odpowiedź Artema Kaznatcheeva jest poprawna, ale nie daje przestrzeni wielomianowej. Oto inne podejście, które powinno pod tym względem działać nieco lepiej.

Za pomocą maksymalnego przepływu możliwe jest rozwiązanie nieco bardziej ogólnego problemu: znajdź parę ścieżek rozłącznych krawędzi od niektórych dwóch wierzchołków {s1, s2} do innej pary wierzchołków {t1, t2}, ale bez kontrolowania, który wierzchołek źródłowy jest podłączony do którego wierzchołka docelowego.

Załóżmy, że mamy wykres G i wierzchołki s1, s2, t1, t2, dla których chcemy wymienić wszystkie pary ścieżek. Znajdź pojedynczą parę ścieżek P1, P2 i niech e = (s1, v) będzie pierwszą krawędzią na jednej z tych ścieżek. Następnie możemy podzielić przestrzeń problemową na dwa podproblemy: pary ścieżek używających e są takie same jak ścieżki od {v, s2} do {t1, t2} w G-s1, i pary ścieżek, które nie używają e są takie same jak ścieżki od {s1, s2} do {t1, t2} w Ge. Powtórz w obu tych dwóch podproblemach i (aby uniknąć powielania) zgłoś ścieżkę tylko wtedy, gdy znajdziesz się u dołu rekurencji.

Po raz pierwszy czytam o algorytmach wielomianowego opóźnienia, więc nie jestem w 100% pewien swojej odpowiedzi, ale myślę, że coś takiego powinno działać.

$<$$D$$G$

$F$

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

$^*D$$D$

1. $(P,Q)$$P < Q$$s$$t$

2. $(P,Q)$$D$

   $(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)$