Problem z minimalną łącznością z klapką

Podczas gry z moim GPS sformułowałem następujący problem. Oto on:

Niech będzie grafem ukierunkowanym, tak że jeśli to , tj. jest orientacją leżącego u jego podstaw wykresu niekierowanego. Rozważ następujące operacje:e = ( u , v ) ∈ E ( v , u ) ∉ E $G(V,E)$$e=(u,v) \in E$$(v,u) \notin E$$G$

• $Flip(u,v)$ : Zamień krawędź na krawędź( v , u $(u,v)$$(v,u)$
• $undirect(u,v)$ : Dodać krawędź nieukierunkowane$(u,v)$

Niech będą dwoma specjalnymi wierzchołkami. Rozważ następujące problemy związane z optymalizacją:$s,t \in V$

• Łączność Min-Flip st: Biorąc pod uwagę i dwa wierzchołki znajdź minimalną liczbę krawędzi, które należy obrócić, aby uzyskać ukierunkowaną ścieżkę od do .s , t s $G$$s,t$$s$$t$
• Silne połączenie Min-Flip: Biorąc pod uwagę znajdź minimalną liczbę krawędzi, które należy odwrócić, aby silnie połączony. Jeśli nie można silnie połączyć poprzez odwrócenie krawędzi, należy wyprowadzić NO.G $G$$G$$G$
• Min. Undirect silna łączność: Biorąc pod uwagę znajdź minimalną liczbę krawędzi, które należy przekierować, aby silnie połączony.$G$$G$

Pamiętaj, że nie możesz dodawać „nowych” krawędzi. Modyfikujesz istniejące krawędzie tylko przy użyciu powyższych operacji. Czy ten problem jest znany w literaturze? Jeśli tak, jakie są znane wyniki?

Podsumowanie: Problemy można rozwiązać w czasie wielomianowym, znajdując silnie powiązane orientację kosztu minimalnego.

Więcej szczegółów: Twierdzenie Robbinsa mówi, że krawędzie niekierowanego wykresu można tak zorientować, że wynikowy skierowany wykres jest silnie połączony tylko wtedy i tylko wtedy, gdy niekierowany wykres jest połączony 2-krawędziami. Istnieje kilka rozszerzeń, a jedno z nich mówi, że stosując algorytm przepływu podmodularnego w czasie wielomianowym, możemy rozwiązać następujący problem w czasie wielomianowym: Biorąc pod uwagę niekierowany wykres z kosztem krawędzi (dla obu kierunków), znajdź orientację kosztu minimalnego, która sprawia, że wykres jest silnie połączony. Na przykład zobacz artykuł Franka . Nowszy algorytm zapewnia Iwata i Kobayashi .

Ten wynik powinien być przydatny do rozwiązania postawionych problemów. Pierwszy problem można rozwiązać metodą zaproponowaną przez Tomka . Dlatego skoncentrujemy się na innych problemach.

W przypadku drugiego problemu używamy tej samej konstrukcji wykresu ważonego krawędzi, co Tomek, i znajdujemy orientację silnie połączoną w minimalnym koszcie w czasie wielomianowym.

W przypadku trzeciego problemu, aby zezwolić na oba kierunki dla każdej krawędzi, powielamy każdą krawędź, a następnie stosujemy tę samą konstrukcję i ten sam algorytm. Jest to ważna redukcja, ponieważ użycie tego samego kierunku dla powielonych krawędzi nie wpływa na silne połączenie.

Oto odpowiedź na pierwszy problem:
rozważ nowy wykres ważony , gdzie E ′ = { ( u , v , 0 ) | ( u , v ) ∈ E } ∪ { ( v , u , 1 ) | ( u , v ) ∈ E } (ciężary wszystkich krawędzi w $G'=(V,E')$$E'=\{(u,v,0)|(u,v) \in E\} \cup \{(v,u,1)|(u,v)\in E \}$$G$wynoszą 0, a masy „odwróconych” krawędzi wynoszą 1). Teraz musisz tylko znaleźć najkrótszą ścieżkę od do t .$s$$t$

$k$$k=0$$s$$t$$k$

W mojej ostatniej książce „Connections in Combinatorial Optimization” (Oxford University Press, 2011) głównym tematem są problemy z orientacją grafów, w tym omówione powyżej odmiany. Wiadomo, że wykres połączony z krawędzią 2k ma orientację związaną z krawędzią k (jest to twierdzenie Nasha-Williamsa). Jeśli wykres nie jest połączony z krawędzią 2k, można być zainteresowanym podjęciem decyzji, czy dany podzbiór F krawędzi jest dobry (w tym sensie, że F ma orientację, dzięki czemu powstały mieszany wykres jest połączony z krawędzią k). W książce opisałem, jak rozwiązać ten problem w czasie wielomianowym. Ale nie wiem, jak znaleźć dobry zestaw minimalnej liczności.

Andras Frank

Podstawa min-Flip st-connectivity: oblicz wszystkie wierzchołki, które są osiągalne z s (T). jeśli t jest w T stop. Indukcyjny: weź pod uwagę wszystkie wierzchołki spoza T, które sąsiadują z T jednym przerzuceniem i nazwij to U. Oblicz wierzchołki osiągalne z U nazwij to V. Jeśli t jest V stop, w przeciwnym razie dodaj V do T i kontynuuj.

Silna łączność Min-Flip Musisz rozumieć pośrednio, ponieważ miałbyś problem z: A -> B