3
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Oct 23 '16 at 4:49
  • 1
    $\begingroup$ Indeed, it seems that this is itself a well-known NP-complete problem, one of the oldest. $\endgroup$ – Nate Eldredge Oct 23 '16 at 5:59
  • $\begingroup$ "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. $\endgroup$ – Raphael Oct 23 '16 at 12:45
  • 2
    $\begingroup$ @GerhardPaseman It's not (plain) Vertex Cover. For instance, a triangle requires two nodes to vertex-cover but only one node to mcdonalds-cover. $\endgroup$ – Raphael Oct 23 '16 at 12:47
  • 1
    $\begingroup$ Hint: Removing set dressing, this is pretty much Set Cover. $\endgroup$ – Raphael Oct 23 '16 at 12:50
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy