2
$\begingroup$

Say you've got a number of sets $S_1,...,S_n$ given and are supposed to calculate $\,\,\displaystyle\big|\bigcup_{i=1}^n S_i\big|$ .

The basic approach probably would be to use the classic inclusion-exclusion principle $\displaystyle\sum_{\emptyset \not= I \subseteq \{1, \dotsc, n\}} \left(-1\right)^{|I|+1}|A_I|$ , where $A_I = \,\,\displaystyle\bigcap_{i\in I}^n S_i$ .

However, inclusion-exclusion feels like it's terribly inefficient - after all, we need to sum over $\displaystyle\sum_{i=1}^n\binom{n}{i} = 2^n-1$ possible sets.

While I guess that there's no algorithm with polynomial complexity for this problem, I'm curious about alternatives that are more efficient (i.e. have polynomial run time in most cases), or are simply largely different.

I'd be thankful if you could name alternative algorithms or optimizations to inclusion-exclusion.


The particular problem I'm trying to write an algorithm for is unsatisfiability in Propositional logic for formulas in CNF. I.e. we have a finite set of atomic formulas $\{p_1,...,p_m\}$. Over these atomic formulas, the clauses of the CNF of the formula are built after these rules:
For ever atomic formula $p$, there may either appear $p$, $\lnot p$ or none of the two in the clause.

As the whole problem was either $NP$ or $co-NP$, there most likely isn't a polynomial algorithm, but I am struggling to just make it anyhow just a little bit more efficient than inclusion-exclusion (besides using ideas that have little to do with the algorithm itself like pure-literals or pure-clauses).


Yes, each set itself is discrete with each element in the set being specified. One example would be $\{ \{\bar A, B \},\{B,C \},\{ A,B \} \}$. However, to fit the example, the initially given inclusion-exclusion algorithm would need to be modified.

This is the case as every clause in the CNF is a representative for a bigger clause, e.g. in the above example $\{\bar A, B \}$ stands for
$ \{\bar A, B ,C \} \{\bar A, B ,\bar C \} $
and $\{B,C \}$ stands for
$ \{B,C, A \} \{B,C ,\bar A \} $

You get the actual set the representative represents by the following algorithm:

Be $M$ a set of the clause, and $S$ our output set. Add $M$ to $S$. Now repeat as long as possible:

Find an atomic formula $A$ so that $A\notin K$ and $\bar A \notin K$ for some $K\in S$.
Remove $K$ from $S$.
Add $K\cup \{A\}$ and $K\cup \{\bar A\}$ to $S$.

Finally, delete all sets in $S$ where $A,\bar A \in S$ for some $A$ and return $S$.

(An atomic formula in this case is simply any letter somewhere in $M$ without the bar (i.e. $A$ for $\bar A$))

This version of the algorithm however is at this point pretty dumb. You can improve it by not explicitly generating the actual sets and calculate it with the representants and applying some arithmetic instead.

It goes like this: Let $A_1,...,A_n$ be our atomic formulas that appear in a set of clauses $\mathcal{K}$. For every $K\in\mathcal{K}$ you can calculate how many sets $K$ actually represents by counting the elements of $K$, let's name it $c$, and calculate $2^{n-c}$.
So, we calculate the sum all the way above, i.e. $$\displaystyle\sum_{\emptyset \not= I \subseteq \{1, \dotsc, n\}} \left(-1\right)^{|I|+1}|A_I|\text{ , where }A_I = \,\,\displaystyle\bigcap_{i\in I}^n S_i$$ just that we calculate $|A_I|$ not by $\big|\,\,\displaystyle\bigcap_{i\in I}^n S_i\big|$, but by calculating how many sets $\,\,\displaystyle\bigcup_{i\in I}^n S_i$ represents (with special case $|A_I|=0$, if $A_I$ contains $A$ and $\bar A$ for some atomic formula).

$\endgroup$
4
  • $\begingroup$ What are the elements of the sets? Integers? If yes, do they have a finite domain? Are there bounds on the size of the sets? $\endgroup$
    – orlp
    Apr 7, 2018 at 16:21
  • $\begingroup$ How are the sets $S_1,\dots,S_n$ provided? Do we get an explicit list of the elements in each set? In that case, there is a simple polynomial-time algorithm based on sorting them and then merging them. Or are the sets specified implicitly in some other way? In that case, you need to tell us how they are represented for us to be able to answer the question. $\endgroup$
    – D.W.
    Apr 8, 2018 at 3:40
  • $\begingroup$ @D.W. Would you mind mentioning the algorithm anyway, even if it doesn't fit for the problem? $\endgroup$
    – Sudix
    Apr 14, 2018 at 1:45
  • $\begingroup$ @Sudix, en.wikipedia.org/wiki/Merge_sort, en.wikipedia.org/wiki/Merge_algorithm $\endgroup$
    – D.W.
    Apr 14, 2018 at 17:17

1 Answer 1

3
$\begingroup$

Unfortunately, if the only reasonable method to solve a problem is via inclusion/exclusion, it's going to take $\Omega(2^n)$ time. The reason for this is simple, there are $2^{n}-1$ sets we must inspect (if we don't, then we wouldn't have to do inclusion/exclusion!) So, there are no significant general improvements on inclusion/exclusion.

Asking for an algorithm to "have polynomial run time in most cases" is a rather vague empirical claim that is unfortunately hard to answer precisely and could have little value. A way to make this precise is a probabilistic algorithm. I'm not aware of any probabilistic variants of inclusion/exclusion, but I think that using another method than inclusion/exclusion would be better to create a probabilistic variant.

However, is inclusion/exclusion worthless? No. Often, inclusion/exclusion is used to obtain an algorithm that takes exponential time, but has only polynomial space usage. (sometimes, exponential space is a bigger problem in practice than exponential time!) For instance, the Hamiltonian cycle problem can be solved in $O^*(2^n)$ time but only polynomial space by inclusion/exclusion.


It could be the case that your specific problem has a more efficient solution, but that solution method then is likely very different from inclusion/exclusion.

$\endgroup$
2
  • $\begingroup$ What is the unit of time here that takes $O(1)$? I don't see why this would take exponential time - can't you explicitly compute the union and then compute the size? I feel like I'm missing something. $\endgroup$
    – orlp
    Apr 7, 2018 at 16:33
  • $\begingroup$ @orlp Requiring $O(1)$ for incrementing a loop counter would be enough. Note that we originally have $n$ sets that are subsets of an universe of that is typically of exponential size. For instance, for the universe in the case of the Hamiltonian path we can take all cyclic walks on the graph of length $1$ to $n$, where each $S_i$ contains all of those walks that visit vertex $i$. $\endgroup$
    – Discrete lizard
    Apr 7, 2018 at 17:18

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.