NP-Complete Graph optimization: minimal node selection?

Question

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.

Answer 1

This is exactly the minimum vertex cover problem which is known to be NP-complete. The key insight in seeing that computing the size of a minimum vertex cover is equivalent to computing the size of a maximum independent set is the following:

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

In particular, this means that the total number of vertices is equal to the size of a minimum vertex cover plus the size of a maximum independent set. This illustrates nicely how computing one number reduces to computing the other.