# Any suggestions about a known NP-complete problem that can be reduced to the following problem?

Given an undirected graph $G$, where nodes represent towns and edges represent roads, and given a positive integer $k$, is there a way to build $k$ McDonald's at $k$ different towns so that every town either has its own McDonald's, or is connected by a (direct) road to a town that does have a McDonald's?

I believe that this problem is NP-complete. I am trying to find a well-known NP-complete problem, so I can use it to prove that this problem is NP-complete, too. Any suggestions?

• Suggestion 1: read up on Vertex Cover. Suggestion 2: ask this on a different forum. This forum is intended for current research in mathematics, as opposed to topics in undergraduate computer science. Gerhard "Try A Computer Science Forum" Paseman, 2016.10.22. – Gerhard Paseman Oct 23 '16 at 4:49
• Indeed, it seems that this is itself a well-known NP-complete problem, one of the oldest. – Nate Eldredge Oct 23 '16 at 5:59
• "I believe that this problem is NP I am trying to find a well known NP complete problem, so I can use it to prove that this problem is NP-complete too." -- 1) Being NP is not the same as being NP-complete. I guess you mean the latter? 2) If this problem is indeed NP-hard, every NP problem reduces to it. Pick any. 3) You may profit from reading our reference questions on basics of complexity theory and common techniques for coming up with reductions. – Raphael Oct 23 '16 at 12:45
• @GerhardPaseman It's not (plain) Vertex Cover. For instance, a triangle requires two nodes to vertex-cover but only one node to mcdonalds-cover. – Raphael Oct 23 '16 at 12:47
• Hint: Removing set dressing, this is pretty much Set Cover. – Raphael Oct 23 '16 at 12:50