Dowód kompletności NP problemu z drzewem opinającym

Szukam wskazówek w pytaniu zadanym przez mojego instruktora.

Właśnie dlatego doszedłem do wniosku, że problemem decyzyjnym jest :$\sf{NP\text{-}complete}$

Na wykresie znajduje się drzewo rozpinające w G, które zawiera dokładny zestaw S = { x 1 , x 2 , … , x n } jako liście. I zdobione można wykazać, że N P - c o m s l e t e poprzez ograniczenie ścieżki Hamiltona ten problem decyzji.$G$$G$$S=\{x_1, x_2,\ldots, x_n\}$$\sf{NP\text{-}complete}$

Ale mój instruktor zapytał nas również w klasie:

czy byłoby to również jeśli zamiast „dokładnego zestawu S ”, robimy$\sf{NP\text{-}complete}$$S$

„obejmują cały zestaw i ewentualnie inne liście” lub „podzbiór S ”$S$$S$

Myślę, że „podzbiorem S” byłoby , ale po prostu nie mogę tego udowodnić, nie wiem, jaki problem mogę do tego zredukować. Jeśli chodzi o „dołącz zestaw S ...” myślę, że można go rozwiązać w czasie wielomianowym.$\sf{NP\text{-}complete}$$S$

Krótko mówiąc, twoje domysły są prawidłowe. Na potrzeby tej odpowiedzi nazwijmy trzy omawiane problemy w następujący sposób:

• Wersja równość: z uwagi wykres , a zestaw S ⊆ V decyduje, czy G ma drzewa rozpinającego T tak, że zbiór liści , T jest równe S . Jak już wspomniałeś, jest to NP-zupełne dzięki zmniejszeniu problemu ścieżki hamiltonowskiej.$G = (V, E)$$S \subseteq V$$G$$T$$T$$S$
• Wersja podzbiorem: Biorąc pod uwagę, i S jak wyżej, może zadecydować, czy G posiada drzewo rozpinające T taki, że zbiór liści T jest podzbiorem S .$G$$S$$G$$T$$T$$S$
• Wersja rozszerzeniem: Biorąc pod uwagę, i S jak wyżej, może zadecydować, czy G posiada drzewo rozpinające T taki, że zbiór liści T jest rozszerzeniem S .$G$$S$$G$$T$$T$$S$

Aby udowodnić, że wersja podzbioru jest kompletna z NP, nadal możesz zredukować do niej problem ścieżki Hamitonian. Spróbuj zmodyfikować dowód kompletności NP wersji równości.

Aby udowodnić, że wersja rozszerzeniem można rozwiązać w czasie wielomianowym, spróbować znaleźć warunek konieczny i wystarczający dla takiego drzewa istnieć.$T$

Obie wersje (jak również niektóre inne problemy dotyczące drzew opinających) są badane w [SK05]. Ale myślę, że lepiej jest, jeśli spróbujesz rozwiązać problemy samodzielnie, zanim spojrzysz na dowody w gazecie, ponieważ patrzenie na papier może być dużym spoilerem. Niestety spojrzałem na artykuł przed próbą znalezienia algorytmu czasu wielomianowego dla wersji superset!

[SK05] Mohammad Sohel Rahman i Mohammad Kaykobad. Złożoność niektórych interesujących problemów na drzewach opinających. Information Processing Letters , 94 (2): 93–97, kwiecień 2005. [ doi ] [ autor ]

Te wskazówki nie były wystarczające, aby doprowadzić mnie do rozwiązania problemu nadzbiórki S - chociaż wskazówki są pomocne i poprawne. To mój ciąg myśli, który doprowadził mnie do rozwiązania.

Co się stanie, jeśli usuniesz wszystkie wierzchołki w S z G, (VS), a następnie znajdziesz drzewo rozpinające T z DFS? Jeśli w G są jeszcze niepołączone wierzchołki, powiedz v1; co to mówi o roli, jaką usunięto co najmniej jeden z wierzchołków w S? Że leży na ścieżce do v1 z jakiegoś wierzchołka, który jest obecnie w drzewie rozpinającym. Zatem nie może to być liść (ponieważ liście nie mają dzieci). Jeśli nie ma niepołączonych węzłów, oznacza to, że każdy wierzchołek w S może być liściem, pod warunkiem, że ma krawędź prowadzącą do drzewa opinającego. Wierzchołki w S, które łączą się tylko z innymi wierzchołkami w S, oczywiście nie będą miały połączenia z drzewem opinającym i naruszyłyby ten warunek. Istnieją więc dwa przypadki, aby sprawdzić:

1. Jeśli wszystkie węzły spoza S są połączone po usunięciu S z G i znalezieniu drzewa opinającego
2. Jeśli każdy węzeł w S można podłączyć bezpośrednio do drzewa opinającego.