Given $n$ subsets $S_1,\ldots,S_n$ of $\{1,\ldots,d\}$.Check whether there are sets $S_i,S_j$ with $S_i \subsetneq S_j$. (If so, find an example, if not, simply say no)The trivial solution to this problem goes through all pairs of sets and checks inclusion for a pair in time $O(d)$, so the overall runtime is $O(n^2 d)$. Can this problem be solved faster? Is there a name for it in the literature?
What is the fastest way to check for set inclusion?
ds.algorithms;reference request
You cannot solve it in $O(n^{2-\epsilon})$ time for any constant $\epsilon>0$ unless the Strong Exponential Time Hypothesis is false.That is, if we had such an algorithm, we could solve $n$-variable CNF Satisfiability in $O((2-\epsilon')^{n})$ time for some $\epsilon'>0$.The reason is that we could divide the variables in two equal parts $P_1$ and $P_2$ of $n/2$ variables each. For each part we constructa family $F_1$ and $F_2$ respectively of subsets of the clauses in the following way. For each assignment we add a subset consisting of theclauses not satisfied by the assignment. This construction runs in $poly(n)2^{n/2}$ time.To finish the construction, we note that the original CNF instance has a solution iff there is a subset in $F_1$ which is disjoint to some subset in $F_2$.Adding some extra elements to your ground set in addition to the ones for each clause, it is not too hard to embed this disjointness problem as a question ofset inclusion. You basically take the complements of the subsets in $F_1$. To make sure two sets in $F_1$ isn't counted as an inclusion you add a code from an anti-chainon the extra elements. Another anti-chain code (on other extra elements of the ground set) is used on the subsets of $F_2$ to make sure no pair of subsets from $F_2$ form an inclusion.Finally, all sets formed from $F_1$ includes all elements of $F_2$'s anti-chain codes.This is a set inclusion question on $2^{n/2+1}$ subsets on a $d=poly(n)$ ground set. The argument basically goes back to some early paper of Ryan Williams (can't remember which).