algorithm - NP-完全图优化 : minimal node selection?

Question

假设您有一个图 G = (V, E) 表示单层购物中心的平面图。各个商店由顶点表示，顶点之间的边表示一些任意定义的彼此靠近的商店。

最近，该购物中心发生的入店行窃事件有所增加，因此管理层决定让每家商店:

• 里面有保安人员驻守

• 或者靠近有保安的商店

同时雇佣尽可能少的保安人员。

您如何证明这个优化问题是 NP 完全问题？我觉得这是独立集问题的简单归约，但我想确定一下。

Answer 1

这正是 minimum vertex cover problem已知它是 NP 完全的。看到计算最小顶点覆盖的大小等同于计算最大独立集的大小的关键见解如下:

一组顶点是一个顶点覆盖，当且仅当它的补集是一个独立的集合。

特别地，这意味着顶点总数等于最小顶点覆盖的大小加上最大独立集的大小。这很好地说明了计算一个数字如何减少到计算另一个数字。