Trudne problemy z NP na drzewach

Kilka problemów optymalizacyjnych, o których wiadomo, że są trudne do NP na grafach ogólnych, można w prosty sposób rozwiązać w czasie wielomianowym (niektóre nawet w czasie liniowym), gdy grafem wejściowym jest drzewo. Przykłady obejmują minimalną osłonę wierzchołków, maksymalny niezależny zestaw, izomorfizm subgrafu. Wymień niektóre naturalne problemy z optymalizacją, które na drzewach są trudne do NP.

Można znaleźć „naturalne” i „dobrze znane” przykłady problemów graficznych, które są trudne, nawet jeśli ograniczają się do drzew z naszego standardowego źródła . Przykłady:

• Zintegrowany k -multicoorsity flow ,
• Wspólne osadzone poddrzewo ,
• Wspólne poddrzewo .

(Są one sformułowane jako problemy z drzewem, ale można je uogólnić na dowolne wykresy. Następnie powyższe formuły są uzyskiwane jako szczególny przypadek, gdy ograniczasz swój wkład do drzew.)

Bardziej ogólny przepis na generowanie problemy, które trudno na drzewach: Podjęcie jakichkolwiek NP-trudny problem związany z supersequences , superstrun , podciągi itp Następnie ponownie zinterpretować jako ciąg oznaczonego wykresu ścieżki. Następnie zadaj analogiczne pytanie dla grafów ogólnych (podsekwencja minor wykres mniejszy, podciąg ≈ podgraph). I wiemy, że problem jest trudny do przeprowadzenia nawet w przypadku drzew (i ścieżek).

Istnieje również wiele problemów, które są trudne dla ważonych gwiazd, poprzez redukcję problemu z sumą częściową. Naturalnym przykładem jest:

• TSP z dwoma podróżnikami : biorąc pod uwagę wykres ważony na krawędzi i granicę W , możemy znaleźć dwa zamknięte przejścia C 1 i C 2 w G tak, że każdy spacer ma całkowitą masę co najwyżej W , a każdy węzeł G jest objęty przez przynajmniej jeden spacer?$G$$W$$C_1$$C_2$$G$$W$$G$

Ponownie łatwo jest wymyślić różne motywy.

Jest NP-kompletny, aby ustalić, czy drzewo może zostać osadzone w dwuwymiarowej siatce liczb całkowitych, z wierzchołkami drzewa umieszczonymi w różnych punktach siatki, a krawędziami drzewa umieszczonymi na krawędziach siatki.

Patrz np. Gregori, IPL 1989 .

Problem grupy Steiner jest dobrym przykładem. Dane wejściowe do tego problemu to nieukierowany wykres ważony na krawędzi ik grupy wierzchołków S 1 , S 2 , … , S k . Celem jest znalezienie drzewa o minimalnej wadze, które zawiera co najmniej jeden wierzchołek z każdej grupy. Łatwo zauważyć, że problem z ustawieniem osłony jest szczególnym przypadkiem, nawet gdy G jest gwiazdą. Tak więc problem jest trudny do przybliżenia w ramach współczynnika O ( log n ) , chyba że P = NP. Co więcej, Halperin i Krauthgamer wykazali, że problem jest trudny do przybliżenia w ciągu$G=(V,E)$$S_1, S_2, \ldots, S_k$$O(\log n)$Współczynnik O ( log 2 - ϵ n ) dla dowolnego ustalonego ϵ > 0, chyba że NP ma randomizowane quasi-wielomianowe algorytmy czasowe (dokładne wyjaśnienie w artykule). Jest O ( log 2 n ) przybliżeniem na drzewach przez Garg, Konjevod i Ravi.$O(\log^{2-\epsilon} n)$$\epsilon > 0$$O(\log^2 n)$

Jednym z najtrudniejszych problemów na drzewach jest problem minimalnej przepustowości. To -hard na drzewach maksymalnego stopnia 3. Ponadto jest NP-trudny na okrągłej gąsienica długości włosów 1.$NP$

Bibliografia:

Michael R. Garey, Ronald L. Graham, David S.Johnson i Donald E. Knuth. Wyniki złożoności w celu minimalizacji przepustowości. SIAM J. Appl. Math., 34 (3): 477–495, 1978.

Burkhard Monien. Problem minimalizacji szerokości pasma dla gąsienic o długości włosów 3 jest NP-zupełny. SIAM J. Algebraic Discrete Methods, 7 (4): 505-512, 1986.

W. Unger. Złożoność przybliżenia problemu z przepustowością. W FOCS, strony 82–91, 1998

$G$$G$$k$$S$$k$$G$

Ten problem jest trudny NP (i MAX SNP-twardy) na gwiazdach [ 1 ].

[ 1 ] Garg, Vazirani i Yannakakis, Primal-Dual Approximation Algorytm for Integral Flow and Multicut in Trees , Al algorytmica, 18 (1), str. 3-20, 1997.

Problem strażaka zyskał ostatnio sporo uwagi i jest (nieco zaskakujący) trudny do naprawienia na drzewach o maksymalnym stopniu 3 . Jest to właściwie dość naturalne pytanie, opisane w następujący sposób:

$k$

Lub wariant, także trudny do NP : Czy istnieje strategia dla strażaka, w której nie pali się liść?

Problemem, który mógłby się wydawać, NIE byłby trudny dla drzew, ale jest problem polegający na zamrożeniu znaczników w geometrii obliczeniowej : krótko mówiąc, problem planowania budzeń dla robotów zaczynających się od pojedynczego przebudzonego bota, gdzie makespan jest miarą kosztów.

Wiadomo, że jest trudny do NP na ważonych grafach gwiazdowych. Jest jednak otwarte, czy problem jest trudny do NP w samolocie. Można argumentować, że twardość NP nie pochodzi z „drzewa”, ale z „arbitralnej metryki”, ale wykresy gwiezdne dają ci tylko ograniczoną przestrzeń metryk.

$T$$V(T)$$k$$\phi: V(T)\to \{1,\ldots, k\}$$T$$i$$i+1$$K$$K$

$k$

Kolorystyka Imperium jest trudna dla drzew.

$r$$s$$G$$r$$(s, r)$$s$$\text{COL}_r$$G$$s$

$s$$\text{COL}_r$$s \in \{3,\ldots, 2r − 1\}$$s$

Przepływ w sieci jest zlewny, jeśli wykorzystuje co najwyżej jeden łuk wychodzący w każdym węźle. Twardość NP wyznaczania maksymalnego przepływu konfluentnego w drzewie (o średnicy 4, z dozwolonymi wieloma zlewami) została udowodniona w: D. Dressler i M. Strehler, Capacitated Confluent Flows: Complexity and Algorytmy, LNCS 6078 (2010) 347-358 .

$TS$$T$$T_1\in TS$$T$$T_1$$T$

Problem jest trudny NP (w rzeczywistości trudno go oszacować) tylko wtedy, gdy wszystkie drzewa wejściowe mają nieograniczony stopień.

Harmonijne zabarwienie prostego wykresu to właściwe zabarwienie wierzchołków, dzięki czemu każda para kolorów pojawia się razem na co najwyżej jednej krawędzi. Harmonijna liczba chromatyczna wykresu to najmniejsza liczba kolorów w harmonijnej kolorystyce wykresu. Edwards i McDiarmid wykazali, że problem znalezienia harmonicznej liczby chromatycznej jest NP-zupełny na drzewach . W rzeczywistości pokazują również, że problem pozostaje NP-zupełny dla drzew o promieniu 3.

$u$$u$

Należy zauważyć, że w powiązanym (i bardziej znanym) problemie TSP celem jest zminimalizowanie maksymalnego, a nie średniego opóźnienia. Myślę, że TRP jest ogólnie uważany za bardziej skomplikowany problem (w rzeczywistości TSP jest w P dla wskaźników drzewa).

Twardość NP na drzewach została pokazana w RA Sitters „Problemem minimalnego opóźnienia jest NP-twardy dla drzew ważonych”, ISCO 2002.

Motyw graficzny to problem NP-Complete na drzewach o maksymalnym stopniu trzecim:

Faceci, Fertin, Hermelin i Fiolka, Ostre granice podatności na znajdowanie połączonych motywów na wykresach w kolorze wierzchołków Wykład notatki z informatyki, 2007, tom 4596/2007, 340-351

Jest (bardzo ogólny) problem, na który patrzyłem w ramach projektu: wariant tego problemu jest trudny do NP nawet na wykresach z dwoma wierzchołkami i jedną krawędzią, a inny wariant jest trudny do NP na drzewach. Ponieważ twardość NP pierwszego wariantu oczywiście nie wynika z kształtu wykresu, drugi jest prawdopodobnie bardziej interesujący.

$S$$C$$G=(V,E)$$S \subset V$$C \subset V$$S \cap C = \emptyset$$s \in S$$|s|$$F$$f \in F$$|f|$$e \in E$$t_e$$R \subseteq C \times F$$(c,f) \in R$$c$$f$

$s \in S$$A_s$$\sum_{f \in A_s} |f| \leq |s|$$P_r$$G$$r = (c,f) \in R$$c$$s$$f \in A_s$$e$$D_e$$r = (c,f) \in D_e$$P_r$$e$$\sum_{(c,f) \in D_e}|f| \leq t_e$

Jeśli nie wymagają wszystkie pobrane pliki mają być kierowane lecz starają się maksymalizować sumę filesizes tych pliki do pobrania, które są kierowane można łatwo zmniejszyć sumy podzbioru tego problemu: trzeba pojedynczy serwer z dużej ilości przestrzeni, pojedynczy klient podłączony do serwera o krawędzi o pojemności równej wartości docelowej instancji sumy częściowej i dla każdej liczby całkowitej w instancji sumy częściowej tworzony jest plik o równej wielkości; następnie klient chce pobrać wszystkie te pliki.

(Dużo?) Bardziej interesującym wariantem tego pytania jest to, że próbujesz zminimalizować liczbę krawędzi, których pojemność jest przekroczona - być może sieć, nad którą pracujemy, modeluje transatlantyckie kable internetowe i wymiana kabla jest tak kosztowna, że ​​różnica koszt ulepszenia do współczynnika dwa szybciej, a podwyższenie do współczynnika trzy szybciej jest nieistotna. Mówimy również, że rozmieszczenie plików na serwerach jest już podane i nie można go modyfikować, dlatego przyglądamy się wyłącznie problemom z routingiem.

$U$$S \subseteq P(U)$$u \in U$

$s \in S$$u \in s$$u$

Chodzi o to, że klient potrzebuje plików, które są unikalne dla wszystkich klastrów serwerów, więc krawędzie łączące klienta z klastrami serwerów są już na granicy swoich możliwości (ich pojemności to 1, pliki mają rozmiar 1). Jeśli klient pobierze dowolne elementy wszechświata z dowolnego klastra, krawędź łącząca się z tym klastrem zostanie przeciążona. Ponieważ wymagamy jedynie zminimalizowania liczbyprzeciążeń (a nie o ile przekraczamy pojemności), klient może pobrać resztę elementów wszechświata hostowanego w tym klastrze serwerów (a więc resztę elementów odpowiedniego podzbioru) bez kary. Odpowiada to zatem wybranemu podzbiorowi. Klient chce raz pobrać wszystkie pliki z wszechświata, więc wszechświat rzeczywiście zostanie objęty, a aby zminimalizować liczbę przeciążonych krawędzi, musimy zminimalizować liczbę wybranych podzbiorów.

Zauważ, że powyższa konstrukcja daje wykres drzewa, więc jest to przykład trudnego NP problemu na drzewach.

Problem niewypełnionego przepływu. W rzeczywistości UFP jest trudny nawet na jednej krawędzi (plecak).

$G(V, E)$$NP$

Formalnie problemem jest:

IZOMORFIZM WYKRESU DZIAŁANIA

$T = (V,E)$

$\{E1,E2 \}$$E$$T1 = (V,E1)$$T2 = (V,E2)$

Kolumna NP-zupełność cytuje niepublikowany manuskrypt Grahama i Robinsona, „Izomorficzna faktoryzacja IX: nawet drzewa”.

DS Johnson, Kolumna NP-kompletność: przewodnik w toku, Journal of Algorithms 3 (1982), 288–300

Jakoś mi brakowało problemu liczby achromatycznej w ostatniej odpowiedzi, ale jest to jeden z najbardziej naturalnych problemów, jakie znam, które są NP-zupełne na drzewach.

Kompletne zabarwienie wykresu to prawidłowe zabarwienie, dzięki czemu pomiędzy każdą parą klas kolorów jest krawędź. Zabarwienie można określić w przeciwieństwie do Harmonijnego zabarwienia, jako prawidłowe zabarwienie, dzięki czemu każda para kolorów pojawia się na co najmniej jednej krawędzi. Można to również określić jako całkowity (lub pełny) homomorfizm kliki. Problem liczby achromatycznej jest problemem maksymalizacji , w którym szukamy największej liczby klas kolorów w pełnym zabarwieniu wykresu.

Yannakakis i Gravil udowodnili, że ten problem jest trudny do przeprowadzenia na NP w uzupełnieniu grafów dwustronnych . Cairnie i Edwards rozszerzyli ten wynik i wykazali, że problem dotyczy NP na drzewach .

Wiele pracy poświęcono temu zagadnieniu w dziedzinie algorytmów aproksymacyjnych [ 3 , 4 , 5 ].

$n$$k$$\lceil\frac{n}{k}\rceil$

Czy obwód SAT na drzewach NPC ?. Wewnętrzne wierzchołki drzewa są oznaczone jako bramki OR / AND. Liście są wejściami. Ustal, czy istnieje zadowalający zestaw sygnałów wejściowych dla obwodu, który ma być oceniony na True.

$2^k - 1$