Talk:Set cover problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
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.
 

What does it mean to call the decision problem NP-complete and the optimization problem NP-hard? NP-hardness refers to decision problems. Isn't #P-completeness the notion we are after for the optimization part?

NP-Complete means that the problem is both NP-Hard (harder than any other problem in NP) as well as in NP (meaning a given solution can be verified in polynomial time). We can verify that a solution to the decision problem is valid in polynomial time (by simply checking if there are at most k sets used in the solution, and whether those sets actually do cover U). However, it is more difficult to verify a solution to the optimization problem, as we have to check whether the given solution is in fact the optimal one (which can't be done in polynomial time). This means the optimization problem is not in NP, and therefore cannot be NP-Complete. So no, NP-hardness does not always refer to decision problems. —Preceding unsigned comment added by 128.113.55.43 (talk) 02:45, 22 April 2008 (UTC)

NP is a class of decision problems, so an optimization problem cannot be in NP *by definition*. Your argument is a red herring (in particular since it is probably difficult to prove that deciding whether a given solution is optimal cannot be done in polynomial time). --Mellum (talk) 12:35, 12 May 2008 (UTC)


I believe that set packing and hitting set are duals of one another, not set cover and hitting set, as indicated in "related problems." Set cover and hitting set are both minimization problems. —Preceding unsigned comment added by 132.236.215.11 (talk) 16:12, 4 September 2008 (UTC)

True. I corrected that and added a template Template:Covering-Packing_Problem_Pairs with the goal to collect all important covering problems together with their LP-dual problems. ylloh (talk) 17:50, 11 March 2009 (UTC)

Hitting set and set cover[edit]

There is some discussion related to this page at Talk:Vertex cover#Merge hitting set to set cover?; comments welcome. — Miym (talk) 14:49, 11 November 2009 (UTC)

Oops[edit]

Thanks for fixing my change Miym, i must have misclicked in some way. —Preceding unsigned comment added by 129.132.57.162 (talk) 14:22, 30 November 2009 (UTC)

m and n[edit]

Hi everyone, There is a mistake in this article: the universe should contain n elements instead of m, and the collection of subsets should be of size m instead of n. This way, the approximability and inapproximability section become correct. — Preceding unsigned comment added by 89.159.247.99 (talk) 20:56, 8 May 2012 (UTC)

NP-complete?[edit]

The decision version of set covering is NP-complete, and the optimization version of set cover is NP-hard.

Isn't the optimization version NP-complete, too? — Preceding unsigned comment added by 134.95.82.23 (talk) 08:51, 8 March 2013 (UTC)