# Fast Algorithm to Check if a Set of Sets forms an Anti-chain

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

• This problem is SETH-hard at time $n^2$ (Williams 04). There is no $n^{2-\epsilon}$ algorithm for any $\epsilon > 0$ if the universe has size $\omega(\log n)$. Do you care about subpolynomial improvements over n^2 or is your universe very small? – Stefan Schneider Sep 5 '16 at 2:08
• Thanks for the pointer. Exactly what I was looking for. The universe is not very small but I was hoping that some near linear time algorithm exists. So, I don't care about sub-polynomial improvements in this case. Also, if you write down your comment in an answer, I would be able to accept it :-) – Shahab Sep 5 '16 at 10:23

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)