Hiçbir kenar kalmayana kadar köşeleri kaldırın

Question

Yönlendirilmemiş bir G (V, E) grafiği verildiğinde, grafiğin Kenar Kümesinin boş olması için kaldırılacak minimum köşe noktalarının sayısını bulun.

Başka bir deyişle: Bir tepe noktasını kaldırırsak, o tepe noktasına bağlı tüm kenarlarla birlikte o tepe noktasını da kaldırırız. Kaldırıldıktan sonra G'de kenar kalmaması için kaldırılacak minimum köşe noktası sayısını bulun.

Answer 1

Cevabı kendiniz bulmuşsunuz gibi görünüyor , birçok yönden Bağımsız Set'e çok benzeyen Vertex Cover'ı tanımlıyorsunuz , her iki problem de NP-tamamlandı .

Bağımsız Küme ile olan ilişki bir grafikte $G = (V,E)$, bir set $S$ minimal bir köşe kaplamasıdır ancak $V \setminus S$ maksimum bağımsız bir kümedir.

Independent Set'in NP-complete olduğunu biliyorsanız, o zaman Vertex Cover'ın da NP-tamamlandığını izler.

Başka bir deyişle, maksimum bir Bağımsız Set de arıyorsunuz.

Köşe kapağı . Bir grafik verildiğinde$G = (V,E)$ ve bir tam sayı $k$, bir set var mı $S \subseteq V$ en fazla boyut $k$ öyle ki tüm kenarlar $G$ bir tepe noktasıyla ilgili olay $S$?

Bağımsız set . Bir grafik verildiğinde$G = (V,E)$ ve bir tam sayı $k$, bir set var mı $S \subseteq V$ en azından boyut $k$öyle ki indüklenen grafik $G[S]$ kenarları yok mu?