Talk:Vertex cover

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Mid-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Mid Priority
 Field: Discrete mathematics
WikiProject Computer science (Rated C-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 

Tree Minimal Vertex Cover[edit]

The reference to [1] contains an error in the algorithm as explained by mmiguel.martin. I added an alternative algroithm that suppose to do that but I didn't find any reference, I found the algorithm in a test solution of a course in the Open University of Israel. — Preceding unsigned comment added by 37.46.41.87 (talk) 11:42, 4 June 2016 (UTC)

Merge hitting set to set cover?[edit]

Should we merge everything from Vertex cover#Vertex cover in hypergraphs (and k-approximation of k-hitting set) to Set cover problem? The current situation is strange, as different aspects of the approximability of the set cover problem are discussed in different articles. — Miym (talk) 22:41, 9 November 2009 (UTC)

Hitting Set and Set Cover are two different views on the same problem. However, I think that the bounded edge size view on hitting set is more natural than the bounded frequency view on set cover. Therefore, I'd vote to merge k-approximation of k-hitting set into Vertex cover#Vertex cover in hypergraphs and tidy up the situation in Set cover problem a little. Agreed? ylloh (talk) 14:18, 11 November 2009 (UTC)
  • To give some examples of how other sources handle this confusion, see [2] and [3]. Vazirani's textbook ("Approximation Algorithms", Springer 2003) seems to present everything (including k-approximation of k-hitting set) from the perspective of set covering. — Miym (talk) 14:55, 11 November 2009 (UTC)
In a textbook or a lecture, it's good to only have few example problems since they are to be read or taught from start to end. This does not hold for wikipedia. Also I wouldn't want to do it like wwwcompendium as this may not be a good example. ylloh (talk) 14:40, 13 November 2009 (UTC)
I don't know much about the subject matter, but k-approximation of k-hitting set should definitely be merged with something else. --Robin (talk) 20:06, 12 November 2009 (UTC)

Claim not supported by reference[edit]

The article claimed that vertex cover remains NP-complete

even in planar graphs of degree at most 3.

with a reference to Garey and Johnson (1977). I checked my copy and the claim is not supported there. According to page 190 it is the problem of connected vertex cover (where the set of vertices is required to be connected) that remains NP-complete for planar graphs. So I removed the claim. Gdr 10:42, 23 March 2012 (UTC)

Look again. On p.190 it says that vertex cover has the same complexity as independent set for any class of graphs and on p.195 it says that independent set is NP-complete for planar 3-regular graphs. —David Eppstein (talk) 17:46, 23 March 2012 (UTC)
Thanks, David. Sorry to have misunderstood. Gdr 13:44, 27 April 2012 (UTC)