Problemy łatwe w przypadku wykresów nieważonych, ale trudne w przypadku wykresów ważonych

Wiele problemów związanych z grafem algorytmicznym można rozwiązać w czasie wielomianowym zarówno na wykresach nieważonych, jak i ważonych. Niektóre przykłady to najkrótsza ścieżka, min. Drzewo rozpinające, najdłuższa ścieżka (w ukierunkowanych grafach acyklicznych), maksymalny przepływ, min. Cięcie, maks. Dopasowanie, optymalne arborescencje, niektóre najgęstsze problemy z podgrafami, maks. Rozłączne nacięcia ukierunkowane, maks. Klika w niektórych klasach grafów, maks. Niezależna ustawione w niektórych klasach grafów, różne problemy z maksymalną rozłączną ścieżką itp

Istnieją jednak pewne (choć prawdopodobnie znacznie mniej) problemy, które można rozwiązać w czasie wielomianowym w przypadku nieważonym , ale stają się trudne (lub mają status otwarty) w przypadku ważonym . Oto dwa przykłady:

1. Biorąc pod uwagę pełny wykres -vertex i liczbę całkowitą , znajdź łączący podgraph łączący z minimalną możliwą liczbą krawędzi. Można to rozwiązać w czasie wielomianowym, używając twierdzenia F. Harary'ego, który mówi o strukturze optymalnych grafów. Z drugiej strony, jeśli krawędzie są ważone, to znalezienie podgrupy łączącej o minimalnej wadze jest twardym.k ≥ 1 k k N $n$$k\geq 1$$k$$k$$NP$

2. Niedawny (grudzień 2012 r.) Artykuł S. Chechika, MP Johnsona, M. Partera i D. Pelega (patrz http://arxiv.org/pdf/1212.6176v1.pdf ) rozważa między innymi problem ścieżki wywołać ścieżkę minimalnej ekspozycji. Tutaj szuka się ścieżki między dwoma określonymi węzłami, tak aby liczba węzłów na ścieżce plus liczba węzłów, które mają sąsiada na ścieżce, była minimalna. Dowodzą, że na wykresach z ograniczonym stopniem można to rozwiązać w czasie wielomianowym dla przypadku nieważonego, ale staje się twardy w przypadku ważonym, nawet z ograniczonym stopniem 4. (Uwaga: Odniesienie znaleziono jako odpowiedź na pytanie Co to jest złożoność tego problemu ścieżki? )$NP$

Jakie są inne interesujące problemy tego rodzaju, to znaczy, gdy przejście do wersji ważonej powoduje „skok złożoności”?

W świecie algorytmów aproksymacyjnych występuje problem pojemnościowego pokrycia wierzchołków. Biorąc pod uwagę i pojemności całkowite c ( v ) dla każdego v ∈ V, celem jest znalezienie minimalnej wielkości osłony wierzchołków dla G, gdzie liczba krawędzi pokrytych przez v wynosi co najwyżej c ( v ) . Ten problem ma stałą aproksymację współczynnika w przypadku nieważonym (to znaczy chcemy zminimalizować rozmiar osłony wierzchołków), podczas gdy jest on Ω ( log n ) twardy (chyba że$G=(V,E)$$c(v)$$v \in V$$G$$v$$c(v)$$\Omega(\log n)$w ( v $P = NP$ ) w przypadku ważonym (każdy wierzchołek ma ciężar i chcemy zminimalizować ciężar pokrycia).$w(v)$

Moim ulubionym przykładem jest problem niezależnej dominacji (biorąc pod uwagę wykres i liczbę całkowitą k , czy G ma maksymalny niezależny zestaw co najwyżej k wierzchołków?). Dobry wynik dzięki Martinowi Farberowi ( patrz tutaj ), nieważona wersja jest rozwiązana wielomianowo na wykresach akordowych. Gerard Chang udowadnia, że ​​wersja ważona jest NP-kompletna dla wykresów akordowych ( patrz tutaj ).$G$$k$$G$$k$

Idealny problem dopasowania w grafach dwustronnych występuje w podczas gdy dokładne dopasowanie idealnej wagi dla wykresu dwustronnego to N P- Complet .$P$$NP$

Kontynuując odpowiedź Mohammad Al-Turkistany za wydaje się, że wiele z wielomianem czasie rozwiązywalnych problemów nieważonych można przekształcić -Complete ważonej przypadku, jeśli pytamy, czy istnieje rozwiązanie, które ma dokładnie określoną wagę. Powodem jest to, że może to pozwolić na zakodowanie problemu sumy podzbioru w rozważanym zadaniu.$NP$

Na przykład, w przypadku dopasowania dokładnego dokładnego wagi, możemy wziąć na wejściu pełny dwustronny wykres, przypisując podane wagi krawędziom konkretnego dopasowania, a 0 wagi wszystkim pozostałym krawędziom. Łatwo jest zauważyć, że ten ważony graf ma idealne dopasowanie wagi dokładnie wtedy i tylko wtedy, gdy jest podzbiorem sumy ciężarów że dokładnie W . (Jeśli istnieje taki podzbiór, możemy pobrać odpowiednie krawędzie z ustalonego dopasowania i rozszerzyć go do idealnego dopasowania z krawędziami o zerowej masie, używając tego, że jest to kompletny wykres dwustronny.) Myślę, że podobna prosta sztuczka może również działać w przypadku wielu innych problemów.$W$$W$

Równoważenie wykresów (znane również jako Min Out-degree Orientation) jest kolejnym przykładem tego zjawiska. W tym problemie otrzymujemy niekierowany wykres ważony na krawędzi. Celem jest takie zorientowanie krawędzi, aby zminimalizować uzyskany (ważony) maksymalny stopień wyjściowy wykreślnika.

Problem jest często motywowany scenariuszem planowania. Wyobraź sobie, że każdy wierzchołek jest procesorem, a każda krawędź jest zadaniem, które może działać tylko na jednym z dwóch punktów końcowych. Ciężar krawędzi to długość odpowiedniego zadania, a celem jest zminimalizowanie czasu pracy.

Problemem jest NP-trudny i APX-twardy, nawet jeśli wszystkie wagi mają 1 lub 2 (patrz Ebenlendr i wsp. „Bilansowanie wykresów: specjalny przypadek planowania niepowiązanych równoległych maszyn” w SODA 2008). Jest to jednak P dla wykresów nieważonych (patrz Asahiro i wsp. „Klasy wykresów i złożoność orientacji wykresu minimalizująca maksymalne ważone przekroczenie” w CATS 2008).

Być może jest to tylko trywialny przykład i możesz uznać go za przypadek zdegenerowany, ale pierwszym przykładem, który przyszedł mi do głowy, jest problem Traveling Salesman (gdzie zwykle zakłada się, że wykres jest kompletny). Zauważ, że nieważona wersja to cykl Hamiltoniana, który jest trywialny dla kompletnych wykresów.

Wydaje się, że znalezienie ścieżki minimalnego kosztu w ramach opóźnienia (zwanego również problemem Ograniczonej Najkrótszej Ścieżki) jest tutaj odpowiednie.

$G=(V,E)$$d:V\to\mathbb {N}^+$$c:\to\mathbb {N}^+$$D\in \mathbb {N}^+$$s,t\in V$

$s-t$$D$

$\forall v\in V:d(v) =1$$hop-count$

Jeśli problem jest ważony, staje się Ograniczoną Najkrótszą Ścieżką , o której wiadomo, że jest NP-zupełny nawet na DAG.

Problem Lokalne maksymalne cięcie w sąsiedztwie FLIP jest kompletne z PLS na ogólnych wykresach ważonych liczbami całkowitymi.

AA Schaeffer i M. Yannakakis. (1991). Proste lokalne problemy wyszukiwania, które są trudne do rozwiązania. SIAM Journal on Computing, 20 (1): 56–87.

Jeśli jednak największa waga ma wielomian w wielkości wykresu, wówczas lokalne ulepszenia potencjału (masy nacięcia) zbiegną się w czasie wielomianowym, ponieważ każda poprawa zwiększy funkcję potencjalną o co najmniej jedną, a funkcja potencjalna jest wielomianowo ograniczony. (W przypadku wag ogólnych znalezienie rozwiązania możliwego do uzyskania dzięki lokalnym ulepszeniom z określonego początkowego cięcia jest kompletne dla PSPACE.)

Podobnie dzieje się w innych „potencjalnych grach”.

Podróżujący sprzedawca jest otwarty na sprzedawanych grafach siatkowych, ale cykl Hamiltona (wariant nieważony) jest znany jako wielomianowy.

Dyskusja obu na temat projektu otwartych problemów:

http://cs.smith.edu/~orourke/TOPP/P54.html

W wersji 2K_1 Maksymalne cięcie jest wielomianowe, a ważone maksymalne cięcie jest NP-kompletne.