Algorithm to decide if the union of a set system covers the power set

Question

Assume that we have a set system $\mathfrak T = \{\mathcal T_1, \mathcal T_2, \dots, \mathcal T_N \}$ where each $\mathcal T_k$ is a collection of subsets of $[n] := \{1,\dots,n\}$ of the form $$ \mathcal T_k = [m_k, M_k] := \{T \subseteq [n]:\; m_k \subseteq T \subseteq M_k \}. $$ Moreover, we know that $\mathcal T_k$s are mutually disjoint, i.e., $\mathcal T_k \cap \mathcal T_{k'} = \emptyset$ when $k \neq k'$, which implies that $N \le 2^n$. Note also that $\mathcal T_k \subseteq 2^{[n]}$ for each $k$.

Question: Is there an algorithm with polynomial time in $(N,n)$ to either find a subset in $2^{[n]}$ which is not in any of the $\mathcal T_k$s when possible, otherwise conclude that $\bigcup \mathfrak T := \bigcup_{k=1}^N \mathcal T_k = 2^{[n]}$, i.e. the set system covers the power set?

EDIT: Changed the number of subsets to $N$ instead of $m$. Corrected the question from polynomial time in $n$ to polynomial time in $(N,n)$. Also, fixed the statement regarding the union of elements of $\mathfrak T$. There were many confused statements in the original post. Hopefully, this version is clear. The problem is to see if we can cover the power set, not the ground set $[n]$. That is, all the action is at the level of subsets of $[n]$.

Answer 1

Given $T_k = [m_k,M_k]$ and $X\subseteq [n]$, it is easy to calculate the number of sets in $T_k$ that contain $X$: $$Q_{X,k}=|\{T\in T_k \mid X\subseteq T\rbrace|.$$

So start with $\sum_k Q_{\emptyset,k}$. If it equals $2^n$, every subset of $[n]$ is covered.

Otherwise, there is $x_1\in [n]$ such that $\sum_k Q_{\lbrace x_1\rbrace,k} \lt 2^{n-1}$; find it by trying the $n$ cases. Then find $x_2$ such that $\sum_k Q_{\lbrace x_1,x_2\rbrace,k} \lt 2^{n-2}$ by trying all cases for $x_2$. Continuing in this manner, after at most $n$ rounds you will have $X\subseteq [n]$ such that $\sum_k Q_{X,k}=0$.

Altogether it seems to need something like $O(n^2N)$ operations on sets.

Answer 2

With some preprocessing time, you should be able to do it in about N times n queries. I can't imagine it being done in much less time. For example, you need to distinguish between the case that you have N = 2^{n-1} - 1 disjoint two element intervals (when you are missing a two element interval from a complete cover) and the case with the same N where one of the intervals has four elements and is a complete cover. Here is how I would start, with the assumption that the N lattice intervals have been processed so that their top elements M_i and maximal elements (inside T_i and just below M_i) are accessible with a single query or at most n queries.

Start with the top level set which I will call n (avoiding square brackets). Preprocessing allows me to pick the set T that contains n, and the k many maximal elements of T just below n. If k=n (notation clash), then we are done as T covers the whole power set being an interval.

Otherwise there are n-k sets of size n-1 not covered by T, and we know which ones. For each of them, either there is another set T that covers that n-1 set, or we have found an uncovered set. Anyway, put the n-k sets in a list and go through them one by one.

Now if we are lucky, all the size n-2 sets under these (n-k) many size (n-1) sets are covered by n-k intervals T. Otherwise we have to start a list of size (n-2) sets that are not covered. (Also, if the first set T had k=1, that T is an interval containing n and a size (n-1) subset m, so we have to worry about all the size (n-2) subsets of m. So put those subsets of m in the n-2 list to check.)

In this way we descend level by level, checking uncovered sets of smaller size. However, because of the preprocessing, as we look at each potentially uncovered set, we either find a T which has that as its M, or we stop because the set M is not covered. For each such T, we check at most n subsets of its M to determine what sets one level down are not covered, which is at most nN queries.

Gerhard "Layer Cakes And Archaeological Excavations" Paseman, 2018.08.15.

Answer 3

Note that because $T_k$ are disjoint, it is trivial to check whether they cover $[n]$: just add up their sizes ($|T_k| = 2^{|M_k| - |m_k|}$) and compare the sum with $2^n$: if it is smaller than $2^n$, then there exists a uncovered subset of $[n]$, otherwise there is no such subset.

Quite often, if there exists a polynomial time algorithm for decision problem, there also is a polynomial time algorithm for finding a certificate. In the case of this problem it is true as well. Indeed, consider the following procedures:

do_cover($n, T$):
$~~~~$Returns whether $T$ covers $[n]$. Checks this by simply summing up $|T_k|$.

reduce($n, T, b$):
$~~~~$Reduces each $T_k$ by leaving only sets that contain $n$ or not
$~~~~$if $b = 1$ or $b = 0$ respectively. In case of $b = 1$ element $n$
$~~~~$is also deleted from all sets that belong to $T_k$.
$~~~~$Returns reduced $T$ (and does not modify $T$)
$~~~~$This reduction preserves disjointness of $T_k$ and the
$~~~~$fact that $T_k = [m_k, M_k]$ for some $m_k, M_k \subset [n]$.
$~~~~$Reduced $T_k$ may become empty, but that does not matter much.

find_uncovered($n, T$):
$~~~~$if do_cover($n, T$):
$~~~~~~~~$no such element then
$~~~~$if n == 0:
$~~~~~~~~$just try both possibilities

$~~~~$Now, we know for sure that there exists a subset of $[n]$
$~~~~$that is uncovered and want to find this subset.
$~~~~$There are 2 possibilities: either it contains element $n$,
$~~~~$or it does not. We will just iterate over them.

$~~~~$if do_cover($n - 1$, reduce($n, T, 0$)):
$~~~~~~~~$return find_uncovered($n - 1$, reduce($n, T, 0$))
$~~~~$else if do_cover($n - 1$, reduce($n, T, 1$)):
$~~~~~~~~$return find_uncovered($n - 1$, reduce($n, T, 1$)) $\cup \{ n \}$
$~~~~$else:
$~~~~~~~~$can't happen, because there is an uncovered set

Clearly, find_uncovered runs in polynomial time of $n$ and $N$ (because do_cover does).

Now, note that the same problem is NP-hard if there is no restriction of $T_k$ being disjoint. Indeed, consider some 3-SAT instance with $n$ variables $x_1, x_2, \ldots, x_n$ and $N$ clauses. $T_k$ for $k = 1, 2, \ldots, N$ will consist exactly from such subsets $S$ of $[n]$ such that setting $x_i := (i \in S)$ for all $i = 1, 2, \ldots, n$ will make $k$-th clause false. Clearly, a solution of original problems for such $T_k$ would yield a solution to our 3-SAT instance.

P. S. The solution above for the case of disjoint $T_k$ can be implemented quite efficiently if you forego the immutability of $T$ that I used for clarity. Indeed, you only need to keep $m_k, M_k$ and sum of $|T_k|$. All queries and changes that you'll do all end up very small: you just ask whether some element belongs to some set $m_k$ or $M_k$, do similar minor modifications to $m_k$'s and $M_k$'s (don't forget to update the sum of $|T_k|$, when doing so) and check whether the sum of $T_k$ is equal to $2^x$ for some $x$.