Trudne problemy z NP na drzewach

47

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.

Shiva Kintali
źródło
1
Jukka, dyskusyjne jest, czy konieczne jest tutaj „wiki społeczności”. Oczywiście wymyślone problemy o małym znaczeniu prawdopodobnie i tak zostaną odrzucone.
Ryan Williams,
1
Skłaniam też do myślenia, że ​​CW nie jest konieczne
Suresh Venkat
2
Nie jestem pewien, czy CW jest potrzebny. Nie mogę wymyślić żadnego problemu z głowy. Wydaje się, że plakaty powinny być nagradzane za odpowiedź na to pytanie.
Robin Kothari,
5
Niektóre losowe hity Google w artykułach naukowych, które pokazują, że problem jest trudny do NP, nawet jeśli dane wejściowe to drzewo:
pojemny
4
Nie o to prosiłeś, ale warto o tym wspomnieć: są pewne problemy, które są łatwe na drzewach, ale trudne na ograniczonej szerokości. Na przykład ścieżki rozłączne krawędzi (Nishizeki, Vygen, Zhou '01) i rozpiętość macierzy wiązań (McDiarmid, Reed '03).
Diego de Estrada,

Odpowiedzi:

23

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:

(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?GWC1C2GWG

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

Jukka Suomela
źródło
Szkoda, że ​​kompendium nie jest już aktualizowane.
Anthony Labarre,
Co to jest „wykres ścieżki oznaczonej”?
David
29

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 .

David Eppstein
źródło
To implikuje twardość prostoliniowego rysowania drzew? Czy istnieje określony stopień zachowania twardości?
Mohammad Al-Turkistany,
2
Re związany ze stopniem: jeśli istnieje wierzchołek stopnia większy niż cztery, wówczas osadzanie siatki nie jest możliwe.
David Eppstein,
Dzięki David, proste stwierdzenie, ale ciekawy problem.
Mohammad Al-Turkistany
Drzewo wejściowe jest również drzewem binarnym. To wspaniale!
Cyriak Antony,
24

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ąguG=(V,E)S1,S2,,SkO(logn)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(log2ϵn)ϵ>0O(log2n)

Chandra Chekuri
źródło
4
Aaah: niesformatowany lateks !! boli oczy :)
Suresh Venkat
Cóż, nie wiem jak tutaj formatować lateks :). Wskaźniki?
Chandra Chekuri,
po prostu użyj $ .. $ jak zwykle.
Suresh Venkat
ok wszystko już naprawione.
Suresh Venkat
22

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

Mohammad Al-Turkistany
źródło
1
Poprawioną wersją papieru Ungera są wyniki twardości dla przybliżenia przepustowości , Chandan Dubey, Uriel Feige i Walter Unger.
Yuval Filmus
8

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.

Suresh Venkat
źródło
8

TV(T)kϕ:V(T){1,,k}Tii+1KK

k

użytkownik13136
źródło
8

Kolorystyka Imperium jest trudna dla drzew.

rsGr(s,r)sCOLrGs

sCOLrs{3,,2r1}s

Jens G.
źródło
6

TSTT1TSTT1T

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

Gianluca Della Vedova
źródło
6

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.

Ashutosh Rai
źródło
5

uu

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.

Michael Lampis
źródło
1
To niezły problem!
Tayfun Zapłać
3

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.

SCG=(V,E)SVCVSC=sS|s|FfF|f|eEteRC×F(c,f)Rcf

sSAsfAs|f||s|PrGr=(c,f)RcsfAseDer=(c,f)DePre(c,f)De|f|te

Jeśli nie wymagają wszystkie pobrane pliki mają być kierowane lecz starają się maksymalizować sumę filesizes tych pliki do pobrania, które 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.

USP(U)uU

sSusu

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.

Alex ten Brink
źródło
3

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

Arindam Pal
źródło
3

G(V,E)NP

Formalnie problemem jest:

IZOMORFIZM WYKRESU DZIAŁANIA

T=(V,E)

{E1,E2}ET1=(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

Mohammad Al-Turkistany
źródło
2

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 ].

Ashutosh Rai
źródło
2

nknk

użytkownik1105
źródło
-1

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.

2k1

Chad Brewbaker
źródło
1
Umm, obwody, które są drzewami, mają nazwę: formuły. Formuła SAT jest oczywiście NP-zupełna, ponieważ 3-SAT lub nawet pełna CNF-SAT to jej szczególne przypadki.
Emil Jeřábek
1
Jak to? Wszystkie formuły są drzewami. Jeśli chcesz ograniczyć wiele wystąpień zmiennych, jest to dodatkowe ograniczenie. (Zakładam również, że pisząc „dane wejściowe”, naprawdę masz na myśli „literały”, ponieważ obwód SAT z tylko AND, OR i literałami dodatnimi jest trywialnie wielomianowy czas na początek.)
Emil Jeřábek
1
((a+b)+c)+d((a+b)+c)+a
1
(pq)p
1
To nie jest problem z zabawkami. Jest to standardowa terminologia, gdy kiedy mówimy, że obwód jest drzewem, nie oznacza to, że zmienne pojawiają się tylko raz. W każdym razie i niezależnie od tego, jak to nazywamy, proponowany przez ciebie problem jest trywialny, jak pisałem.
Kaveh