HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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?

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.