删除顶点，直到没有留下边缘

Question

给定无向图G（v，e），找到要删除的最小顶点数量，使得图形的边缘集变为空。

换句话说：如果我们删除一个顶点，我们将删除顶点以及连接到该顶点的所有边缘。找到要删除的最小顶点数量，以便在删除后G中没有留下的边缘。

Answer 1

听起来你自己找到了答案，你正在描述顶点封面，哪个许多方式与独立集非常相似，这两个问题都是 np-complete 。

与独立集的关系是，在图 $ g=（v，e）$ ，一个set $ S $ 是一个最小的顶点封面，如果且仅当 $ v \ setminus s $ 是一个最大独立集。

如果您知道独立集是NP-Created，那么它遵循顶点封面也是NP-Create。

换句话说，您也在寻找最多独立的集合。

顶点封面。给定图 $ g=（v，e）$ 和一个整数 $ k $ ，是否存在SET $ S \ SUBSETEQ V $ 大多数 $ k $ ，使得 $ g $ 在 $ s $ 中的顶点上是一个顶点的意图？

独立集。给定图 $ g=（v，e）$ 和一个整数 $ k $ ，是否存在一个set $ s \ subseteq v $ 大小至少 $ k $ ，使得引起的图 $ g [s] $ 没有边缘？