2
$\begingroup$

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).

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – Spark
    Jan 12, 2015 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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