Loại bỏ các đỉnh cho đến khi không còn cạnh nào

Question

Cho một đồ thị vô hướng G (V, E), hãy tìm số đỉnh nhỏ nhất cần loại bỏ để Tập cạnh của đồ thị trở nên trống.

Nói cách khác: Nếu chúng ta loại bỏ một đỉnh, chúng ta loại bỏ đỉnh đó cùng với tất cả các cạnh nối với đỉnh đó. Tìm số đỉnh tối thiểu cần loại bỏ để không còn cạnh nào trong G sau khi loại bỏ chúng.

Answer 1

Có vẻ như bạn đã tự mình tìm ra câu trả lời, bạn đang mô tả Vertex Cover , về nhiều mặt rất giống với Independent Set, cả hai vấn đề đều là NP-hoàn chỉnh .

Mối quan hệ với Tập hợp độc lập là trong một biểu đồ $G = (V,E)$, một bộ $S$ là một phủ đỉnh tối thiểu nếu và chỉ khi $V \setminus S$ là một tập độc lập cực đại.

Nếu bạn biết rằng Bộ độc lập là NP-hoàn chỉnh, thì điều đó có nghĩa là Vertex Cover cũng là NP-hoàn chỉnh.

Nói cách khác, bạn cũng đang tìm kiếm một Tập hợp Độc lập tối đa.

Vỏ đỉnh . Cho một đồ thị$G = (V,E)$ và một số nguyên $k$, có tồn tại một tập hợp không $S \subseteq V$ có kích thước tối đa $k$ sao cho tất cả các cạnh trong $G$ là sự cố đến một đỉnh trong $S$?

Bộ độc lập . Cho một đồ thị$G = (V,E)$ và một số nguyên $k$, có tồn tại một tập hợp không $S \subseteq V$ có kích thước ít nhất $k$sao cho đồ thị cảm ứng $G[S]$ không có cạnh?