Meeting rooms on university campuses may or may not contain coff ee machines. We would
like to ensure that every meeting room either has a coff ee machine or is close enough to a
meeting room that does have a co ffee machine. (For any two meeting rooms, the architect
has told us whether or not they are close enough.) Our problem is to determine among all the
meeting rooms of any university campus, which ones should have coff ee machines so that we
use as few co ffee machines as possible. Specify this problem as an optimization problem on a
graph. Formulate the corresponding Coff ee-machine Decision Problem (abbreviated Coff ee).
Prove that the Coff ee Machine Decision Problem is NP-complete.

Hint: You could use Vertex Cover. For every edge, add two more edges and one more vertex.