5
$\begingroup$

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]$.

$\endgroup$
  • $\begingroup$ How can it be polynomial in $n$ if $m \sim 2^n$? You can't scan all of $\mathfrak T$ in polynomial time. $\endgroup$ – Robert Israel Aug 15 '18 at 17:00
  • 1
    $\begingroup$ OP your notation is hard to follow...$m$ is an integer in the top line whereas in the math equation just below $m_k$ is a set(?) $\endgroup$ – Mike Aug 15 '18 at 17:11
  • $\begingroup$ @RobertIsrael what I am getting is that there is some extra structure to the problem i.e., if we were to get our hands on the $M_k$s then we could check in polynomial time if there exists a point not covered by any of the $\mathcal{T}_k$s and if so get our hands on it. That the $\mathcal{T}_k$s are mutually disjoint may imply a stronger bound on $m$ besides $m \le 2^n$? $\endgroup$ – Mike Aug 15 '18 at 17:14
  • $\begingroup$ Since $\mathcal T_k \cap \mathcal T_{k'} = \emptyset$, you can just go through $\mathcal T_k $ one by one and throw elements of each $\mathcal T_k $ in a hash table. This will be linear in $n$. $\mathcal T_k \cap \mathcal T_{k'} = \emptyset$ guarantees that total size of all $\mathcal T_k$ won't exceed $n$. $\endgroup$ – Pratik Deoghare Aug 15 '18 at 17:15
  • 1
    $\begingroup$ You could have each $\mathcal T_k$ consist of a single subset, giving $m=2^n$. $\endgroup$ – Robert Israel Aug 15 '18 at 17:55
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Or, if you have the guarantee of disjointness and each T being an interval, just add up the sizes of the T's which are computable from M and m. Gerhard "That's Enumeration At Its Finest" Paseman, 2018.08.15. $\endgroup$ – Gerhard Paseman Aug 15 '18 at 21:39
  • $\begingroup$ I am interested in an answer too, but I must admit that I am finding this hard to follow. So is $T$ a set? A collection of subsets? What do you mean by two-element intervals? But yes, it is easy to calculate the size of each $\mathcal{T}_k$(given each $M_k$ and $m_k$) and as the $\mathcal{T}_k$s are disjoint, $|\cup_k \mathcal{T}_k|$; to see whether there is a solution, compare $|\cup_k \mathcal{T}_k|$ to $2^n$. $\endgroup$ – Mike Aug 16 '18 at 2:43
  • $\begingroup$ I am avoiding a lot of Tex. T is one of the N subsets of the power set of n that are contained in the given collection script T. In the lattice of the power set of n, each member of script T is not just a subset T, it is an interval in this lattice. One example is a two element interval given by the collection {n,n'}, where n' is a subset of n with one fewer element. Gerhard "Can Dot Some I's Too" Paseman, 2018.08.15= $\endgroup$ – Gerhard Paseman Aug 16 '18 at 2:58
  • $\begingroup$ @GerhardPaseman, thanks. This looks interesting (e.g. using the lattice structure). I agree that the notation is a bit confusing! But I think I understand your point and a figure might help. A few comments: (1) "Preprocessing allows me to pick the set T that contains n", there might not be such $\mathcal T$ to start with, so we might start down the lattice hierarchy. (2) "For each of them, either there is another set T that covers that n-1 set", in which case $\mathcal T$ necessarily has to have the n-1 set as it maximum element M. Right? $\endgroup$ – passerby51 Aug 18 '18 at 2:56
  • $\begingroup$ @GerhardPaseman, (3) technically, M would be the maximal (and maximum) element of the interval [m,M], but I understand that you are using maximal elements to refer to those elements directly below M. (4) I am not sure about the complexity: O(nN) seems to be the case if we can decide whether a given set appears as M of some $\mathcal T$ in our collection with O(1) operations. But it seems that this requires at most O(N) operations? So would the complexity be O(n N^2) instead? $\endgroup$ – passerby51 Aug 18 '18 at 3:18
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ thanks, very interesting approach. Re: "Quite often, if there exists a polynomial time algorithm for decision problem, there also is a polynomial time algorithm for finding a certificate" I was wondering about this as well! Is this part of the folklore of complexity theory? Could you point me to a reference? Also, thanks for pointing the connection to 3-SAT problem. $\endgroup$ – passerby51 Aug 18 '18 at 3:06
  • 1
    $\begingroup$ This is like a folklore statement, which is often true. Of course, there are cases when we believe the opposite, say factoring (search) vs primality checking (decision). A few links that I found by a quick search, that illustrate nicely how such reductions usually look like: cs.sfu.ca/~kabanets/308/lectures/lec12.pdf cs.stackexchange.com/questions/39673/… $\endgroup$ – Kaban-5 Aug 18 '18 at 11:31

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.