Talk:Dominating set

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

illustration[edit]

I'd quite some trouble seeing the difference between NODE COVE and DOMINATING SET. Its easy to interpret the definition so that they are identical. Thats why I think this article would benefit from some sort of illustration to the problem.83.249.48.221 08:30, 11 December 2006 (UTC)A[reply]

validity[edit]

I wonder about the reduction used in the proof. If G is not connected, it fails because vertices V of degree 0 are not required to be members of C, but must be members of C if C is a dominating set of G'. (Trivially: Suppose vertex v of degree 0 is not in the dominating set. Then by definition, it must be joined to a member of the dominating set by an edge. But by definition, v has no incident edges. This is a contradiction; consequently, v must be a member of the dominating set.)

Presumably this could be addressed by defining G'=(V',E) where V' = {all vertices v in V such that degree(v) > 0}?

For that matter, I still have problems with the construction of G' to assist with proving that the existence of a dominating set for G' implies the existence of a vertex cover for G. I can see that having vertex "vw" covered by D implies that edge (v,w) is covered, but how do we ensure D is a proper subset of V (i.e. it does not contain any of the vertices created by the transformation)?

Scott 03:38, 14 April 2007 (UTC)[reply]

Merger proposal[edit]

I have proposed that Dominating set problem is merged to this page. Some thoughts:

  • Recent edits show that the idea of keeping combinatorial and algorithmic aspects on separate pages does not work well. There is a lot of overlap between the two pages; moreover, some algorithmic aspects are now covered in much more detail on this page, even though the original idea seems to be to cover them in Dominating set problem.
  • In general, having separate pages for "X" and "X problem" seems to lead to confusion and overlapping content. (And even if the pages were perfect, there is confusion in other parts of Wikipedia: when creating wikilinks, people pick either "X" or "X problem" somewhat randomly.)
  • I think that pages such as Vertex cover and Matching (graph theory) are fairly good examples demonstrating that we do not need to have separate pages for "X" and "X problem".
  • There is related discussion in Talk:Independent set (graph theory)#Merger proposal.

Any thoughts? — Miym (talk) 09:32, 31 October 2009 (UTC)[reply]

Merging them seems like a good idea. --Robin (talk) 21:06, 5 December 2009 (UTC)[reply]
Definitely a good idea. I think the actual algorithm to calculate the dominating set is notable and of intrinsic interest, but that's not here just a proof that the problem is NP complete. There's no need for two pages on this subject even including both an algorithm and the computational complexity aspects. There's no talk about why people are interested in this either, surely there should be some references to its use in things like optimising compilers and linking subroutines? The current contents are very one sided. Dmcq (talk) 15:06, 6 December 2009 (UTC)[reply]
Thanks for the comments. I started to merge the pages, but in the end it seemed that Dominating set is already in a fairly good shape and there was little useful content in Dominating set problem that was not yet covered. So I just redirected Dominating set problem here and did some minor editing; more to come later. If someone thinks we should have the detailed NP-completeness proof, feel free to copy it from the history of Dominating set problem (and add references!). Fixed-parameter tractability could be covered here as well, but the relevant paragraph in Dominating set problem was unreferenced, so perhaps that's easier to rewrite from scratch. — Miym (talk) 22:18, 7 December 2009 (UTC)[reply]
I would have actually kept the NP-completeness proof and section on FPT and marked it with a [citation needed] tag. I don't know where to find info about FPT. The NP-completeness proof is probably the same as in Garey & Johnson. --Robin (talk) 22:44, 7 December 2009 (UTC)[reply]
I tried to add the NP-completeness proof, but I had some difficulties believing that a reader would happily accept that vertex cover is NP-complete and would be interested to see a reduction from vertex cover to dominating set. Even though this is historically "correct", nowadays it seems to be completely backwards. I think I'd rather give a reduction that shows that dominating set is as hard to approximate as set cover (e.g. [1], p. 108-109); this would not only show the NP-completeness (by a reduction from one of Karp's problems to keep everyone happy) but also explain the inapproximability result. What do you think? — Miym (talk) 23:15, 7 December 2009 (UTC)[reply]
That's fine too. I don't know which problem is used for the inapproximability reduction, but there should be some proof of NP-completeness, not necessarily rigorous, but just a rough sketch. If it's easier to reduce from set cover, that reduction can be given instead. --Robin (talk) 23:45, 7 December 2009 (UTC)[reply]
Actually, as a student learning these algorithms, I would like to see the NP-completeness proof using vertex cover. I found that version out in Google cache, and hope it could be added back. – PeterCX&Talk 13:43, 11 December 2009 (UTC)[reply]
By the way, you can find the old version here: [2]. — Miym (talk) 21:55, 13 December 2009 (UTC)[reply]
I have now sketched the reductions; feel free to edit. I don't think there is need to give a different reduction from vertex cover; after all, the vertex cover problem is a special case of the set cover problem. What do you think? — Miym (talk) 23:08, 15 December 2009 (UTC)[reply]
Looks good. Good job. --Robin (talk) 14:24, 16 December 2009 (UTC)[reply]

Applications[edit]

As Dmcq commented above in #Merger proposal, we should mention some applications of dominating sets. There are hundreds (thousands?) of papers that study dominating sets (and connected dominating sets) in the context of wireless ad hoc networks, sensor networks, etc. However, I have no idea if any of these problem motivations are real. Does anyone happen to have a reference that describes some actual (and not just potential) real-world use? — Miym (talk) 23:27, 7 December 2009 (UTC)[reply]

I was thinking about the Dominator (graph theory) rather that the dominating set, sorry. Dmcq (talk) 09:08, 16 December 2009 (UTC)[reply]

External links modified[edit]

Hello fellow Wikipedians,

I have just modified one external link on Dominating set. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 23:44, 14 December 2016 (UTC)[reply]

Bad reference[edit]

doi:10.1145/258533.258641 is not related to dominating set problem, this reference is confusing and should be fixed. — Preceding unsigned comment added by 86.57.154.43 (talk) 11:32, 15 November 2017 (UTC)[reply]

Incorrect statement[edit]

In the “Dominating and independent sets” section, the first paragraph states:

> Dominating sets are closely related to independent sets: an independent set is also a dominating set if and only if it is a maximal independent set, so any maximal independent set in a graph is necessarily also a minimal dominating set.

Yet this is untrue for the cyclic graph of order 3. 2A02:8428:1B19:3D01:D185:9FBF:AEC1:4BB (talk) 09:30, 9 February 2024 (UTC)[reply]

Seems ok to me: the maximal independent sets in C_3 consist of one vertex, and these are the same as the minimal dominating sets. --JBL (talk) 17:40, 9 February 2024 (UTC)[reply]
Indeed. I thought I was on the vertex cover page. Sorry about that. 37.66.63.122 (talk) 23:19, 9 February 2024 (UTC)[reply]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Dominating_set&oldid=1205561584"