2
$\begingroup$

Say we have $n$ sets $A_1,\dots,A_n$ with elements from a universal set $U$.

We want to compute the cardinality of $\cup_{i=1}^n 2^{A_i}$ or at least decide on non-trivial bounds. Is this problem NP-complete?

The obvious counting algorithm is $\mathcal{O}(n 2^m)$ where $m = \max_i |A_i| \leq |U|$.

I tried using the principle of inclusion-exclusion since intersections of power sets has nicer behavior. This gives $\mathcal{O}(2^n m)$ solution. I suspect there might be a nice reduction from set-cover or by recasting the sets and elements as vertices in a bipartite graph, but I haven't had any luck.

In the special case where our set-system is a sunflower with core $|Y| = k$, then $|\cup_{i=1}^n 2^{A_i}| = \sum_{i=1}^n 2^{|A_i|} - (n - 1) 2^k$. I thought that maybe the sunflower lemma could reduce the problem to a smaller size, but I can't see how to create a new problem by taking out a sunflower.

$\endgroup$
3
  • 2
    $\begingroup$ It is #P-complete. There is a reduction from counting vertex covers. $\endgroup$
    – Laakeri
    Jan 30, 2022 at 19:39
  • 1
    $\begingroup$ @Laakeri Can you elaborate on the reduction? $\endgroup$ Jan 30, 2022 at 22:19
  • $\begingroup$ In the case when each element in $U$ is in at most $d=O(1)$ sets, I guess inclusion-exclusion gives you an $O(n^d)$-time algorithm. $\endgroup$
    – Neal Young
    Feb 7, 2022 at 21:50

1 Answer 1

2
$\begingroup$

It is $\#P$-complete. Here is a reduction from counting vertex covers. Let $G = (V,E)$. We wish to count the number of sets of vertices that are not vertex covers. We observe a set $X \subseteq V$ is not a vertex cover if and only if there exists an edge $uv \in E$ so that $X \subseteq V \setminus \{u,v\}$. Now, we have that the family of all sets of vertices that are not vertex covers is equal to $\bigcup_{uv \in E} 2^{V \setminus \{u,v\}}$.

$\endgroup$

Your Answer

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

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