1

Suppose you have a graph G = (V, E) that represents the floor plan of a one-story shopping mall. The individual stores are represented by vertices, and the edges between vertices represent some arbitrary definition of stores being close to each other.

Recently, there has been an increase in the amount of shoplifting that occurs in this mall, so management decides to make it so that every store either:

  • Has a security guard stationed in it

  • Or is close to a store that has a security guard stationed in it

While hiring as few security guards as possible.

How would you prove this optimization problem is NP-complete? I feel like it's a simple reduction from the independent set problem, but I want to make sure.

4

1 回答 1

2

这正是已知的 NP完全的最小顶点覆盖问题。看到计算最小顶点覆盖的大小等同于计算最大独立集的大小的关键见解如下：

A set of vertices is a vertex cover, if and only if its complement is an independent set.

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

于 2013-04-18T21:23:07.943 回答