Given a set $S$ of sets, what is the fastest algorithm to check if elements of $S$ form an anti-chain with respect to subset ordering? That is, how can I quickly decide if there exists two sets $A$ and $B$ in $S$ such that $A \subseteq B$?
Fast Algorithm to Check if a Set of Sets forms an Anti-chain
ds.algorithms;ds.data structures
This problem is SETH-hard at time $n^2$ (Williams 04). There is is no $n^{2-\epsilon}$ algorithm for any $\epsilon > 0$ if the universe has size $\omega(\log n)$.For small universe size ($c \log n$ for some $c$), there is an algorithm with time $n^{2-1/O(\log c)}$ (Abboud, Williams, Yu 15)