patternMinor
Any suggestions about a known NP-complete problem that can be reduced to the following problem?
Viewed 0 times
problemcantheanyfollowingcompletethatknownaboutsuggestions
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?
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?
Solution
This problem is called Dominating Set, and as pointed out by Raphael in the comments it's a special case of Set Cover (for each vertex, create a set for it and its neighbours). It's NP-hard.
Context
StackExchange Computer Science Q#64995, answer score: 3
Revisions (0)
No revisions yet.