Przycinanie silnie połączonego digrafa

10

Biorąc pod uwagę silnie połączony wykres G z ważonymi krawędziami, chciałbym zidentyfikować krawędzie, które prawdopodobnie nie są częścią żadnego minimalnie silnie połączonego podgrupy (MSCS) G.

Jedną z metod znajdowania takich krawędzi jest zmodyfikowany algorytm Floyda-Warshalla. Korzystając z algorytmu Floyda-Warshalla, można określić, które krawędzie nigdy nie są najlepszą opcją przejścia od wierzchołka i do j. Te węzły nie mogą być częścią MSCS, ponieważ lepiej zastąpić je dwiema lub więcej innymi krawędziami.

Technika przycinania Floyda-Warshalla działa całkiem dobrze, gdy wagi krawędzi różnią się znacznie, ale bardzo słabo, gdy wagi krawędzi są podobne, ale duże.

Czy znasz jakieś skuteczne metody przycinania dużych, podobnych obciążników krawędzi? Czy ten problem jest bardziej powszechny, którego nie rozpoznaję? Czy tego rodzaju przycinanie było wcześniej badane w literaturze?

ds.algorithms graph-theory graph-algorithms Nate
źródło
1
Nie potrafię odpowiedzieć na to pytanie bez zapoznania się z literaturą dotyczącą problemu. Czy sam próbowałeś czytać literaturę? Czy możesz streścić to, co znalazłeś?
Warren Schudy
1
Znaczna część literatury dotyczy znalezienia algorytmów aproksymacyjnych, z których niektóre są całkiem dobre. Większość z nich działa poprzez skurcz cyklu, z dobrymi wynikami. Mam problem ze znalezieniem literatury do przycinania zamiast przybliżania, dlatego zastanawiam się, czy problem przycinania jest uogólnieniem bardziej powszechnego problemu, z którym mogę przeczytać. Wszelkie wskazówki dotyczące literatury są mile widziane.
Nate
1
Jaką funkcję aproksymują algorytmy aproksymacyjne i czym to się różni od przycinania?
Suresh Venkat
Przybliżenia są zbliżone do minimalnie silnie połączonego podsgrafu. Jak powiedziałem, często używają do tego skurczu cyklu. Przycinanie poprzez skurcz cyklu może skutkować nieoptymalnym subgrafem (stąd przybliżenie). Chcę przycinać w taki sposób, że mogę zagwarantować, że nie przyciąłem żadnych krawędzi wyświetlających MSCS.
Nate

Odpowiedzi:

3

Zakładamy, że wagi krawędzi są dodatnimi liczbami całkowitymi. Biorąc pod uwagę ukierunkowany wykres G z wagami krawędzi, nazwij zboczę e zbędną, jeśli e nie należy do żadnego silnie połączonego podgraphu G o minimalnej wadze .

Twierdzimy, że jeśli P = NP, nie ma algorytmu czasu wielomianowego, który zawsze znajduje zbędne zbocze na danym ukierunkowanym wykresie z wagami krawędzi, o ile istnieje. Dokładniej:

Twierdzenie . Biorąc pod uwagę ukierunkowany wykres G z wagami krawędzi, trudno jest znaleźć zbędną krawędź w G lub zadeklarować, że G nie ma zbędnej krawędzi.

Dowód . Kluczową obserwacją jest to, że jeśli G ma unikatowy silnie połączony podgraph obejmujący minimalną masę, wówczas można obliczyć ten podgraph, usuwając jeden po drugim zbędne krawędzie. Dlatego pozostaje wykazać, że wyjątkowość nie sprawia, że ​​minimalny ciężar silnie połączonego problemu podporygrafu łączącego jest łatwiejszy, ale dowodzi tego następny lemat. QED .

Lemat . Z uwagi na skierowany wykres G o masach krawędzi jest NP-trudne do obliczenia ciężaru minimalnego ciężaru silnie połączony rozciągającą podgrafu z G nawet pod obietnicą G ma unikalną minimalnej wagi silnie połączony obejmujące podgrafu.

Dowód . Jak wiecie , problem bez obietnicy jest trudny NP (nawet w przypadku wagi jednostkowej) dzięki zmniejszeniu problemu z obwodem hamiltonowskim. Zmniejszamy problem bez obietnicy problemu z obietnicą.

Niech G będzie kierowanym wykresem z wagami krawędzi. Etykieta krawędzie G o e 0 , E, 1 , ..., e m -1 , gdzie m jest liczbą krawędzi w G . Niech w i jest podany ciężar krawędzi e I . Niech nowa waga w ′ i = 2 m w i +2 i . Łatwo jest wtedy sprawdzić, czy G z nowymi obciążnikami ma unikalny, ściśle związany podpunkt słupkowy o minimalnej masie. Łatwo jest również sprawdzić, czy minimalna wagaW silnie połączonego podporygrafu rozpinającego w G z pierwotnymi odważnikami można obliczyć z minimalnej masy W ′ w G z nowymi odważnikami jako W = ⌊ W ′ / 2 m ⌋. QED .

Tsuyoshi Ito
źródło
2
Tak, oczywiście, trudno jest znaleźć wszystkie takie krawędzie. Nie szukam wszystkich takich krawędzi, szukam zestawu krawędzi, które można określić, które można przycinać w czasie wielomianowym. Algorytmu Floyda-Warshalla można użyć do znalezienia jednego takiego zestawu krawędzi, jak opisano powyżej. Zastanawiałem się, czy istnieją inne sposoby identyfikacji podzbioru usuwalnych krawędzi w czasie wielomianowym.
Nate,