2
$\begingroup$

I have the following algorithmic problem. I am given a set of elements. Each element has a set of properties. For example:

A: has properties p1, p2, p4
B: has properties p2, p4
C: has properties p2, p1

The task is to find the number of subsets of elements, where the union of the properties of the elements in the subset are equal to some predefined set.

For example if the predefined set is:

  • {p2}, then the answer is 0, because there are no subsets with a union of {p2}
  • {p1, p2, p4}, then the answer is 5, because we can take {A}, {A, B}, {A, C}, {B, C}, {A, B, C}

This problem seems like it might be hard (e.g., NP-hard), but I can not find anything similar in this list of NP-complete problems. I do realize that this is only small subset of NP complete problems.

Is there an efficient algorithm for this problem? Or, is it NP-hard, and if so, how can we prove that?

$\endgroup$
  • 3
    $\begingroup$ It's not clear that the decision version of this problem is even in NP. $\endgroup$ – Yuval Filmus Jul 9 '15 at 23:31
  • $\begingroup$ @YuvalFilmus yes, when I meant that I think it is NP, I was thinking about a decision version (is the answer 5?). And I am not sure whether it is NP or not. $\endgroup$ – randomizer Jul 10 '15 at 1:34
  • $\begingroup$ I agree with Yuval. It's still not clear whether the decision version is in NP. What's the witness/certificate that a specific instance is a "Yes" instance? The obvious candidate is to list all of the subsets that meet the condition, but this won't work if the number 5 is expressed in the input in binary: in general the length of a list of length $k$ will be exponential in the number of bits needed to represent $k$. $\endgroup$ – D.W. Jul 10 '15 at 1:40
  • 2
    $\begingroup$ Sets that are not subsets of the predefined set can't be used, since unions with such sets can't be subsets of the predefined set. ​ If the predefined set is not a subset of the union of the other sets, then the answer would be 0, since the predefined set also couldn't be a subset of the union of any number of the other inputs sets. ​ Thus, one may restrict to the case in which the predefined set is the union of the other input sets. ​ ​ ​ $\endgroup$ – user12859 Jul 10 '15 at 2:55
2
$\begingroup$

The problem is NP-hard: in fact, it is #P-complete. Therefore, it is unlikely you'll be able to find an efficient solution for this problem. The proof is by reduction from #Monotone-SAT.

As Ricky Demer explains, without loss of generality we can take the "predefined set" to be equal to the union of all properties. (If the predefined set is larger than that, the answer to your problem is 0. If the predefined set is smaller than that, then we can remove all elements that mention a property not found in the predefined set, and we get a new problem instance with the desired property.) So let's focus only on this case.

Here is the reduction from #Monotone-SAT. Suppose we have a CNF formula $\varphi$ over $n$ variables and with $m$ clauses, where all of the literals in each clause are positive (i.e., no variable is negated). Then we can define an instance of your problem that corresponds to $\varphi$. The problem instance has $n$ elements, one element for each variable, and $m$ properties, one property for each clause. The set of properties of a variable is just the set of clauses that mention that variable. Then the number of solutions to this problem instance is exactly the number of satisfying assignments to $\varphi$.

It follows that your problem is exactly as hard as #Monotone-SAT: any algorithm for your problem gives a solution to #Monotone-SAT. However, it is known that #Monotone-SAT is #P-complete. (In fact, we can make a stronger statement: #Monotone-2SAT is also #P-complete.) It is widely believed that #P-complete problems cannot be solved in polynomial time. Thus, there is unlikely to be any polynomial-time algorithm for #Monotone-SAT -- or for your problem.

That's the bad news. Now one slight bit of hope. There are off-the-shelf #SAT solvers out there that you could try applying to your problem. See, e.g., https://cstheory.stackexchange.com/q/1295/5038 for some pointers. Now you shouldn't expect them to be efficient -- they are subject to the same hardness result, and so they might be very slow for all but small problem instances. However, if you absolutely must solve your problem in practice, this is something you could try. There are also tools for approximate model counting, which could be used to compute an approximation/estimate for the number of solutions to your problem -- however, again, this is a hard problem and you shouldn't expect algorithms with a good worst-case running time.

My thanks to Ricky Demer for the key insight that enabled me to recognize the relationship to #Monotone-SAT.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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