Maksymalny przepływ - przez wierzchołek - jak?

Question

Problem:

Niech G = (V, E) będzie skierowanym wykresem na n> = 3 wierzchołkach z m krawędziami. Zestaw wierzchołków V zawiera trzy specjalne wierzchołki a, v i b. . Znajdź prostą ścieżkę od a do b do v, jeśli istnieje. (Prosta ścieżka to ścieżka bez powtarzających się wierzchołków.)

Wierzę, że ten problem powinien/może być rozwiązany za pomocą algorytmu Max Flow, ale nie jestem pewien jak. Przypomina mi algorytm Max Flow z wieloma źródłami, w których krawędzie mają pojemność 1. Ktoś wie, jak problem można zredukować do algorytmu Maksymalnego Przepływu?

Jeśli ustawię wierzchołek B jako zlew nie mogę być pewien, że będzie to v. Jeśli ustawię v jako tonięcie, jak mam kontynuować po osiągnięciu v?

Answer 1

Poniższa powinno działać:

• znaleźć wszystkie minimalne ścieżek z a do v, że nie zawierają wierzchołek b. Można je uzyskać poprzez (np.) DFS na wykresie bez wierzchołka b. Mówimy, że a-v-ścieżka p jest minimalna, jeśli żadna inna a-v-ścieżka p' zawiera tylko wierzchołki od p.

• dla każdego minimalnego a-v -path, spróbować znaleźć drogę od v do b ignorując wierzchołkach już należącej do a-v -path. Jeśli znajdziesz coś takiego, gotowe.

Uwagi: pamiętać, że liczba ścieżek może rosnąć wykładniczy, ale jak już wskazano w moim komentarzu, przynajmniej uogólniona wersja tego problemu wydaje się sprowadzić do TSP, co jest prawdopodobnie bardzo trudny.

Answer 2

Jest to równoważne zapytaniu, czy wykres zawiera podglem homeomorficzny do skierowanej ścieżki z trzema wierzchołkami (wzór jest wykresem na niektórych wierzchołkach z wykresu wejściowego, a podgraph jest rodzajem homeomorficznym do wzoru, jeśli krawędzie wzór można odwzorować na proste, parami rozłączne ścieżki podgrafu). Zostało udowodnione przez Fortune, Hopcroft, and Wyllie, że ukierunkowany homeomorfizm subgraph jest NP-trudny dla prawie wszystkich ustalonych wzorców, w tym również. Problem jest więc NP-trudny i nie można go rozwiązać technikami przepływu, chyba że P = NP.

Wersja bez odniesienia może jednak zostać zredukowana do maksymalnego przepływu przez to, że aib jest źródłem i v zlewem.