An instance of the SET-PACKING problem is given by a list of sets $\mathcal{S} = \{S_1,\dots,S_m\} \subseteq 2^U$. It is a ``yes'' instance iff there exists some subset $\mathcal S'$ of $\mathcal S$ of size $\ge k$ such that for every $S,T \in \mathcal S'$, $S\cap T = \emptyset$.

Now, I propose the "promise variant" of this problem: I am telling you that your instance is a yes instance; that is, there exists some $\mathcal T'\subseteq \mathcal S$ such that all elements of $\mathcal T'$ are disjoint and it is of size $\ge k$. Can you find some $\mathcal S'$ that is of size $\ge k$ with all disjoint elements?

This seems to be an obviously NP-hard problem, but one needs to be slightly careful in the proof: intuitively, simply taking an instance of SET-PACKING and appending k arbitrary disjoint sets will work (informally, if finding them is in P, then SET-PACKING is also in P).

This relates to a similar question that appeared in cs.stackexchange. I am aware that promise variants of NP hard problems are generally hard (that is, given an NP hard problem X, define promise-X to be the problem X when a yes instance is guaranteed).

up vote 1 down vote accepted

Suppose that there was a polynomial time algorithm $A$ for your promise problem, say with time complexity bounded by $const*|U|^a*m^b$.

Take an arbitrary instance of SET-PACKING (the original variant, not the priomise variant) and run algorithm $A$ on it for $2*const*|U|^a*m^b$ steps. If $A$ does not terminate within this time bound, the answer must be NO. If $A$ does terminate, verify whether the output produced by $A$ indeed is a feasible solution.

This would allow you to solve the original SET-PACKING problem in polynomial time.

  • I'd say something like this - if the algorithm throws an exception or does not accept instances for which SET-PACKING is no: it's able to distinguish between yes and no instances of SET-PACKING. If it accepts either yes or no instances of SET-PACKING, and just returns meaningful input on yes instances, then it is able to decide SET-PACKING (here the fact that SET-PACKING is in NP is important, since it allows us to verify output feasibility in poly-time). – Yair Zick Jan 12 '15 at 19:56

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.