Usuń wierzchołki, aż nie pozostaną żadne krawędzie

Question

Mając niekierowany graf G (V, E), znajdź minimalną liczbę wierzchołków do usunięcia, tak aby zestaw krawędzi wykresu stał się pusty.

Innymi słowy: jeśli usuniemy jeden wierzchołek, usuniemy ten wierzchołek wraz ze wszystkimi krawędziami połączonymi z tym wierzchołkiem. Znajdź minimalną liczbę wierzchołków do usunięcia, aby po ich usunięciu nie pozostały żadne krawędzie w G.

Answer 1

Wygląda na to, że sam znalazłeś odpowiedź, opisujesz Vertex Cover , który pod wieloma względami jest bardzo podobny do Independent Set, oba problemy są NP-zupełne .

Relacja do zbioru niezależnego jest taka, jak na wykresie $G = (V,E)$, zestaw $S$ jest minimalnym pokryciem wierzchołków wtedy i tylko wtedy, gdy $V \setminus S$ jest maksymalnym niezależnym zbiorem.

Jeśli wiesz, że zestaw niezależny jest kompletny NP, wynika z tego, że pokrycie wierzchołka również jest kompletne w trybie NP.

Innymi słowy, szukasz również maksymalnego zestawu niezależnego.

Osłona wierzchołka . Biorąc pod uwagę wykres$G = (V,E)$ i liczba całkowita $k$, czy istnieje zestaw $S \subseteq V$ co najwyżej rozmiaru $k$ tak, że wszystkie krawędzie do wewnątrz $G$ są przypadkowe do wierzchołka w $S$?

Niezależny zestaw . Biorąc pod uwagę wykres$G = (V,E)$ i liczba całkowita $k$, czy istnieje zestaw $S \subseteq V$ wielkości co najmniej $k$taki, że indukowany wykres $G[S]$ nie ma krawędzi?