Meeting rooms on university campuses may or may not contain coffee machines. We would like to ensure that every meeting room either has a coffee machine or is close enough to a meeting room that does have a coffee 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 coffee machines so that we use as few coffee machines as possible. Specify this problem as an optimization problem on a graph. Formulate the corresponding Coffee-machine Decision Problem (abbreviated Coffee). Prove that the Coffee Machine Decision Problem is NP-complete.
Hint: You could use Vertex Cover. For every edge, add two more edges and one more vertex.