| <kentyman> | Show the following problem is NP-complete:Â The dominating-set problem:Â given a graph G and an integer k, does there exist a subset S of G with k nodes such that each node is either in S or adjacent to a node of S? |
|
<Oax> | exactly k nodes |
|
<kentyman> | yes, but adding nodes wouldn't change it, no? |
|
<Oax> | no |
|
<Oax> | it's monotone |
|
<kentyman> | like my prof |
Similar:
| Chat 9053 | lib1790: so, at this college there was an extra credit question "Is hell endothermic or exothermic" ... |
| Chat 731 | Shadowless: How can I tell if I'm circumsized or not? From everyone's descriptions, I'm assuming I am not. I think I even rec... |
| Chat 7329 | h0ward: it began with the forging of the great servers ... |
| Chat 19406 | freud: once i found a gummybear in my computer ... |
| Chat 21536 | helf: my trip was stupid. it was my fault :P the problem that is. i had forgotten and left automatic updates enabled.. so it would download ... |
| Chat 23003 | mikeash: ok, look, if there's a specific problem that prompted you to come in here ... |
| Chat 17010 | Sketchee: Ok. How does the game connection work? ... |
| Chat 2875 | nick: FUCKING HELL!!!! ..
nick: I swear one day I'm just gonna go and hunt down every stupid bitch on earth and put them out of their... |
| Chat 2245 | Helix: fuck ..
Helix: my back right tire is flat ... |